魔方吧·中文魔方俱乐部

标题: 非专业分析KCube [打印本页]

作者: aubell 时间: 2010-4-14 20:15:40 标题: 非专业分析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 编辑 ]

附件: KCube1.0.rar (2010-4-14 20:15:40, 58.91 KB) / 下载次数 113
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTMyNDd8NWU5YjA0NmZ8MTc0OTQ3OTYwOHwwfDA%3D

作者: aubell 时间: 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 (2010-4-14 22:32:27, 54.83 KB) / 下载次数 184
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTM0Mjd8OWVhYzc4Yzl8MTc0OTQ3OTYwOHwwfDA%3D

作者: aubell 时间: 2010-4-14 20:19:07

4.所有的头文件
头文件给出了类的定义，先看每个类公开了那些属性、方法
总共10个头文件，Vector和combinat两个文件没有定义类，其余都定义了类

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

表的管理，有两种表，MoveTable和PruningTable，MoveTable有六个子类，都在Kocimvot中定义，这个文件没有对应的cpp;MoveTable声明是一个独立的文件；PruningTable是乘法表（或分支表？），感谢铯告知，是剪枝表，这个是专业的称呼了。

存储内容可视作深度值。所以有3个头文件是管理表的。

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

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

[ 本帖最后由 aubell 于 2010-4-15 21:17 编辑 ]

附件: pub1.JPG (2010-4-15 12:36:17, 133.93 KB) / 下载次数 196
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTM0NzJ8ZWM3ZjQzMmJ8MTc0OTQ3OTYwOHwwfDA%3D

附件: pub2.JPG (2010-4-15 12:36:17, 72.58 KB) / 下载次数 204
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTM0NzN8M2VlMjUwZTF8MTc0OTQ3OTYwOHwwfDA%3D

作者: aubell 时间: 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 编辑 ]

作者: aubell 时间: 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 编辑 ]

作者: 夜雨听风 时间: 2010-4-14 20:25:09

支持，虽然我看不懂，为大众服务

作者: 宇枫幽蓝 时间: 2010-4-14 20:29:44

还没学C++，对程序不了解，但也支持LZ，以后可以学习下！

作者: AlphaCB 时间: 2010-4-14 21:01:12

我愿意出10分之1的力

作者: mengfl 时间: 2010-4-14 21:02:37

这样的事是一定要顶的。。

作者: 斜月 时间: 2010-4-14 21:28:28

我来十楼，哈哈，支持支持～

作者: yanzi7816 时间: 2010-4-14 21:29:40

我再来支持！！！！鼎力支持

作者: 今夜微凉 时间: 2010-4-14 21:38:40

好吧~~~我是第七个~~~编程的东西~~~只学过C和C++而已~~~现在都忘光了~~~

作者: aubell 时间: 2010-4-14 21:48:38 标题: 回复 12# 的帖子

这个程序正好是老外用C++写的
老外的C++和中国的C++是一样的吧

作者: zbyxzh 时间: 2010-4-14 21:50:36

那我也来支持一下吧！
下下来自己看看先：）我用过C，但是面对C++就有点力不从心了……

Edit:大致瞥了一眼源代码，原作者的注释真是非常详尽啊，呵呵

还有，我真的不是啥高手，您这么说我实在是不好意思啊（×＾＿＾×）

[ 本帖最后由 zbyxzh 于 2010-4-17 14:42 编辑 ]

作者: aubell 时间: 2010-4-14 21:56:53

感谢LS！
LS是汉化CubeExplorer5.0的高手，令蓬帖生辉！

作者: dangerxxxx 时间: 2010-4-14 21:59:13

是吗？楼主加油啊！

作者: aubell 时间: 2010-4-14 22:04:05

谢谢支持！我会努力的。

作者: 铯_猪哥恐鸣 时间: 2010-4-14 22:10:27

顶楼主，话说其实那段代码我分析是分析过了，不过没太在意细节和初始化方面，期待楼主的成果。

