[转帖]美专家证明任意状态魔方最多只需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

cube_artist

那估计迟早会有人背下来的.......

乌木

好像不大可能背得下来。因为，一个三阶魔方，离初态26步的态不会只有一种吧？离初态25步的、24步的……也都不会仅一种吧？初态（0步态）仅一个，一步态仅12个（U、 U’、D、 D'……B或 B'，共12种一步态），两步态还要多，……大概过了高峰后逐代减少，但到末代（26步态），不大会少到仅一个。四千亿亿个状态分布成为一张巨大、复杂的关系网，人们怎么把某一态到初态的最少步骤“背下来”呢？许许多多个26步态（最远态），它们有各自不同的复原回去的、26步路线。（如果路线一样，必定是同态。）总之，我怀疑人脑能否背下有关复原路线，“雨人”另当别论。这个问题，一条复原路线的步数倒不大，最多26步，但是路线数目极多极多。

此外，有人算过二阶魔方逐代状态数目的分布（比如二阶魔方的最远状态 (第11步) ），可以给人一定启发。（11步态有2644个，10步态有 623800个，9步态有1887748个，……）

[此贴子已经被作者于2007-6-4 23:24:32编辑过]

rongduo

我猜想应该是：把一种状态输入电脑，电脑就计算出一种不多于26步的公式。此公式原则上只适用于这一种或一类状态，对其它状态无效。

电脑的程序应该是万用的，但每次输出的公式则不是万用的。

不知这种猜想是否对。

[此贴子已经被作者于2007-6-4 21:06:12编辑过]

彳亍

cube4 好像不用1秒就能找到20步的算法呢？

集合庞大的电脑资源，来个穷举好了

[em06]

牛眼看魔方

QUOTE:

以下是引用彳亍在2007-6-4 22:24:55的发言：

cube4 好像不用1秒就能找到20步的算法呢？

集合庞大的电脑资源，来个穷举好了

[em06]

就是啊，这个程序似乎每次都能找出20步的算法，哪里需要那么好的机器，还有什么程序。。。楼主文章的叙述，好象没有提到证明，也只是做到了这一点而已，那何必那么费心费力费钱。。。

明华

QUOTE:

以下是引用彳亍在2007-6-4 22:24:55的发言：

cube4 好像不用1秒就能找到20步的算法呢？

 

    如果这个状态为 21 步，cube4 等工具 要用 多少 秒（天、月、年）找到 20 步 ？[em07]

 

明华

QUOTE:

以下是引用乌木在2007-6-4 20:37:13的发言：

人们怎么把某一态到初态的最少步骤“背下来”呢？许许多多个26步态（最远态），它们有各自不同的复原回去的、26步路线。这个问题，一条复原路线的步数倒不大，最多26步，但是路线数目极多极多。

 

    另：乌木 先生的概念有点混乱。美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。

    相关主题，请大家另参考：魔方的最远状态要几步复原

QUOTE:

以下是引用ggglgq在2005-2-21 8:57:59的发言：

      ？？？ 老猫 的“正六面体五阶魔方” ？？？
  
    老猫 先生，请问：

    如果有人在“魔方吧论坛”上证明了下面两个问题中的任意一个结论：

    1.对于 正六面体三阶魔方 旋转侧面（ 上、下、左、右、前、后 ） 90 度 或
180 度 都算 1 步，正六面体三阶魔方的最远状态为 21 步（即：此时根本不存在
22 步 的状态）；

    2.对于 正六面体三阶魔方 仅 旋转侧面（ 上、下、左、右、前、后 ） 90 度
算 1 步，正六面体三阶魔方的最远状态为 22 步（即：当 180 度算 2 步时才存在
22 步 的状态）。

    你的“正六面体五阶魔方”该如何处理 ？[em07]

乌木

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

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

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

乌木

1楼中说：“……找到任意魔方状态不超过26步的解决方法。……”

既然是“解决方法”应该就是具体的复原步骤。此外，这话就是说魔方的最远状态离开初态不超过26步；或者说任意两态之间距离不超过26步。

对吧？