[转帖]美专家证明任意状态魔方最多只需26步解开

rongduo

美专家证明任意状态魔方最多只需26步解开

http://www.sina.com.cn 2007年06月04日 13:20  科学网

      

       魔方是匈牙利人Erno Rubik于20世纪70年代发明的，它能够产生数十亿种组合状态，是世界上最流行的组合游戏之一。最近，美国计算机科学家对于魔方的一项研究证实，26步足以解开任意状态的魔方，这一结论打破了此前27步的最好历史证明，成为了一项新的纪录。

　　1997年5月，UCLA的计算机科学家Richard Korf表示，任意状态的魔方可以用不超过20步解决。不过，他并不能证实这一观点，此前也没有人能够证实魔方能以少于27步解决。

　　在此次的研究中，美国东北大学的Gene Cooperman教授和研究生Dan Kunkle将数学上群的概念应用于魔方的组合状态，在计算机上进行了模拟研究。他们的成功离不开技术上的支持：作为内存扩展的7G分布式硬盘以及每秒1亿次的超快计算方式。此外，Kunkle表示，此次编写的程序能够进行大量的预先计算(pre-computation)，这大大提高了研究中的计算速度，因此他们最终能够在一秒钟内找到任意魔方状态不超过26步的解决方法。

　　此次研究的意义并不只限于进一步解开了一个谜团。Cooperman表示，魔方是探究和列举问题的“实验田”，许多不同领域的科研人员都有可能用到这一有效的工具。(科学网 任霄鹏/编译）

转自：http://tech.sina.com.cn/d/2007-06-04/13201544076.shtml

ggglgq

&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 呵呵，不用等“明年”，今年就有高人证明正六面体三阶魔方还原步数<BR>&nbsp; <BR>不超过 23 步了！<BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 请大家参考：&nbsp; <A href="http://bbs.mf8-china.com/viewthread.php?tid=9610"><FONT color=blue><STRONG>计算机证明魔方还原步数小于23&nbsp;</STRONG></FONT></A><BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp; <A href="http://bbs.mf8-china.com/viewthread.php?tid=9610">http://bbs.mf8-china.com/viewthread.php?tid=9610</A><BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

geslon

时隔多日，看到这个老帖子，我想说：“美专家证明任意状态魔方最多只需 26 步”，“并没有证明存在 26 步态。”。
这个说法一点也不矛盾。

打个比方就好理解了。我从北京去到地球上任何一个地方，肯定不超过10万公里的路程。但是我没有说存在一个地方，恰好是10万公里。

美国人仅仅证明了26步一定够用。但是也许明年，他们会有更新的发现，25步也是足够的。

乌木

D

乌木

QUOTE:

以下是引用foxmirra在2007-10-21 21:05:41的发言：
26步是个啥子概念哦。。。。。昏迷[em06][em06][em06]

我就我目前的认识大概说说这个问题。

三阶魔方的状态数有约四千亿亿个，任一状态都可以从复原态出发一步、一步……地转得。反之，从除了复原态的任一状态出发，都可以一步、一步……复原。

有一种理论任为这一步、一步……最多为22步，即距离最远的两个状态之间的变化步子为22步。此外，一个态所对应的最远态可以有许多个。也就是说，一个初态，可以有许多个第X代“后代”。

如果某一态和复原态的最短距离为n步（n≤22），但不知道具体哪n步，我们往往用不止n步来复原它，那是没办法的办法，只好走迂回曲折的路线。可以保证成功，但不敢说是最少步数。

即使用某种电脑软件来求得某一复原路线，它比一般人工复原方法的步数少，但也没有人敢说它属于最少步数，或者说了也是不见得能给出证明的。

现在有人证明了可以不超过26步复原魔方，这和22步尚有一定差距。据说，今后或许会有更接近22的新研究结果。

请各位指正。

[此贴子已经被作者于2007-10-22 15:26:57编辑过]

foxmirra

26步是个啥子概念哦。。。。。昏迷[em06][em06][em06]

乌木

回24楼,我那是举例，以说明“研究的对象存在不存在都未定，怎么就有如何如何的结论”，同时质问8楼说的“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”。

现在，我再想想，8楼说得蛮奥妙，因为“任意状态魔方最多只需 26 步”和“（是否）存在 26 步态”这两个概念放在一句话中并不见得有多大的矛盾。

XiaoBai

QUOTE:

以下是引用乌木在2007-6-8 1:04:35的发言：

8楼说“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”

这话不好理解。我能不能这样想：

既然说的是魔方的“任意状态”，当然它们都是存在的咯？不见得会超出N（N约为四千亿亿个）个状态范围吧？如果连研究的对象存在不存在都未定，就有如何如何的结论了，会有这种事吗？

所谓 任意状态 应该指的是在这N种状态中的任意一种吧

s332654662

不会是用穷举法吧

Arcan

我只是那么举了一个例子，不必太深究：）