魔方吧·中文魔方俱乐部

标题: 【翻译】20步可还原任意状态魔方 [打印本页]
作者: shifujun    时间: 2010-8-10 22:50:36     标题: 【翻译】20步可还原任意状态魔方

原文：www.cube20.org
__________________________________________________

上帝之数是20
http://mf8.com.cn/flash/cube3.swf?&initmove=R\'U2BL\'FU\'BDFUD\'LD2F\'RB\'DF\'U\'B\'UD\'&move=R\'U2BL\'FU\'BDFUD\'LD2F\'RB\'DF\'U\'B\'UD\'

3×3×3魔方的每一个状态都可以在20步以内还原。
通过由Google贡献的大约时长35年的CPU空闲时间，一个研究团队已经根本地（essentially）解决3×3×3魔方的每一个状态，并进一步提出没有状态需要超过20步还原。 每一个状态都用一个有着一连串步骤的算法解决。这用的算法可能用一连串的步骤解决顶层，然后用另一串步骤解决中间的边块，然后是类似的步骤。我们知道很多不同的算法，它们在复杂度和所需步数上有所不同，但是那些可以被人类记忆的方法通常要超过40步。
Superflip,第一个被证明最少需要20步还原的状态。
有人可能猜测上帝用的算法更高效，总是用最少的步骤解决；这被称作"上帝算法"（God's Algorithm）。这个算法在解决最复杂的魔方状态时所用的步数称作"上帝之数"。终于，上帝之数被证明是20了。 从有魔方以来，人们花了15年时间才找到第一个被证明至少需要20步才能还原的状态；在那之后，我们又花了将近15年证明了20步可以解决所有的状态。


上帝之数的历史
到1980年，通过分析小于等于17步的有效不同转动得到的状态数，发现这个数字小于3×3×3魔方的状态数，所以上帝之数的下界被确定为18。由早期的魔方解决方法小册子的算法来看，第一个上帝之数的上界大概在80左右。这个表格统计了随后的成果。

日期下界上界范围摘要和链接
1981年7月185234Morwen Thistlethwaite 证明 52 步足够了。
1992年4月184224Hans Kloosterman把它改善到 42步 。
1992年5月183921Michael Reid 证明 39 步总是足够的。
1992年5月183719Dik Winter 一天之后就把它降低到 37 步 。
1995年1月182911Michael Reid在分析完Kociemba's two-phase algorithm后把上界减少到29 步。
1995年1月20299Michael Reid 证明 ''superflip'' 状态(角块全正确, 棱块全部原地翻转) 需要 20 步。
2005年12月20288Silviu Radu 证明 28 步 总是足够的。
2006年4月20277Silviu Radu 改善他得到的上界到 27 步。
2007年5月20266Dan Kunkle 和 Gene Cooperman 证明 26 步是足够的。
2008年3月20255Tomas Rokicki 把上界减少到 25 步。
2008年4月20233Tomas Rokicki 和 John Welborn 把它减少到只有 23 步。
2008年8月20222Tomas Rokicki 和 John Welborn 把它继续减少到 22 步。
2010年7月20200Morley Davidson, John Dethridge, Herbert Kociemba, 和 Tomas Rokicki 四人证明了上帝之数确切的是20步。
  我们是如何做的我们如何解决全部43,252,003,274,489,856,000种状态的？
分区法
我们将这个大问题化为2,217,093,120个小问题，每个问题由19,508,428,800个不同的状态组成。每个子问题都足够小到可以用一台流行配置的电脑解决，我们分解问题的方法（数学上，运用{U,F2,R2,D,B2,L2}生成的群的陪集(coset)，简单的说就是H的陪集）使得我们可以非常快速的解决每一个集合。
对称性
如果你拿一个混乱的魔方，把它上下颠倒一下，这样你不会把它变得更难还原；它还是需要同样的步数还原。还原这两个状态，你可以只还原其中一个状态，然后把解决方法也上下颠倒一下就可以还原另一个状态了。一个魔方在空间中有24种不同的摆放方法，通过镜像可以得到2种对称状态，所以总共可以减少48倍需要还原的状态。运用类似对称论证和找到一个解决到一个大的"集合覆盖（set cover）"问题的方法，我们能把要解决的集合数从2,217,093,120减少到55,882,296。
好方法和最优方法
随机状态H的陪集
最优化0.362,000,000
20步或更少3,9001,000,000,000
一个最优方法不需要比还原必要的步数多的步数还原。自从发现了一个还原必要步数是20步的状态，我们就不需要用最优方法解决每一个状态了；我们只需要找到一个小于等于20步的方法还原每一个状态。这要简单相当多；左边的表格显示了一个配置较好的台式电脑解决随机状态时的速度。
解决速度，状态数/秒
快速陪集求解程序运用数学技巧和精心编程的结合，我们能在一台台式机上以左边表格里写的速度解决完整的H的陪集，得到最优方法或者小于等于20步的方法。
   大量的电脑最终，我们能将这55,882,296个H的陪集分派到Google的大量的电脑上，并在几个星期内完成计算。Google没有公布它的电脑系统信息，但是这将会花费一台配置较好的台式机(Intel Nehalem, 四核, 2.8GHz) 11亿秒，即35个CPU年，去完成这个计算。
