[注意] 两阶段搜索算法

roundy

中文版本: 两阶段搜索算法 ( 翻译by Roundy,呵呵,乱译.) (如果您在利用本译文研究时导致您的脑子或者您的魔方或者计算机等损坏,本人概不负责) 下面的介绍尝试给你一个关于这个算法基本的概念. (3阶)魔方的六个面我们分别叫U(上),D(下),R(右),L(左),F(前) 和B(后). U的意思就是把'上'面顺时针旋转90度.而U2的意思是把'上'面顺时针旋转180度.U'的意思是把'上'面逆时针旋转90度. 一个移动序列如 U D R' D2 ,我们称之为一个'步法'. 如果你在拧魔方的时候不使用R, R', L, L', F, F', B和B',那么会生成一个状态子集.这个子集我们用G1=<U,D,R2,L2,F2,B2>表示.在这个子集里面,角块和边块的方向是不会改变的(这点在盲拧中我们也可以体会到,译者注).那就是说,对于一个块(边块或角块)而言,他的方向是不会改变的.而UD间夹心的那四块边块仍然会待在UD间.(那么自然,U/D面的边角块仍然会待在U/D面) 在第1阶段的搜索中,本算法会查找能把一个打乱的魔方变成G1状态的步法.那就是说,做完该步后,整个魔方边/角块方向都被纠正.UD间夹心的那四块边块被运到UD间(那么自然,U/D面的边角块会待在U/D面).在这个抽象的空间里,移动魔方一步会把代表魔方状态的三位组(x,y,z)变成(x',y',z'),所有G1状态的魔方都拥有相同的三位组(x0,y0,z0).而这就是第1阶段搜索的目标. 为了达到这个目标,本程序使用了一种正在研究中的叫做 下限启发式迭代深度A星算法,缩写为IDA*(晕,不知道怎么翻译好,但大概知道这种算法的优点是省内存).在 Cube Explorer 2中,它会给出需求解的魔方确切的达到G1状态的最少步数.这种启发是的算法可以在产生解法的时候提前剪枝,这让你不需要等待一段非常非常长的时间来等结果.这种启发式的算法 h1使用的是基于内存的查表方法,最多允许提前12步做出判断剪枝. 在第2阶段搜索中,本算法使用G1步法(U,D,R2,L2,F2,B2)来复原魔方.实际上就是复原 8个角块,U/D面的8个边块和UD面夹心的那四块的位置.启发式函数 h2(a,b,c) 只对复原六面的步法长度内的情况做出评估,因为G1子集里面的情况实在太多了. 本算法不会在找到上面的解法后停止,而是会继续的在第一阶段的结果基础上继续展开第二阶段的搜索.举一个例子,如果上面的解法找到第1阶段需要10步,第2阶段需要12步,但后面搜索的结果可能是第1阶段11步,而第2阶段变成了5步.第1阶段的步法长度增加了,但第2阶段的步法减少了.如果第2阶段的步法长度减少到0.那么这个解法是优化完毕的,算法结束. 当前的两阶段搜索算法并不能在所有的情况下都找到最优解,在这种情况下我们必须倒回头,继续做一次2阶段搜索.这会增加相当多大的时间.如果你确实需要优化一些情况,你可以使用' 优化'(Optimal)选项. 最后举个例子让大家体会上面所说的内容.用步法D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2打乱一个已复原六面的魔方,然后使用cube explorer求出解法U2 R2 F U' B D2 L' U2 D2 R2 F' L U' B2 U' B2 L2 F2 D2 .我们可以看到,整个解法可以分为两步 (U2 R2 F U' B D2 L' U2 D2 R2 F' L)*(U' B2 L2 F2 D2),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.

中英对照版本: The Two-Phase-Algorithm (Herbert Kociemba) (http://home.t-online.de/home/kociemba/homex.htm) 两阶段搜索算法 ( 翻译by Roundy,呵呵,乱译.) (如果您在利用本译文研究时导致您的脑子或者您的魔方或者计算机等损坏,本人概不负责)

The following description is intended to give you a basic idea of how the algorithm works. 下面的介绍尝试给你一个关于这个算法基本的概念.

The 6 different faces of the Cube are called U(p), D(own), R(ight), L(eft), F(ront) and B(ack). While U denotes an Up Face quarter turn of 90 degrees clockwise, U2 denotes a 180 degrees turn and U' denotes a quarter turn of 90 degrees counter-clockwise. A sequence like U D R' D2 of Cube moves is called a maneuver. (3阶)魔方的六个面我们分别叫U(上),D(下),R(右),L(左),F(前) 和B(后). U的意思就是把'上'面顺时针旋转90度.而U2的意思是把'上'面顺时针旋转180度.U'的意思是把'上'面逆时针旋转90度. 一个移动序列如 U D R' D2 ,我们称之为一个'步法'.

If you turn the faces of a solved cube and do not use the moves R, R', L, L', F, F', B and B' you will only generate a subset of all possible cubes. This subset is denoted by G1 = <U,D,R2,L2,F2,B2>. In this subset, the orientations of the corners and edges cannot be changed. That is, the orientation of an edge or corner at a certain location is always the same. And the four edges in the UD-slice (between the U-face and D-face) stay isolated in that slice. 如果你在拧魔方的时候不使用R, R', L, L', F, F', B和B',那么会生成一个状态子集.这个子集我们用G1=<U,D,R2,L2,F2,B2>表示.在这个子集里面,角块和边块的方向是不会改变的(这点在盲拧中我们也可以体会到,译者注).那就是说,对于一个块(边块或角块)而言,他的方向是不会改变的.而UD间夹心的那四块边块仍然会待在UD间.(那么自然,U/D面的边角块仍然会待在U/D面) In phase 1, the algorithm looks for maneuvers which will transform a scrambled cube to G1. That is, the orientations of corners and edges have to be constrained and the edges of the UD-slice have to be transferred into that slice. In this abstract space, a move just transforms a triple (x,y,z) into another triple (x',y',z'). All cubes of G1 have the same triple (x0,y0,z0) and this is the goal state of phase 1. 在第1阶段的搜索中,本算法会查找能把一个打乱的魔方变成G1状态的步法.那就是说,做完该步后,整个魔方边/角块方向都被纠正.UD间夹心的那四块边块被运到UD间(那么自然,U/D面的边角块会待在U/D面).在这个抽象的空间里,移动魔方一步会把代表魔方状态的三位组(x,y,z)变成(x',y',z'),所有G1状态的魔方都拥有相同的三位组(x0,y0,z0).而这就是第1阶段搜索的目标.

To find this goal state the program uses a search algorithm which, in terms of the current research, is called iterative deepening A* with a lowerbound heuristic function (IDA*). In the case of the Cube, this means that it iterates through all maneuvers of increasing length. The heuristic function h1(x,y,z) estimates for each cube state (x,y,z) the number of moves that are necessary to reach the goal state. It is essential that the function never overestimates this number. In Cube Explorer 2, it gives the exact number of moves which are necessary to reach the goal state in Phase 1. The heuristic allows pruning while generating the maneuvers, which is essential if you do not want to wait a very, very long time before the goal state is reached. The heuristic function h1 is a memory based lookup table and allows pruning up to 12 moves in advance. 为了达到这个目标,本程序使用了一种正在研究中的叫做 下限启发式迭代深度A星算法,缩写为IDA*(晕,不知道怎么翻译好,但大概知道这种算法的优点是省内存).在 Cube Explorer 2中,它会给出需求解的魔方确切的达到G1状态的最少步数.这种启发是的算法可以在产生解法的时候提前剪枝,这让你不需要等待一段非常非常长的时间来等结果.这种启发式的算法 h1使用的是基于内存的查表方法,最多允许提前12步做出判断剪枝.

In phase 2 the algorithm restores the cube in the subgroup G1, using only moves of this subgroup. It restores the permutation of the 8 corners, the permutation of the 8 edges of the U-face and D-face and the permutation of the 4 UD-slice edges. The heuristic function h2(a,b,c) only estimates the number of moves that are necessary to reach the goal state, because there are too many different elements in G1. 在第2阶段搜索中,本算法使用G1步法(U,D,R2,L2,F2,B2)来复原魔方.实际上就是复原 8个角块,U/D面的8个边块和UD面夹心的那四块的位置.启发式函数 h2(a,b,c) 只对复原六面的步法长度内的情况做出评估,因为G1子集里面的情况实在太多了.

The algorithm does not stop when a first solution is found but continues to search for shorter solutions by carrying out phase 2 from suboptimal solutions of phase 1. For example, if the first solution has 10 moves in phase 1 followed by 12 moves in phase 2, the second solution could have 11 moves in phase 1 and only 5 moves in phase 2. The length of the phase 1 maneuvers increase and the length of the phase 2 maneuvers decrease. If the phase 2 length reaches zero, the solution is optimal and the algorithm stops. 本算法不会在找到上面的解法后停止,而是会继续的在第一阶段的结果基础上继续展开第二阶段的搜索.举一个例子,如果上面的解法找到第1阶段需要10步,第2阶段需要12步,但后面搜索的结果可能是第1阶段11步,而第2阶段变成了5步.第1阶段的步法长度增加了,但第2阶段的步法减少了.如果第2阶段的步法长度减少到0.那么这个解法是优化完毕的,算法结束.

In the current implementation the Two-Phase-Algorithm does not look for some solutions that are optimal overall, those that must cross into and back out of phase 2. This increases the speed considerably. Use the Optimal Solver, if you want to prove some maneuver to be optimal. 当前的两阶段搜索算法并不能在所有的情况下都找到最优解,在这种情况下我们必须倒回头,继续做一次2阶段搜索.这会增加相当多大的时间.如果你确实需要优化一些情况,你可以使用' 优化'(Optimal)选项.

(译者注:最后举个例子让大家体会上面所说的内容.用步法D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2打乱一个已复原六面的魔方,然后使用cube explorer求出解法U2 R2 F U' B D2 L' U2 D2 R2 F' L U' B2 U' B2 L2 F2 D2 .我们可以看到,整个解法可以分为两步 (U2 R2 F U' B D2 L' U2 D2 R2 F' L)*(U' B2 L2 F2 D2),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.)

[此贴子已经被作者于2005-3-21 1:19:41编辑过]

cube_master

好，虽然未细看，但好东西还是先顶一下

cube_master

来自QQ群的一段话：

(2005-03-20 13:48:02) roundy(811416)
我的一个心愿:能集合魔方吧大集体的力量做一个工具:她有强劲高效的算法引擎,然后有漂亮的渲染3d引擎.可换壳.功能多样,可以帮助大家找最优解.找某个算法的多种解法供自己挑选最适合自己手感的方法.可以做为一个教练训练大家玩魔方.....

可惜我不会编程

希望有能力者都齐来参与

[此贴子已经被作者于2005-8-26 23:38:20编辑过]

大烟头

最后举个例子让大家体会上面所说的内容.用步法D2 F2 L2 B2 U B2 U L' F R2 D2 U2 L D2 B' U F' R2 U2打乱一个已复原六面的魔方,然后使用cube explorer求出解法U2 R2 F U' B D2 L' U2 D2 R2 F' L U' B2 U' B2 L2 F2 D2 .我们可以看到,整个解法可以分为两步 (U2 R2 F U' B D2 L' U2 D2 R2 F' L)*(U' B2 L2 F2 D2),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.

ggglgq

以下是引用cube_master在2005-3-20 14:01:14的发言：

(2005-03-20 13:48:02) roundy(811416) 我的一个心愿:能集合魔方吧大集体的力量做一个工具:她有强劲高效的算法引擎,然后有漂亮的渲染3d引擎.可换壳.功能多样,可以帮助大家找最优解.找某个算法的多种解法供自己挑选最适合自己手感的方法.可以做为一个教练训练大家玩魔方.....

支持，roundy 的心愿也是所有魔友的心愿！

ggglgq

roundy 先生您好：

很长时间未光顾“魔方吧”了，今欣喜地看到 roundy 先生依据 Two-Phase-Algorithm 算法开发出国产的“正六面体三阶魔方”最少步软件，真是可喜可贺呀！我谨在此向 roundy 先生表示衷心地祝贺！

没有太多的时间仔细看和测试，感觉您对 Two-Phase-Algorithm 算法已经融会贯通了， 并且试着用它开发出很棒的三阶魔方最少步软件。下面谈谈我的一些个人看法 （信口胡说， 若有说的不对的地方还望 roundy 先生补充更正）：

1、您的“正六面体三阶魔方”最少步程序很干练，很精巧；

2、程序初始化的库很小，因此在处理步数较少的状态时速度很快；

在国外研究 Two-Phase-Algorithm 算法的人很多，其中研究高效快速的“估价函数” 是重中之重！因为面对“三阶魔方天文数字的状态”蛮算是不行的！尤其对于步数较多的 状态！比如要找“三阶魔方的最远状态”无论任何算法都要先进行“评估优化”！

能够胜任 Two-Phase-Algorithm 算法的人，必然能够掌握和胜任“循环变换算法”。 因为我很忙没太多时间研究算法和编程，因此我把我的“循环变换算法”在论坛上发表以 期待能有像您这样的程序员一起去研究完善，并运用其编程！ “循环变换算法”在“正六面体三阶魔方”运用时如果只考虑旋转 90 度为单步长，而 旋转 180 度为两步长，在此基础上得到正六面体三阶魔方“循环变换”的步数和 [或长度] 为偶数！这一点非常重要：我们就没必要考虑长度为奇数的循环变换，从而简化了编程。 当然，对于旋转 180 度为单步长，“循环变换算法”应该没有太大的问题。不知您对 此持怎样的看法 ？

xinru

没下文啦？？？[em07][em07][em07]

gdkool

好啊

ggglgq

补充 roundy 先生的原创最少步软件：

roundy 先生的原创最少步软件: http://bbs.rbook.net/UploadFile/2006-2/20062288395489694.rar

乌木

我对1楼的一点小议论请见此帖中8、11楼我的跟帖：http://bbs.mf8-china.com/dispbbs.asp?boardid=18&replyid=1997&id=1997&page=1&skin=0&Star=1