魔方吧·中文魔方俱乐部

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

计算魔方某些公式的汉化软件(单机、网络版) [复制链接]

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2006-2-26 13:25:06 |显示全部楼层


今把网上常见的几款计算魔方某些公式的工具(如只计算 某些棱 或 某些角 还原的步骤、
最少步数、循环公式等)汉化了,奉献给大家。

固顶到本区,以便大家下载并研究其在最少步数等领域的应用。同时,希望大家把有关汉化
涉及 最少步数 的软件 集中放到这里,便于大家学习交流。

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2006-2-26 13:42:54 |显示全部楼层
正六面体二阶魔方求解工具(汉化版):








      原版-二阶:原版-二阶
  
      汉化-二阶:汉化-二阶
  
  
  
  
  
  

[ 本帖最后由 ggglgq 于 2009-6-18 10:26 编辑 ]
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2006-2-26 14:10:31 |显示全部楼层
正六面体三阶魔方求解工具(汉化版):







   原版-三阶: 原版-三阶  
  
   汉化-三阶: 汉化-三阶     
  
  
  
  
  

[ 本帖最后由 ggglgq 于 2009-6-18 10:29 编辑 ]
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2006-2-26 14:16:45 |显示全部楼层
正六面体三阶魔方的最少步算法:The Two-Phase-Algorithm (Herbert Kociemba 中英对照版本)
感谢 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 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 U' B2 L2 F2 D2),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.)  
  
  
  
  
  

[ 本帖最后由 ggglgq 于 2009-6-18 10:39 编辑 ]
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2006-2-26 14:27:25 |显示全部楼层
正六面体三阶魔方的最少步专用软件
  最新版本下载:到 Cube Explorer 主页 http://kociemba.org/cube.htm  下载
将下面的汉化补丁拷至安装目录覆盖即可。
   感谢 pan528 先生 做的汉化工作, cube410 汉化补丁下载:

   cube410s汉化.rar (285.84 KB, 下载次数: 1006)
  
  
  
  
  
  

[ 本帖最后由 ggglgq 于 2009-6-18 10:39 编辑 ]
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
5125
帖子
1445
精华
9
UID
553
性别

收藏爱好者 论坛建设奖 八年元老

发表于 2006-2-26 14:44:14 |显示全部楼层
好贴呀!!!顶起[em02][em04][em05]
http://shop33625270.taobao.com/
国甲天下,我爱国甲,爱魔方

使用道具 举报

Rank: 8Rank: 8

积分
17978
帖子
16418
精华
9
UID
449
性别

魔方理论探索者 论坛建设奖 爱心大使 十年元老

发表于 2006-2-26 23:38:13 |显示全部楼层

4楼有误吧?4楼最后说:

(译者注:最后举个例子让大家体会上面所说的内容.用步法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),你可以尝试在'*'号的位置停下来看一看整个魔方的状态,加深一下对这个算法的感性认识.)

其中我涂红的部分有误,应该是 U'B2 U'B2 L2 F2 D2 ,即4楼漏了U' B2 两步!




感谢 乌木 先生对 roundy 先生失误的订正,4 楼帖子已经更正! ggglgq 鸣谢


此外,译者的例子这么巧?程序算出的解法正好是打乱的逆步骤?!是否都是这样的?如果是的,那么,吧内以前给出的许多“x月x日题目”,岂非只要把所给的打乱步骤换成逆步骤,就是最少步啦?最多在所给的打乱步子中去掉可能有的、无效的反复步子。

[此贴子已经被ggglgq于2006-2-28 8:58:34编辑过]

使用道具 举报

积分
1090
帖子
64
精华
0
UID
4464
性别
发表于 2006-2-28 09:30:24 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

使用道具 举报

Rank: 8Rank: 8

积分
1742
帖子
145
精华
6
UID
235

十年元老

发表于 2006-3-10 22:13:01 |显示全部楼层
什么宝贝?

使用道具 举报

Rank: 2

积分
201
帖子
1
精华
0
UID
5304
性别
发表于 2006-3-14 11:59:52 |显示全部楼层

我需要,要看看

使用道具 举报

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

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

GMT+8, 2023-2-6 14:03

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部