最难的状态是什么？
我们知道有些状态最少需要20步还原已经15年了；我们刚刚证明了没有状态需要更多的步数。 最少步需要20步的状态既罕见又丰富；它们罕见是因为它们只有全部状态的十亿分之一，然而很可能有超过一亿个这样的状态。我们还不能确切的知道它们到底有多少。这张右边的表格给出了每个最小步数所包含的状态数。对于大于等于16步的情况，只能给出一个估值。我们的研究已经确认前面的结果，从0到14，15步的结果是一个新成果。我们希望月内能有另外的研究者独立确认这个结果。
到目前为止我们已经发现了大约2000万个最小步20步的状态。下面的状态曾是我们的程序遇到的最难解决的状态：
http://mf8.com.cn/flash/cube3.swf?&initmove=D2U2F\'RD2BU\'L\'URDL\'FRU\'B\'DF2UF\'&move=FU\'F2D\'BUR\'F\'LD\'R\'U\'LUB\'D2R\'FU2D2
最小步数状态数量
01
118
2243
33,240
443,239
5574,908
67,618,438
7100,803,036
81,332,343,288
917,596,479,795
10232,248,063,316
113,063,288,809,012
1240,374,425,656,248
13531,653,418,284,628
146,989,320,578,825,358
1591,365,146,187,124,313
16大约 1,100,000,000,000,000,000
17大约 12,000,000,000,000,000,000
18大约 29,000,000,000,000,000,000
19大约 1,500,000,000,000,000,000
20大约 300,000,000
联系我们
我们的团队由这些人组成：
Morley Davidson，肯特州立大学的数学家
John Dethridge，Google总部加利福尼亚州山景城的工程师
Herbert Kociemba，德国达姆施塔特的数学老师
Tomas Rokicki，美国加利福尼亚州帕罗奥图市的程序员
我们的Email是：
rokicki@gmail.com
davidson@math.kent.edu


Rubik's Cube是Seven Towns, Ltd的注册商标。
感谢Werner Randelshofer为此页面提供的魔方展示插件。



------------------------------------------------------------------------------------

[ 本帖最后由 shifujun 于 2010-8-11 20:39 编辑 ]
作者: shifujun    时间: 2010-8-10 22:54:10

其实俺昨天晚上就翻译完了，就是没搞定排版的问题。
作者: kattokid    时间: 2010-8-10 22:57:30

好像是不是有人先你一步了？用的是穷举法？

[ 本帖最后由 kattokid 于 2010-8-10 22:58 编辑 ]
作者: shifujun    时间: 2010-8-10 23:03:38

确实是穷举了，48同态算1个，还有我听不懂的集合覆盖，通过这两个手段减少了一部分状态。其余状态都穷举了。
作者: 黑白子    时间: 2010-8-10 23:10:26

妙！两幅图案都是24步。
作者: wyn1992    时间: 2010-8-10 23:13:37

翻译得很好，我算明白一点上帝之数的算法了
作者: shifujun    时间: 2010-8-10 23:13:46

原帖由 黑白子 于 2010-8-10 23:10 发表
妙！两幅图案都是24步。

那个原网页实际只是想展示一下打乱是什么样子的，没想贴出来20步的还原步骤。
作者: xty_90    时间: 2010-8-10 23:43:03

无奈飘过。。。。。。。。。。。
作者: firstjasmines    时间: 2010-8-11 11:07:27