作者: r_517 时间: 2010-4-14 22:13:15

count me in

[ 本帖最后由 r_517 于 2010-4-14 22:14 编辑 ]

作者: aubell 时间: 2010-4-14 22:17:30

好啊，最难的地方就要仰仗版主了，就是那个IDA*的搜索。

谢谢版主支持，版主就不count了，count LS。

[ 本帖最后由 aubell 于 2010-4-14 22:19 编辑 ]

作者: 真的是个游客 时间: 2010-4-14 22:19:08

怎么生成了那么多临时文件？

作者: 铯_猪哥恐鸣 时间: 2010-4-14 22:20:52

回楼主，我手机不太方便发大篇幅的内容，有什么需要单独交流的可以发我邮箱：chens09@mails.tsinghua.edu.cn

作者: aubell 时间: 2010-4-14 22:25:52 标题: 回复 22# 的帖子

收到，已存下。等分析到最难的地方，一定发邮件。

作者: 真的是个游客 时间: 2010-4-14 22:41:16

iostream.h在哪里？怎么在vs2005中没有。

作者: yq_118 时间: 2010-4-14 23:27:11

原帖由 真的是个游客 于 2010-4-14 22:41 发表 iostream.h在哪里？怎么在vs2005中没有。

iostream.h是c++标准出来以前的头文件，可以改成

#include<iostream>
using namespace std;

作者: yq_118 时间: 2010-4-14 23:31:38

楼主加油！
这些代码可能比较老了，很多不符合标准的。
估计VC6上面能编译。
楼主方便的话可以改一下。

作者: ggglgq 时间: 2010-4-15 01:08:28

　　

支持！楼主的相关主题也移到这里了，以方便大家查阅和学习。

如果 ★ 程序下载 ★ 还有其它与本版相关的主题需要移动，请大家告知，谢谢。
　　
　　
　　

作者: aubell 时间: 2010-4-15 11:36:07

回复 26# 的帖子
啊，这个也out了。
在VC6下可以编译。
我用的还是out已久的VC6，
我对C++的标准不熟悉，更加不熟悉.NET下的各种东东，
就不改动原始代码了。

作者: aubell 时间: 2010-4-15 11:38:01 标题: 回复 27# 的帖子

感谢g版主的辛勤工作。

作者: aubell 时间: 2010-4-15 17:12:36 标题: 回复 21# 的帖子

生成的不是“临时”文件，是“永久”不再改变的文件，
存着状态转移表和剪枝表，下次运行的时候直接调入内存。
只在第一次运行的时候生成。

[ 本帖最后由 aubell 于 2010-4-15 23:41 编辑 ]

作者: aubell 时间: 2010-4-15 19:53:12

7.cubepars.cpp
  就是CubeParser,处理命令行的。
  从命令行接受输入，稍作错误检查，填写一个贴纸层魔方。
  写这段程序需要耐心。逻辑上很简单。
  每个参数对应一个面，整面整面的填写就可以了。

8.cube.cpp
  这个是方块水平的魔方。每块的排列和方向是分开存储的。是可以转动的魔方。
  贴纸魔方在检查着色后，就会填写一个方块魔方。
  文件中定义了各种转动方法，以及求一个简单操作的逆操作，求一个面的对面等。
  同时，这个类是KociembaCube的基类。

9.KociembaCube
  这个大概是最重要的一种Cube了。也就是“坐标水平的魔方”，在“方块水平”，使用
  四个数组存储角排列、角方向、棱排列、棱方向，在“坐标水平”将使用六个整数来代
  替魔方的状态。

在第一步骤中，用3个整数表示魔方状态：棱的翻转状态、角的方向、E层棱在魔方中的位置

  因为第一步骤要还原这些。
  棱的翻转直接用2进制整数，角的方向用3进制整数，

  E层棱的位置表示有两种不同实现方式，一种是把选择方式同整数之间对应，
