魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 2427628|回复: 94

非专业分析KCube [复制链接]

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2010-4-14 20:15:40 |显示全部楼层
目前,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 编辑 ]

KCube1.0.rar

58.91 KB, 下载次数: 87

已有 2 人评分经验 收起 理由
oyyq99999 + 20 重量级技术贴
ynjyht + 10 精品文章,加分支持

总评分: 经验 + 30   查看全部评分

Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2010-4-14 20:17:27 |显示全部楼层
先占领沙发,如果有十个以上的支持者,那么就地分析。
十位齐了,开工了。

这一楼准备分析一下概况,顺便介绍些入门知识给初学的朋友,高手不要笑话啊。


原始文件概况:
一共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 编辑 ]
文件列表.JPG
已有 3 人评分经验 收起 理由
臭虫 + 10 非常支持
cube_master + 20 支持!
superacid + 20 原创内容

总评分: 经验 + 50   查看全部评分

Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

使用道具 举报

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2010-4-14 20:19:07 |显示全部楼层
4.所有的头文件
头文件给出了类的定义,先看每个类公开了那些属性、方法
总共10个头文件,Vectorcombinat两个文件没有定义类,其余都定义了类

CubeParse接受键盘输入,着色FaceletCubeFaceletCube接受着色输入,检查输入;在检查输入的时候,会顺便填写一个Cube的状态码;KocimbaCube则可详细分析Cube的状态,分别来设定各种状态。以上类在4个头文件。

表的管理,有两种表,MoveTablePruningTableMoveTable有六个子类,都在Kocimvot中定义,这个文件没有对应的cpp;MoveTable声明是一个独立的文件;PruningTable是乘法表(或分支表?),感谢铯告知,是剪枝,这个是专业的称呼了。 存储内容可视作深度值。所以有3个头文件是管理表的。

Solver不必多说,最硬的骨头大概在里面。

值得注意的是类的继承,基类中的函数有虚有实。




[ 本帖最后由 aubell 于 2010-4-15 21:17 编辑 ]
pub1.JPG
pub2.JPG
Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

使用道具 举报

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2010-4-14 20:20:36 |显示全部楼层
5. VECTOR 和 combinat
这两个是作者的最基本的“库”

vector是向量,这里就是简单的整数数组而已。vector.cpp中定义了两个
函数,CopyVector和PrintVector,前者简单的调用库函数memcpy完成数组
拷贝,后者就是依次输出数组内容。这两个函数没有什么特别的地方。但
这个类定义了Vector,意味着比数组高一点的抽象。

combinat,组合
名称虽然叫组合,但combiant.cpp中,不仅定义了组合,还定义了排列。

NChooseM函数:计算选择数,就是通常用二项式定理或者杨辉三角计算的选择数,
实现的比较美观和高效,值得学习。作者在注释这个函数时,对排列组合的介绍十分详细。
详细的过了,呵呵。只要注意第一个参数大,第二个小就行了。

OrdinalToPermutation和PermutationToOrdinal函数:
因为魔方会用向量来表示,也就是一个数组。数组顺序就表示了魔方不同的方块在不同的
位置,假如 [01234567] 表示的是原始的魔方八个角的位置, [10234567]就表示特定的两块换了
位置。这是两个不同的排列。有人说了:你直接用整数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 编辑 ]
Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

使用道具 举报

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2010-4-14 20:21:48 |显示全部楼层
第五层也要,好了,不占楼了。

如果支持者有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[p] > permutations[q])
    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 编辑 ]
已有 1 人评分经验 收起 理由
superacid + 10 靠,给你加分还不算我是支持者...

总评分: 经验 + 10   查看全部评分

Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

使用道具 举报

铜魔

♂鉦版宅娚ミ

Rank: 8Rank: 8

积分
10831
帖子
9358
精华
1
UID
90305
性别

爱心大使 六年元老

发表于 2010-4-14 20:25:09 |显示全部楼层
支持,虽然我看不懂,为大众服务
哥拧的不是魔方,是寂寞
“人生就好比魔方,要想好下一步该怎么走”
魔方吧-福建超级群:63887957
玩魔方就是玩个低调

使用道具 举报

透魔

已退役

Rank: 6Rank: 6

积分
6788
帖子
4147
精华
5
UID
12912
性别
WCA ID
2010zeng03
兴趣爱好
其它

论坛建设奖 爱心大使 六年元老 十年元老

发表于 2010-4-14 20:29:44 |显示全部楼层
还没学C++,对程序不了解,但也支持LZ,以后可以学习下!
【已从魔界退役!勿寻我!】

使用道具 举报

Rank: 3Rank: 3

积分
787
帖子
769
精华
0
UID
1254153
性别
保密
发表于 2010-4-14 21:01:12 |显示全部楼层
我愿意出10分之1的力

使用道具 举报

Rank: 3Rank: 3

积分
996
帖子
868
精华
0
UID
1242458
性别
发表于 2010-4-14 21:02:37 |显示全部楼层
这样的事是一定要顶的。。
该开始练了,为什么还在等待

使用道具 举报

Rank: 1

积分
90
帖子
87
精华
0
UID
1254639
性别
保密
发表于 2010-4-14 21:28:28 |显示全部楼层
我来十楼,哈哈,支持支持~

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-1-18 21:27

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部