这……很尴尬一不小心抢了你的风头……
讨论两个翻译问题吧：
A History of God's Number，那段第一句：
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions.
这句话，18被确定为上帝之数的下限然后by后面的内容我其实没看懂，“the number of effectively distinct move sequences of 17 or fewer moves”，还有 “there were fewer such sequences than Cube positions”是什么意思。
还有，
Symmetry，那一段中间一句：
There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving
这句话意思我大概看懂了，但是and后面的语法结构我没搞明白。
这两处你是怎么理解的，望指教。
作者: 42752277    时间: 2010-8-11 11:08:35

怎么又变成20了，不是17吗、？？？
作者: shifujun    时间: 2010-8-11 12:19:18

原帖由 firstjasmines 于 2010-8-11 11:07 发表
这……很尴尬一不小心抢了你的风头……
讨论两个翻译问题吧：
A History of God's Number，那段第一句：
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effec ...


那句话的意思是说他们分析了17步能产生的状态数，发现比魔方应有的状态数少，那17步自然不能还原所有状态的魔方了。

我英语也没那么好，语法结构正是弱项。
作者: firstjasmines    时间: 2010-8-12 10:11:19     标题: 回复 11# 的帖子

哦，经过你的指点我明白了这句话的意思。Thank you.
作者: 溪风    时间: 2010-8-12 10:14:43

辛苦啦。还得慢慢理解下。
作者: lanjingling    时间: 2011-5-18 11:36:18

准确地说，应该是“20步以内可以还原任意状态三阶魔方”。
对于不需要20步的，采用多余转法，也许不能刚好凑20步。
作者: quancai    时间: 2011-5-18 11:56:08     标题: 回复 14# 的帖子

“不需要20步的”在“20步以内”！

本贴中有老外对魔方上下方向48“镜像状态”的描述，不知能否唤醒乌木大师内心的良知，改邪归正呢？

详见：http://bbs.mf8-china.com/viewthread.php?tid=12877&extra=page%3D1&page=6

[ 本帖最后由 quancai 于 2011-7-3 11:51 编辑 ]
作者: 丁云龙521    时间: 2011-6-9 21:59:52     标题: 回复 1# 的帖子

此贴值得收藏！谢谢楼主！本人在此学习了啊！
作者: jinxian    时间: 2011-10-26 10:18:38

原帖由 铯_猪哥恐鸣 于 2011-10-12 22:27 发表

三阶上帝之数为20证明的源代码发布
以上引用自http://cubezzz.dyndns.org/drupal/
在这个论坛上可以看到各种神牛的神作。。。鉴定完毕

　　
  
    依我看来，这句话放在这里可能更好些。 呵呵！
　　
　　
作者: jinxian    时间: 2011-10-26 10:22:25

Source Code for Face Turn Metric 20 Proof Released
Submitted by rokicki on Tue, 10/11/2011 - 12:03.
You can find the source code used for the "20" proof at:

http://cube20.org/src/

I spent a fair amount of effort documenting it. Any feedback is
welcomed
　　

   

      以上引用自http://cubezzz.dyndns.org/drupal/
   
      在这个论坛上可以看到各种神牛的神作。
　　
　　
　　
　　
作者: 柳下    时间: 2012-6-17 22:51:13

网上有个软件可以25步以内
作者: TOETOE55    时间: 2012-7-14 15:37:21

穷举…………计算机死啦
作者: 无边际的宇宙    时间: 2013-1-12 15:05:45

作者: snowchou    时间: 2013-1-14 12:28:54

先收藏，改天好好学习一下。
作者: TOETOE55    时间: 2013-2-3 00:09:28

TOETOE55 发表于 2012-7-14 15:37
穷举…………计算机死啦

只能这样吖。。。
作者: 黑白子    时间: 2013-6-14 16:20:31

电脑真的证明了吗？程序不会出错吗？
作者: ggglgq    时间: 2013-9-5 12:56:30

　　
　　
  
    楼上如果有“反证”，请“明示”！  否则 ......   
  
    为人不要“多疑”，而应“多思”。多年来有很多科研人员（包括很多优秀程序员）花费了大量辛血，
  
才把 正六面体三阶魔方 的 上帝之数 从 22 ～23 步直升到 20 步，楼上知道吗？ 这绝不是楼上随便一句
  
“电脑真的证明了吗？程序不会出错吗？”  能怀疑的了的。
  
  
　　
　　
　　
作者: mokona    时间: 2013-9-5 14:47:25

谢谢lz啦！
作者: 黑白子    时间: 2013-9-5 17:00:53