实现起来也是用专门的算法，注释的很详细；令一种就直接在一个12位
整数上mark一下；编译的时候可以选择用何种方式。
无论哪种方式，要确保组合方式同整数的一一对应。
这一部分似乎应该分离到combinat中，因为这个才是真正的组合。

  数量：只记录7个角的方向和11个棱的方向。因为最后的一个“被决定”的。
  3的7次方2187；2的11次方2048；12选4为495。

  在第二个步骤中，也用三个整数来表示：
  八个角的排列，八个非E层棱的排列，四个E层棱的排列。

  排列同整数的对应就用combinat中的方式。
  数量：8个角的全排列为40320，八个非E层棱的排列也如此40320，
      4个E层棱的排列24
  以上六个数字都不大，但全乘起来正好是魔方状态数的两倍。

  因为有恰好一半的状态不能达到，孤Parity。
通过两步分治，每个步骤都减轻了负担。

[ 本帖最后由 aubell 于 2010-4-17 21:55 编辑 ]

作者: aubell 时间: 2010-4-15 19:54:27

再重写这个程序的时候，会把以下模块分离出来：
3进制数同数组的转换
2机制数同数组的转换
以上两个合并起来

整数同排列的转换
整数同组合的转换
以上两个放在一起，是排列组合相关内容
已经有成熟的完美的算法，不用再自己设计了

以上是关于魔方状态数组与整数之间的转换，使用频率并不高
只在生成表的时候用一次
在每次搜索之前用一次
都是程序外围的非关键部分，效率高下与否不重要，
随便怎么设计都可以。

10.表的生成 movetabl.cpp 和 pruningt.cpp
这里的表，按照类型可以分两类：状态转移表和剪枝表
按照用途也可分两类：第一步骤的表和第二步骤的表

第一步骤的表
Flip.mtp 棱的方向状态转移表
Twist.mtp 角的方向状态转移表
Choice.mtb E层棱的位置选择状态转移表

FlipChce.ptb Flip和Choice的合并剪枝表
TwstFlip.ptb Twist和Flip合并的剪枝表
TwstChce.ptb Twist和Choice合并的剪枝表

第二步骤的表
CrnrPerm.mtb 角的排列状态转移表
EdgePerm.mtb 非E层棱的排列状态转移表
SlicePerm.mtb E层棱的排列状态转移表

CrnrSlic.ptb CrnrPerm和SlicePerm合并的剪枝表
EdgeSlic.ptb EdgePerm和SlicePerm合并的剪枝表

可以看到，每个步骤三个状态转移表。
两两合并，成三个剪枝表。
但第二个步骤，由于CornerPerm的表和EdgePerm的表乘起来太
大了，所以没有合并成剪枝表。
剪枝表的存在也是为了提高搜索的速度。

生成表的过程

状态转移表的生成
由于整数对应着魔方的状态（twist,flip,choice,perm等），
所以依次取这些整数，作为“老状态”，为每一个“老状态”分别作
18种（12种）基本操作，生成“新状态”，表存储：
Table[老状态][操作]=新状态
表查询到达状态=Table[出发状态][操作]；

分支表的生成
分支表是由两个状态转移表合并的
TB[表1中的状态][表2中状态]=还原态到达这个状态需要的步长
两个状态整数被合并了成一个整数，索引的时候用一个数字乘
表的宽度，再加另一个状态。

合并的状态是既满足表1的状态，也满足表2的状态。

存储的是步长，生成的时候采用的是多次扫描，为一层层的生成。
从初始态开始，一层一层向下扩展。

先取分支表的索引，分解成两个状态表中的状态，让这两个状态在
同一个操作的加工下，生成两个新状态，再把两个新状态合并成分支
表的索引。这个索引在第几层扫描的时候遇到，深度就填几。

以上是moveTable和pruningTable的生成过程。
在对应的文件中定义。

