非专业分析KCube
目前,Kociemba是我们学习最少步数时无法绕开的名字。我准备把 Greg Schmidt的程序KCube1.0分析一下,希望真正
对2-phase理解。
大名鼎鼎的CubeTwister里有一个求解的程序,大家在网上下载到源码以后,
在这个目录层次下可以找到:
cubetwister-2.0alpha125src\CubeTwister\src\main\ch\randelshofer\rubik\solver
这个程序是把KCube用Java重写了,喜欢看java代码的朋友可以看看。
遇到难的地方,大家一定要不吝赐教啊。
有人支持吗?
感谢大家的支持
夜雨听风
329774632
AlphaCB
mengfl
斜月
yanzi7816
今夜微凉
zbyxzh
dangerxxxx
r_517
yq_118
臭虫
ynyht
superflip
oyyq99999
superacid
铯_猪哥恐鸣
ggglgq
cube_master
[ 本帖最后由 aubell 于 2010-5-1 15:52 编辑 ] 先占领沙发,如果有十个以上的支持者,那么就地分析。
十位齐了,开工了。
这一楼准备分析一下概况,顺便介绍些入门知识给初学的朋友,高手不要笑话啊。
原始文件概况:
一共23个文件,10个头文件(.h),10个C++文件(.cpp),
一个KCube.exe,一个readme.txt,一个批处理文件(.bat)。
头文件和C++文件基本一一对应,不对应的有:
kocimovt,只有头文件;kcube只有cpp文件。
运行后,将增加几个文件:
6个.mtb文件,5个ptb文件。
这几个是查表用的文件,在第一次运行的时候生成,以后每次运行直接调入内存,
就连CubeExplorer也是这样工作的。生成的表总共占硬盘空间:6M多。
这个数据远小于CubeExplorer4.64生成的64M表。所以在计算时可能不会达到极速。
CubeExplorer4.64在使用优化的时候,要用637M的硬盘表,1G内存。
所以,写这种程序,要先估计一下空间。
全部状态都存储下来,是不可能的。
最牛的程序,个人认为是Tomas Sirgedas在一次竞赛中写的程序,没有使用外部表,
而速度很快,步数也很少,基本上解都在33步左右。那个程序很短小,但越是短小
的程序,通常越难分析;何况那个是为了比赛“最短小的程序”而写的,代码长度
优化后,可读性势必要打折扣。
所以,选择分析这个很长的、而且作者作了注解的程序。
结论:时间和空间是要考虑的因素;不是越短的程序越好读懂。
编译器:这个代码之在VC6.0下可以编译通过。
有很多地方不符合现在的C++标准。
莫非这个代码是标准出来以前就有的?
所有源代码,包括空白行和纯粹注释行,3117行。
有注释总共913行,纯注释的行412行。
所以代码不算长。但初学的朋友看到了会觉的很长。
其实写到后来,会发现,最关键的只有几行而已。
我会把不那么重要的部分先分析了,这个算是LittleEndian吧。
为什么统计的时候把空白行也算上呢?
因为程序中的空白行是为可读性服务的。假如密密麻麻不留白,会很难读的。
所以建议初学写程序的朋友注意留白、注释。
1.第一个文件 SAMPLE.BAT
给出了一行命令
kcube U:WWRYOOGBY D:BWROROYYR F:WGORWBOGG B:WRORBBWOR L:YWOYYGBBG R:BGGRGYBWY
从这个命令行能看出什么呢? U D F B L R,显然是六个面,
每个面以后跟9个字母,BOY一类都有,RGB也有,w是白的,那么就是颜色;可每个面九个
贴纸按照怎样的顺序输入呢?
大概作者会说明的,多半在README中吧?
2.README.TXT
打开来瞧瞧,介绍了作者Greg Schmidt为什么要写这个程序,也是为了
深入理解Kociemba的算法,同我们的目的一样,在 Mike Reid 的建议
下开始写的。最后还有他的联系方式。
还列出了完整的文件包括哪些,防止残缺。
中间有一句“Please see cubemain.cpp for instructions on how to
invoke this program”,让我们到cubemain.cpp中找如何用这个程序。
但给出的文件没有cubemain.cpp,大约疏忽了,那就猜哪个是主调文件吧。
找同kcube.exe同名的cpp就是了,因为写程序,难免会疏忽,何况写帮助。
3.kcube.cpp
果然是主调程序,main函数就在这里面。命令行程序通常只有一个入口,
通常都是main。
这里的注释给了个展开图:
//For example, consider the following "unfolded"
// cube:
// Red Red Wht
// Yel Wht Wht
// Wht Red Red
//
// Wht Wht Grn Org Yel Yel Blu Red Org Yel Grn Grn
// Red Org Org Yel Yel Yel Blu Red Org Blu Grn Blu
// Yel Wht Grn Org Wht Org Yel Blu Blu Red Grn Red
//
// Blu Org Blu
// Grn Blu Grn
// Wht Org Grn
//
// With the faces above corresponding to:
//
// Up
// Left Front Right Back
// Down
//
// Then one possible way to enter this configuration is:
//
// >cube L:WWGROOYWG R:BROBROYBB U:RRWYWWWRR D:BOBGBGWOG
// F:OYYYYYOWO B:YGGBGBRGR
这个图很重要,有了这个图,就知道输入的顺序了,是展开图的顺序。
而且,不标准的配色应该也可以。
但真的在输入的时候,也不会很轻松,搞反前后左右的事情很常见,弄错弄丢一
两片贴纸也很常见,这是命令行程序的缺点;就算用图形界面的CubeExplorer,
有时都会输入错误。而且,等它给出答案,你还要在魔方是试试,看对不对... ...
真佩服早期玩电脑的朋友,在DOS下,内存没多大,界面没图形,
那时的解魔方的程序是怎样写的呢?怎样玩的呢?
魔方难,程序难,魔方程序就更难了。
魔方好玩,程序好玩,魔方程序就更好玩了。
言归正传。
main函数里出现了四个类的对象,
FaceletCube faceletCube;
CubeParser cubeParser;
KociembaCube cube;
Solver solver;
名称起的好,让我们顾名思义,整个流程是这样的:
parser接受命令行输入的,并且为facletCube着色,
facletCube检查一下,着色是否正确,如果着色错误,直接退出;
正确的话,就转化成一个Kociembacube,让solver来解。
[ 本帖最后由 aubell 于 2010-4-15 20:02 编辑 ] 4.所有的头文件
头文件给出了类的定义,先看每个类公开了那些属性、方法
总共10个头文件,Vector和combinat两个文件没有定义类,其余都定义了类
CubeParse接受键盘输入,着色FaceletCube;FaceletCube接受着色输入,检查输入;在检查输入的时候,会顺便填写一个Cube的状态码;KocimbaCube则可详细分析Cube的状态,分别来设定各种状态。以上类在4个头文件。
表的管理,有两种表,MoveTable和PruningTable,MoveTable有六个子类,都在Kocimvot中定义,这个文件没有对应的cpp;MoveTable声明是一个独立的文件;PruningTable是乘法表(或分支表?),感谢铯告知,是剪枝表,这个是专业的称呼了。:D 存储内容可视作深度值。所以有3个头文件是管理表的。
Solver不必多说,最硬的骨头大概在里面。
值得注意的是类的继承,基类中的函数有虚有实。
[ 本帖最后由 aubell 于 2010-4-15 21:17 编辑 ] 5. VECTOR 和 combinat
这两个是作者的最基本的“库”
vector是向量,这里就是简单的整数数组而已。vector.cpp中定义了两个
函数,CopyVector和PrintVector,前者简单的调用库函数memcpy完成数组
拷贝,后者就是依次输出数组内容。这两个函数没有什么特别的地方。但
这个类定义了Vector,意味着比数组高一点的抽象。
combinat,组合
名称虽然叫组合,但combiant.cpp中,不仅定义了组合,还定义了排列。
NChooseM函数:计算选择数,就是通常用二项式定理或者杨辉三角计算的选择数,
实现的比较美观和高效,值得学习。作者在注释这个函数时,对排列组合的介绍十分详细。
详细的过了,呵呵。只要注意第一个参数大,第二个小就行了。
OrdinalToPermutation和PermutationToOrdinal函数:
因为魔方会用向量来表示,也就是一个数组。数组顺序就表示了魔方不同的方块在不同的
位置,假如 表示的是原始的魔方八个角的位置, 就表示特定的两块换了
位置。这是两个不同的排列。有人说了:你直接用整数10234567表示角块的排列不就得了?何必还
要弄个数组呢?其实直接用整数也未尝不可,但在转动的时候操作不同的位不是那么方便和直观。
所以这里有排列和整数之间的转换,当然不是直接连起来就得了。这个算法是经典的算法。
使得固定长度的全排列同连续的整数一一对应,相互转换。
也就是说,一个整数对应着唯一种排列,一个排列只有唯一的这个整数同它对应。
这个经典的算法,假如让我们自己设计,大概只有天才才能设计的出。
作者说了,他也是从书上照搬的。
因为经典,计算机专业的同学都会学习到,生成排列和生成组合的方法。
由于不是专业的,就只尝试一下结果看看,不详细分析来历。
试了一下4的全排列,没看出什么规律来,就发现0123是最后一个。
0:3 0 1 2
1:3 1 0 2
2:3 2 0 1
3:3 2 1 0
4:3 0 2 1
5:3 1 2 0
6:2 3 1 0
7:2 3 0 1
8:1 3 0 2
9:0 3 1 2
10:1 3 2 0
11:0 3 2 1
12:2 0 3 1
13:2 1 3 0
14:1 2 3 0
15:0 2 3 1
16:1 0 3 2
17:0 1 3 2
18:2 0 1 3
19:2 1 0 3
20:1 2 0 3
21:0 2 1 3
22:1 0 2 3
23:0 1 2 3
这个算法给出的顺序和CubeExplorer帮助文件中给出的似乎不同。
不是严格的降序或升序。
但这没有关系,只要一一对应就好。
其实,许多朋友都想直接拿一个整数代替整个魔方的状态,
那个整数可能很长,操作起来也不会方便到哪儿去。如果配合好的hash存储,
也是有可能的。
这个程序的做法是:把排列对应的整数存储到表中,记录下在某个操作下
会到达哪一个新的排列对应的整数。
(
补充
所以,从魔方排列到整数的工作只做一次,以后每次搜索,
都直接使用硬盘上存好的状态转移表(move table)。
状态转移表的索引方式是这样的:
新状态=Table[旧状态][操作]
)
为什么这里只提到位置排列,不理会方向呢?
( 方向也是使用类似的movetable )
因为2-phase是受到Thistlethwaite方法启发而设计的。虽然是基于复杂的群论的方法,
但表现在魔方是很自然和简明的方法,
原始的Thistlethwaite分四步走:
(1)还原所有棱的方向
(这个“方向”的表现形式同盲拧四步法是一致的)
可以使用18种基本操作(RUFBLD,加'的,加2的)
(2)还原所有角的方向,同时,让E层的棱回到E层
可以使用14种基本操作(FB两个面90度的旋转被禁止,要转就转180度)
(3)调整角和棱进入到适当的位置
可以使用10种基本操作(RL两个面90度的旋转也被禁止)
(4)还原魔方
可以使用6种基本操作(UD两个面90度的旋转也被禁止)
2-phase把(1)(2)两步合并了,(3)(4)两步合并了。
也就是说,2-phase的第一步是还原了所有块的方向,并且额外做了一项工作:
E层的棱回到了E层;所以在第二步还原整个魔方的时候,就不再考虑方向了。
巧妙的是,由于对某些操作“禁止”了,在第二个步骤,无论怎么转动,都不
会破坏第一步的工作成果。这正是我们所期望的。
由于不同的程序“禁止”的顺序不同,第一步“色、面优先级”的表现形式会有不同。
有的时候,有了限制反而有了自由。呵呵。
小结:这两个文件给出了与排列组合有关的计算方法。
最重要的是让排列方式同整数一一对应。
[ 本帖最后由 aubell 于 2010-4-16 23:45 编辑 ] 第五层也要,好了,不占楼了。
如果支持者有10位以上,就开始分析了。
感谢大家的支持
夜雨听风
329774632
AlphaCB
mengfl
斜月
yanzi7816
今夜微凉
zbyxzh
dangerxxxx
r_517
臭虫
superflip
superacid
铯_猪哥恐鸣
ggglgq
cube_master
-----------------------------
6.faceletcube
这个类的定义在facecube.cpp中,名称容易引起误会。
let-表示小,facelet是指一个一个的小色块。
我就干脆称其为贴纸了。这个是贴纸水平的魔方。
表现在程序中就是:用户输入一个一个的颜色,程序给魔方贴贴纸。
在有GUI的程序中,就表现为着色了。
一旦用户着色完毕,我们要还原魔方了。没有见过机器人还原魔方的
朋友总是会问:“我把装错了的魔方给机器人,不知道会怎样”。人
们总是好奇的,期望着看笑话。所以,我们程序的第一步,肯定是:
检查着色正确与否,然后还要检查组装正确与否,不然的话,瞎转半天,
不能还原都不知道。
如果不希望做这些步骤,那么可以一开始就用一个完整的魔方,让用户
输入打乱,而不是贴纸颜色;问题是,想还原一个已经打乱的魔方,又
不知道打乱公式,那怎么玩?鸡生蛋,蛋生鸡... ...
检查参数是为了保证数据的完整性。
这个贴纸层的魔方公开的方法有:
着色、检查、输出错误信息、输出魔方的状态、面的名称变为数字。
着色的方法提供给parser用,parser从命令行接受到数据,解开,着色。
输出错误信息、输出魔方状态是很自然要做的。
面的名称变成数字,是这样的顺序 UDLRFB-012345
这个类中,重点是检查,比较精彩的代码也在这里,检查的内容包括:
中心、贴纸、角、棱、角和棱一起。
中心看是否有六个,每个要唯一,不能重复;
贴纸看是否每种颜色都是9片;
角看旋转方向加起来是否被3整除,不整除就是错的;
棱看翻转方向加起来是否被2整除,不整除也是错的;
检查方向其实是很繁琐的事情,这部分工作要格外细致。
角和棱一起,就看是否组装成只有两角交换没有棱陪伴的情况--孤立Parity。
代码中,检查Parity的一段最精彩。没有读过这段代码的朋友,可以试想一下:
你会怎样检查呢?
代码中的方法很朴实,但很有效。一般还想不到,很难想到。
我以前的程序,检查的时候竟然先编了一个盲拧的编码,然后看编码是否正确。冤。
作者的用这个方法很好,值得我们学习。
看过以后,就知道是怎么实现的。隐约知道是正确的。但为什么正确,就讲不清楚了。
请何方高人讲透彻一些?为什么排列中,元素向后两两比较的结果可以用来计算是否有Parity?
关键段落:
// Permutation parity can be computed by counting the number of
// reversals in the permutation sequence, - i.e., the number
// of pairs (p,q) such that p>q and p precedes q. Then
// determine if the result is even or odd. Do this for both
// edges (EPP) and corners (CPP). A configuration is reachable
// if EPP=CPP. (August/September cube.lovers - Vanderschel/Saxe)
int FaceletCube:: PermutationParity(int* permutations, int numberOfCubies)
{
int p, q;
int permutationParity = 0;
for (p = 0; p < numberOfCubies-1; p++)
{
for (q = p+1; q < numberOfCubies; q++)
{
if (permutations > permutations)
permutationParity++;
}
}
return permutationParity%2;
}
棱和角都有Parity或者都没有parity,就是正确的。
出现孤立Parity是组装错误。
facecube.h中有一宏值得推荐
#define FacesToCorner(face1, face2, face3) (((face1*6)+face2)*6+face3)
#define FacesToEdge(face1, face2) (face1*6+face2)
这个是传说中的秦九韶记法,很花俏的。
(下转31楼)
[ 本帖最后由 aubell 于 2010-4-19 12:53 编辑 ] 支持,虽然我看不懂,为大众服务 还没学C++,对程序不了解,但也支持LZ,以后可以学习下! 我愿意出10分之1的力 这样的事是一定要顶的。。 我来十楼,哈哈,支持支持~