ggglgq 发表于 2013-9-5 12:56
　　
　　
  

1、请版主先介绍一下有关三阶魔方最少步这方面的详细资料，好让我明白其中的道理。
2、“    楼上如果有“反证”，请“明示”！  否则 ......   
  
    为人不要“多疑”，而应“多思”。多年来有很多科研人员（包括很多优秀程序员）花费了大量辛血，
  
才把 正六面体三阶魔方 的 上帝之数 从 22 ～23 步直升到 20 步，楼上知道吗？ 这绝不是楼上随便一句
  
“电脑真的证明了吗？程序不会出错吗？”  能怀疑的了的。”这段话不好，请三思。
3、“否则……”之后的省略号想说什么，直接说出来好了。
4、“多年来有很多科研人员（包括很多优秀程序员）花费了大量辛血，才把 正六面体三阶魔方 的 上帝之数 从 22 ～23 步直升到 20 步”，应该是直降到20步。
5、怀疑是“多思”的结果，不是人云亦云。
6、我为什么有疑问，那是因为计算机并未遍历所有状态，况且也没有复验。
7、怀疑不等于事实，真理不怕检验，实践是检验真理的唯一标准！
作者: ggglgq    时间: 2013-9-5 20:09:39

　　
　　
  
    嗯，“怀疑”起码也得有个“怀疑”的方向吧？！
  
    我想，泛泛地“怀疑”也没有实际意义吧？！ 也就是：“怀疑”不如“行动”，或者“怀疑”不如“实证”。
  
    我想说，希望我们就事论事，不要参杂感情成分。对于 黑白子 的探索精神，我是非常欣赏的，但我更注重
  
“实证”，而非“空口无凭”。
  
    同时 更希望 日后合作愉快！  
   
  
    顺便说一下，我的英语很烂。对于诸如 正六面体三阶魔方 上帝之数 的英文资料也仅仅是能凑合着看，对于
  
里面的术语也不知道怎么翻译为好。有需要这方面资料的，请另找高人。  比如：
  
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html
　　
　　
　　
作者: 黑白子    时间: 2013-9-6 10:09:09

ggglgq 发表于 2013-9-5 20:09
　　
　　
  

在计算机间接证明20步之前，数学家就用群论理论估计出三阶魔方最少步是22步或23步。

没有群论理论，计算机无法间接证明。问题是谁能保证计算机在整个证明过程中不出错？也可能真的没出错，也可能出错了但不影响结果。

相比结果而言，我更关注证明过程！计算机的结果只比群论理论少了2-3步，没什么了不起！很多计算机专家之所以没能解决这一问题，就是因为没有那么强大计算能力的计算机而已，现在，我们不是也没法复验吗？

倒是长期从事这一工作的科学家（包括数学家、程序员和魔方爱好者）更值得人们尊重！

对一个问题出现不同观点产生争论是正常的，以后还可能发生多次！直到问题得到解决。

来到论坛就是来讨论问题的。我们过去、现在合作的就很愉快！今后还是很愉快！像我们这样有话直说比欲言又止好的多！
作者: 黑白子    时间: 2013-9-30 16:49:27

关于最少步有什么新消息吗？
作者: 深圳老钓    时间: 2014-3-3 03:07:37

最小步数        状态数量
0        1
1        18
2        243
3        3,240
4        43,239
5        574,908
6        7,618,438
7        100,803,036
8        1,332,343,288
9        17,596,479,795
10        232,248,063,316
11        3,063,288,809,012
12        40,374,425,656,248
13        531,653,418,284,628
14        6,989,320,578,825,358
15        91,365,146,187,124,313
16        大约 1,100,000,000,000,000,000
17        大约 12,000,000,000,000,000,000
18        大约 29,000,000,000,000,000,000
19        大约 1,500,000,000,000,000,000
20        大约 300,000,000
作者: younkee    时间: 2016-4-1 18:38:39

太强大了，无敌了。。。
作者: qq543450409    时间: 2019-4-10 10:08:21

好厉害的样子，我现在一分钟才能解开一个
作者: PTSD龌龊闵    时间: 2020-3-21 10:03:41

我相信总有一天，WCA上会有人用上帝解法快乐地二速三速三盲三单三脚
作者: 李老豆    时间: 2020-5-16 19:13:51

平均的话应该是15步左右吧，那么最少步WR总有一天会达到这个极限的



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