生成表的过程因为是只工作一次，所以，效率不高也没有关系。也可分离模块，
成为基础支持，表的生成，表的应用。

生成的数据是为了配合高效率搜索的，IDA*的搜索到底是怎样使用这种表的呢?

[ 本帖最后由 aubell 于 2010-4-16 18:46 编辑 ]

作者: aubell 时间: 2010-4-15 19:55:34

就要开始分析最关键的代码了，这里遗留了几个小问题：
1.排列、组合同整数的对应，那种经典算法工作原理是怎样的；
要学习算法--生成排列、生成组合。
2.验证Parity 的那段朴素而神奇的代码为什么有效。

开始之前，先复习一下深度优先搜索和广度优先搜索。
因为IDA*是改进过的A*搜索，叫做“依赖循环子的A*搜索”。
A*搜索使用的广度优先的控制结构，由于加入对深度的估计，所以又像深度优先。
所以从本质上讲，应该算是深度优先的算法，但与传统的深度优先不同：
如果认为某一支深度会太深，就不去扩展那一支了。

搜索的过程中加入了估值函数，估计当前状态还需要多少“消耗”可到达目标状态。

... ...

[ 本帖最后由 aubell 于 2010-4-18 20:14 编辑 ]

作者: aubell 时间: 2010-4-15 19:57:02

再次认识一下与那些表相关的文件，发现它们的构造函数真的太繁杂了，内部结构也不尽合理，
把一个cube放在管理表的类里作为私有成员，也是不太讲究的。
这些表一旦生成，就不再改写，这些类的构造函数没有必要用魔方状态做参数，
长长的初始化列表，原来是混淆视听的。

那些生成表的过程基本就没有用了。
只在搜索开始的时候，提示一下起点和终点。

再重写的时候，用c，不再用c++了。
c++花俏的东西太多了。

从本质上讲，只有solver和这些表重要。
这些表是数据结构，solver是算法，两个合在一起是程序。

除了solver和表，其它部分所做的工作就是“魔方状态与整数的转换”，或者说叫做
“如何用六个整数表示魔方的状态”。

而这个solver却是我所读不懂的

加油。

[ 本帖最后由 aubell 于 2010-4-17 21:54 编辑 ]

作者: aubell 时间: 2010-4-15 19:58:41

solver.cpp

就剩下这一句，没有理解了。

else{
if (totalCost < newThreshold1)
newThreshold1 = totalCost;
}

没有理解这一句，就意味着没有理解IDA*。

只好暂时先把这个当做一种搜索用“框架”结构，以后写程序照着用就是了。
铯解释过了，我暂时还是没有明白。

整个搜索的流程是这样的：
先开始第一阶段的搜索
如果找到了第一阶段的解，就开始第二阶段的搜索。
第一阶段的搜索并不停止，深度渐渐加深，
第二阶段跟随着，如发现比以前过程中的解还要短，就输出；
如果发现更长的解，不输出。

第一阶段搜索过程中，到达一定的深度，如果没有发现解，
就不向下搜了。但是额外做一件事情：
告诉下一次来搜的时候，要到达什么样的程度。

[ 本帖最后由 aubell 于 2010-4-18 22:19 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-4-15 20:59:38

回楼主，move table是转动表，prun table是剪枝表。我先说下前者的用处。
对于魔方在计算机中的储存，楼主可以看到，在声明类的时候已经有两种方式，但如果楼主细心看会发现，在搜索的过程中为了提高效率，程序必然会舍弃用类来表达魔方，楼主应该可以看到一个递归的搜索程序，他关于魔方信息的参数只有3个。其中每个参数分别表示了魔方的部分信息，比如色向等。然后很显然在搜索的时候不能再把这些信息转换为魔方开执行转动，那怎么办呢？就使用打表的方法，把每个状态经过每种转动后的相应状态储存在内存中直接查找即可。而这表，就是move table，也就是mtb文件。这个想法在我二阶的论文中也有提到。
而关于prun table，它就涉及到了IDA*的核心，一下还很难讲清。

作者: aubell 时间: 2010-4-15 21:33:21 标题: 回复 36# 的帖子

多谢铯的指点。我再仔细看看。
我准备用3个月的时间消化这个程序

[ 本帖最后由 aubell 于 2010-4-15 23:47 编辑 ]

作者: superflip 时间: 2010-4-15 22:48:13

来晚了，lz加油！

我看过ce的简易实现版，貌似确实很“简易”，不知这个kcube什么来头，有什么特殊地方吗？

作者: aubell 时间: 2010-4-15 23:45:14 标题: 回复 38# 的帖子

没有特殊来头，好像48种同态都没有处理，也没有多方向搜索。
也算简易版吧。就是注解的详细，相对可能好懂点。

据说CubeTwister里的开解方法是参照这个程序的。

作者: superflip 时间: 2010-4-16 00:19:59 标题: 回复 39# 的帖子

这个，我是觉得没有比CE的帮助更好的注释了~

ps：48同态在2-phase算法体现为：16同态 * 3 搜索方向

作者: 铯_猪哥恐鸣 时间: 2010-4-16 08:40:10

楼上说得对，不过其实看程序也能看到一些东西，比如各种算法的具体快速实现。

作者: aubell 时间: 2010-4-16 19:04:46 标题: 回复 5# 的帖子

特别感谢superacid的加分支持。

作者: 魏森 时间: 2010-4-16 19:07:35

看不懂啊，，楼主可以解释一下吗？？？？？？

作者: aubell 时间: 2010-4-16 19:49:42 标题: 回复 43# 的帖子

哪一段？我尝试解释一下。

作者: aubell 时间: 2010-4-16 19:53:16 标题: 回复 40# 的帖子

16同态？！我再回头看看CubeExplorer的帮助，学习一下。
Bye the way，研究同态，除了可以减少存储空间，还有什么作用呢？
能加快搜索吗？如果实现的不好，会不会减慢搜索？

[ 本帖最后由 aubell 于 2010-4-16 21:46 编辑 ]

作者: aubell 时间: 2010-4-17 00:16:11

cube_master老大亲自加分了，荣耀！

作者: aubell 时间: 2010-4-18 21:09:21 标题: 回复 43# 的帖子

我也有看不懂的地方，高手指点了我，我还没有完全懂！
等我再反复的读源码。

作者: aubell 时间: 2010-4-18 22:28:25

分析工作大致结束了，现在要一个一个解决遗留问题。
准备也动手写一遍。
用c，不用c++。
48同态的将来再说。

作者: aubell 时间: 2010-4-18 22:37:03 标题: 自顶向下的分析结束了，现在要自底向上实现了。

准备重新组合一下模块，再写一遍，用C语言。
每天写一点。
如果代码太难看了，有人指正。

作者: mk^_^ 时间: 2010-4-18 23:12:28

LZ很猛我现在学C学得想吐..

作者: beijiaoff 时间: 2010-4-18 23:54:15

太牛了。。。这还非专业呢？！。。。。

作者: yq_118 时间: 2010-4-19 00:07:27

其实我之前写了一个全排列的算法，可以建立k阶全排列与整数0~k!-1的一一对应，并且按字典排序法对应的。现在还差一个从序数直接判断奇偶性的函数。

算法思路如下：
k阶全排列的集合 ~ Z(k)*Z(k-1)*...*Z(1) ~ {0,1,...,k!-1}

其中Z(k)={0,1,...k-1} *表示笛卡尔积。

附件: 全排列.zip (2010-4-19 00:07:27, 4.53 KB) / 下载次数 13
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTM4Njd8NTBkNDg2YTN8MTc0OTQ3OTYwOHwwfDA%3D

作者: yq_118 时间: 2010-4-19 00:18:50 标题: 回复 5# 的帖子

为什么排列中，元素向后两两比较的结果可以用来计算是否有Parity?

其实高等代数里面的排列和置换群里的置换本质是一样的。
排列的逆序数的奇偶性就是对应置换的奇偶性。

具体证明高代书上面有。

作者: 铯_猪哥恐鸣 时间: 2010-4-19 00:35:19

回楼上。。其实魔方里的奇偶性就应该用这个定义。。。

作者: yq_118 时间: 2010-4-19 00:39:09

原帖由 铯_猪哥恐鸣 于 2010-4-19 00:35 发表回楼上。。其实魔方里的奇偶性就应该用这个定义。。。

你说的是哪个啊？

作者: aubell 时间: 2010-4-19 18:00:57 标题: 回复 53# 的帖子

多谢yq_118提供的程序和给出的解释！

作者: superflip 时间: 2010-4-19 20:07:18 标题: 回复 45# 的帖子

太专业了，标题得改~

同态应该是空间上的考虑吧，单个节点的时间效率会降低，好像版主一直想在这方面做文章，不知进展如何。

期待lz做一个3d版本，速度更快的CE!

作者: aubell 时间: 2010-4-19 21:53:28 标题: 回复 57# 的帖子

真的不专业，因为就连生成排列的算法都要查资料。

立体有可能，更快却不太可能，CubeExplorer真是一座高峰。

作者: dangerxxxx 时间: 2010-4-20 13:24:48

确实看不懂

作者: 美景 时间: 2010-4-20 18:49:30

额我的天那！一个头两个大！！

作者: cyz 时间: 2010-4-21 18:58:33

也就是说这个事一个软件？那就完全不懂了

作者: aubell 时间: 2010-4-21 23:19:02

已经在编程实践了，实践的时候发现一些细节问题，有关于魔方的，
也有关于程序设计的，提醒自己要注意：

1. 定义基本操作是从0开始还是从1开始，结果表明，从0开始更好；
  从1开始容易写错；也许用enum更好；

2.表中存储6种操作还是12种操作，还是18种操作；
  涉及到空间的关系，以及要用何种方式计数步数，以及对速度的要求；
  18*18也只意味着分支表是6*6的 9 倍大小，可以接受，就用18种；
  存储顺序以方便操作为宜；

3.pack二进制、三进制的时候，要注意都用同一种次序；高低位置不要弄反了；
  这一次写的程序同以前的程序反掉了，测试起来也很麻烦；

4.一切的差异是由于次序的差异造成的。

作者: aubell 时间: 2010-4-21 23:25:29

5. 关于编程：开始编程，不要考虑太多，考虑太多，反而容易引起混乱。
程序也是慢慢长大的，不是一下自就拥有成熟的体型。

作者: oyyq99999 时间: 2010-4-26 11:27:41

我也来支持一个，其实我是想写个手机上用的优化解程序

作者: oyyq99999 时间: 2010-4-26 11:38:51

另外补充一点，IDA*算法是A*算法的一种（迭代加深A*算法），属于启发式搜索算法，人工智能基本算法之一。

[ 本帖最后由 oyyq99999 于 2010-4-26 11:40 编辑 ]

作者: aubell 时间: 2010-4-28 23:19:36

非常感谢狼的支持！
感谢大家的支持。

作者: aubell 时间: 2010-4-28 23:26:32 标题: 这一层发重写的代码了

基本按照原思路重写了，用c语言。
就IDA*的框架没有改动，因为不会改

效率没有提高，文件数目有减少，应该好读些了。
如果发现错误，欢迎指正。

暂时叫 ya2phase
( yet another 2-phase的意思 )
这个名字最有普遍性，谁的程序都可以这样叫。

这一层帖的代码由于有较多编译警告和错误，已经删除。
帖在后面。

教训：
编译时要开启警告，W3。

过多依赖编译器检查，也不是好习惯。

[ 本帖最后由 aubell 于 2010-4-29 12:48 编辑 ]

作者: yq_118 时间: 2010-4-28 23:46:10

先下载了，等一下编译，
用VS命令行编译了，怎么一运行就崩溃啊？

[ 本帖最后由 yq_118 于 2010-4-28 23:54 编辑 ]

作者: aubell 时间: 2010-4-29 00:07:58

LS，真的有这么惨吗？是按照“说明”的顺序运行的吗？
因为主程序省略了错误检查，输入的顺序要按照mike的顺序。
sample.bat给出的是一个"cube in cube"图案。

[ 本帖最后由 aubell 于 2010-4-29 00:13 编辑 ]

作者: yq_118 时间: 2010-4-29 00:20:04

1>e:\projects\create_table\cube.c(161) : warning C4013: “strcpy”未定义；假设外部返回 int
1>e:\projects\create_table\cube.c(172) : warning C4013: “strcmp”未定义；假设外部返回 int

cube.c里面是不是没有包含string.h

作者: oyyq99999 时间: 2010-4-29 01:07:42

看的崩溃了…好多东西

作者: yq_118 时间: 2010-4-29 01:16:30

终于好了。

外部引用的函数最好声明一下，有两个close()改成了fclose()才通过的，好多变量声明了没用。

明天再慢慢研究。

附件: ya2phase.zip (2010-4-29 01:16:30, 14.08 KB) / 下载次数 22
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTU0MTd8MWQ5MTc5YTN8MTc0OTQ3OTYwOHwwfDA%3D

作者: aubell 时间: 2010-4-29 10:07:01

感谢告知错误，这就改了。
还有些不明白的地方，fflush 和 fclose 好像不能工作？

[ 本帖最后由 aubell 于 2010-4-29 12:02 编辑 ]

附件: ya2phase.rar (2010-4-29 11:32:50, 10.74 KB) / 下载次数 28
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTU0MjJ8Y2ZjZWNlMDF8MTc0OTQ3OTYwOHwwfDA%3D

作者: aubell 时间: 2010-4-29 12:18:14

文件读写真是个头痛的问题。
贴个不用读写文件的。
因为编译的exe比源码体积还小，所以就不贴源码了。

[ 本帖最后由 aubell 于 2011-4-5 11:43 编辑 ]

附件: ya2phase.rar (2011-4-5 11:43:07, 3.66 KB) / 下载次数 8
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTM3ODQ2fDY3MWRiODI4fDE3NDk0Nzk2MDh8MHww

作者: 魔将 时间: 2010-4-29 12:20:02

又不懂，又没电脑…帮顶吧…

作者: aubell 时间: 2010-4-29 12:32:12 标题: 回复 72# 的帖子

辛苦了，呵呵！谢谢！

作者: yq_118 时间: 2010-4-29 12:50:30

fclose()前面j加上fflush()就出问题了。不加就OK。

作者: aubell 时间: 2010-4-29 12:59:40 标题: 回复 77# 的帖子

可我的电脑上，不加 fflush ，一样运行错误。
只要在write_table里面用 fclose，运行就出错，不知道为什么。
不用 fclose ，反倒可以顺利的运行。

作者: aubell 时间: 2010-4-29 19:31:19

用gcc编译的，加了fflush以及fclose，都可以正常运行。
用cl编译的，加了fclose就不能运行create_table.exe了。
估计要么是编译选项设置的不对，可能跟系统的线程有关？
导致运行时不是严格按照先后次序？

作者: oyyq99999 时间: 2010-4-30 01:39:11

fflush干嘛用的…

作者: oyyq99999 时间: 2010-4-30 01:40:24

话说我用VC写一个mfc的程序，加了两个文件就悲剧了…

作者: PKUSMSBQ 时间: 2010-4-30 10:22:47 标题: 回复 81# 的帖子

狼加油，我不想再玩自己写的囧游戏了

作者: aubell 时间: 2010-4-30 11:43:23

fflush据说是可以强迫系统立即写文件，不知道是否这样。

作者: aubell 时间: 2010-4-30 11:44:41 标题: 回复 81# 的帖子

狼遇到什么样的悲剧？

作者: oyyq99999 时间: 2010-4-30 22:05:17 标题: 回复 84# 的帖子

编译时说unexpected end of file

作者: oyyq99999 时间: 2010-4-30 22:06:00 标题: 回复 83# 的帖子

印象中好像是这样的，不记得了

作者: aubell 时间: 2010-5-1 15:35:47

这个貌似同头文件的包含次序有关系，VC下的常见错误。
以下内容是Copy来的：

VC6中的解决方法：
菜单--〉项目--〉设置...，出现“项目设置”对话框，左边展开项目，在“源文件”中找到出错的文件，然后在右边选择“C/C++”属性页，在Category下拉框中选择“Precompiled Headers”，然后在下面选择“Not using precompiled headers”，重新编译一般就没问题了。

作者: aubell 时间: 2010-5-1 15:51:00

话说这么小的程序，还要动用VC6的IDE环境吗？
用notepad++就好了。
感觉再用 .NET 下的VC编译环境，就像用炮轰小鸟了。

我已经out很久了，还没用上 .NET，也还没学习Java。准备改投gcc 的怀抱了。
他们说：.NET和Java是一个金碧辉煌的坑。我还没勇气跳下去。
用免费的，但不是盗版的gcc，心安一点。

自己写的代码也贴出来了，分析工作结束了。
最关键一行是直接Copy的，那一行还要细细品味。
整个程序，就那一行代码最关键。

感谢祖国。
感谢大家的支持。感谢 GNU的gcc ，感谢Notepad++，感谢 LarryWall 的Perl。
感谢无私的人们与我们分享智慧的果实。

作者: oyyq99999 时间: 2010-5-1 19:08:51

有个问题，试试 R L U2 R' L' F 这个打乱，最后解出来的不是最短

作者: aubell 时间: 2010-5-2 12:28:10

回楼上：
if (depth >= min_solution_length-1)
return OPTIMUM_FOUND;
这一句
把-1去掉就有了。

作者: oyyq99999 时间: 2010-5-2 21:30:18 标题: 回楼上

把-1去掉不行，我后来试的另一个打乱出现了两个16步解，而且第二个是在threshold=15的时候第一阶段16步，第二阶段0步

作者: aubell 时间: 2011-2-6 13:35:01 标题: 回复 91# 的帖子

伪码是这样的：

maxLength=9999
function Kociemba ( position p)
for depth d from 0 to maxLength
Phase1search( p; d )
endfor
endfunction
function Phase1search( position p; depth d )
if d=0 then
if subgoal reached and last move was a quarter turn of R, L, F, or B then
Phase2start( p )
endif
elseif d>0 then
if prune1[p]<=d then
for each available move m
Phase1search( result of m applied to p; d-1 )
endfor
endif
endif
endfunction
function Phase2start ( position p)
for depth d from 0 to maxLength - currentDepth
Phase2search( p; d )
endfor
endfunction
function Phase2search( position p; depth d )
if d=0 then
if solved then
Found a solution!
maxLength = currentDepth-1
endif
elseif d>0 then
if prune2[p]<=d then
for each available move m
Phase2search( result of m applied to p; d-1 )
endfor
endif
endif
endfunction

复制代码

不是去掉-1。我想我要慢慢理解这个2-phase。

作者: lovelesszhou 时间: 2011-2-6 13:38:26

支持一下，虽然看不懂。。。

作者: 锋魔方 时间: 2018-8-17 16:30:09

感谢楼主。在8年前就研究了。我这小小辈学习呢。

不过现在我用VS2017编译是出好多错误的，

作者: 锋魔方 时间: 2018-8-17 16:31:37

支持支持楼主呢

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)