[转帖]美专家证明任意状态魔方最多只需26步解开
<h1>美专家证明任意状态魔方最多只需26步解开</h1><div class="from_info">http://www.sina.com.cn 2007年06月04日 13:20 <font color="#a20010">科学网</font></div><p><!--Element not supported - Type: 8 Name: #comment--> </p><p> 魔方是匈牙利人Erno Rubik于20世纪70年代发明的，它能够产生数十亿种组合状态，是世界上最流行的组合游戏之一。最近，美国计算机科学家对于魔方的一项研究证实，26步足以解开任意状态的魔方，这一结论打破了此前27步的最好历史证明，成为了一项新的纪录。</p><p> 1997年5月，UCLA的计算机科学家Richard Korf表示，任意状态的魔方可以用不超过20步解决。不过，他并不能证实这一观点，此前也没有人能够证实魔方能以少于27步解决。</p><p> 在此次的研究中，美国东北大学的Gene Cooperman教授和研究生Dan Kunkle将数学上群的概念应用于魔方的组合状态，在计算机上进行了模拟研究。他们的成功离不开技术上的支持：作为内存扩展的7G分布式硬盘以及每秒1亿次的超快计算方式。此外，Kunkle表示，此次编写的程序能够进行大量的预先计算(pre-computation)，这大大提高了研究中的计算速度，因此他们最终能够在一秒钟内找到任意魔方状态不超过26步的解决方法。</p><p> 此次研究的意义并不只限于进一步解开了一个谜团。Cooperman表示，魔方是探究和列举问题的“实验田”，许多不同领域的科研人员都有可能用到这一有效的工具。(科学网 任霄鹏/编译）</p><p></p><p>转自：<a href="http://tech.sina.com.cn/d/2007-06-04/13201544076.shtml">http://tech.sina.com.cn/d/2007-06-04/13201544076.shtml</a></p> 那估计迟早会有人背下来的....... <p>好像不大可能背得下来。因为，一个三阶魔方，离初态26步的态不会只有一种吧？离初态25步的、24步的……也都不会仅一种吧？初态（0步态）仅一个，一步态仅12个（U、 U’、D、 D'……B或 B'，共12种一步态），两步态还要多，……大概过了高峰后逐代减少，但到末代（26步态），不大会少到仅一个。四千亿亿个状态分布成为一张巨大、复杂的关系网，人们怎么把某一态到初态的最少步骤“背下来”呢？许许多多个26步态（最远态），它们有各自不同的复原回去的、26步路线。（如果路线一样，必定是同态。）总之，我怀疑人脑能否背下有关复原路线，“雨人”另当别论。这个问题，一条复原路线的步数倒不大，最多26步，但是路线数目极多极多。</p><p>此外，有人算过二阶魔方逐代状态数目的分布（比如<a title="《<FONT color=#0000ff>二阶魔方的最远状态</FONT> <FONT color=#ff0000>(第11步)</FONT>》<br>作者：黑王子<br>发表于：2006-1-25 2:28:53<br>最后发贴：" href="http://bbs.mf8-china.com/dispbbs.asp?boardID=18&ID=1850&page=1"><font color="#0000ff"><strong>二阶魔方的最远状态 (第11步)</strong></font></a> ），可以给人一定启发。（11步态有2644个，10步态有 623800个，9步态有1887748个，……）<br/><br/></p>[此贴子已经被作者于2007-6-4 23:24:32编辑过]
<p>我猜想应该是：把一种状态输入电脑，电脑就计算出一种不多于26步的公式。此公式原则上只适用于这一种或一类状态，对其它状态无效。</p><p>电脑的程序应该是万用的，但每次输出的公式则不是万用的。</p><p>不知这种猜想是否对。</p><p></p>
[此贴子已经被作者于2007-6-4 21:06:12编辑过]
<p>cube4 好像不用1秒就能找到20步的算法呢？</p><p>集合庞大的电脑资源，来个穷举好了</p> <div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>彳亍</i>在2007-6-4 22:24:55的发言：</b><br/><p>cube4 好像不用1秒就能找到20步的算法呢？</p><p>集合庞大的电脑资源，来个穷举好了</p></div><p></p>就是啊，这个程序似乎每次都能找出20步的算法，哪里需要那么好的机器，还有什么程序。。。楼主文章的叙述，好象没有提到证明，也只是做到了这一点而已，那何必那么费心费力费钱。。。 <div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>彳亍</i>在2007-6-4 22:24:55的发言：</b><br/><p>cube4 好像不用1秒就能找到20步的算法呢？</p></div><p></p><p> </p><p> 如果这个状态为 21 步，cube4 等工具 要用 多少 秒（天、月、年）找到 20 步 ？</p><p> </p> <div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>乌木</i>在2007-6-4 20:37:13的发言：</b><br/><p>人们怎么把某一态到初态的最少步骤“背下来”呢？许许多多个26步态（<font color="#ff0000">最远态</font>），它们有各自不同的复原回去的、26步路线。这个问题，一条复原路线的步数倒不大，最多26步，但是路线数目极多极多。</p></div><p> </p><p> 另：乌木 先生的概念有点混乱。美专家证明任意状态魔方<font color="#ff0000">最多</font>只需 26 步，并<font color="#ff0000">没有</font>证明存在 26 步态。</p><p> 相关主题，请大家另参考：<a href="http://bbs.mf8-china.com/dispbbs.asp?boardid=15&replyid=16733&id=514&page=1&skin=0&Star=2"><font color="#0000ff">魔方的最远状态要几步复原<br/></font></a></p><br/><div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>ggglgq</i>在2005-2-21 8:57:59的发言：</b><br/><p><br/> <font color="#3300ff" size="5">？？？ <font color="#990000"><b>老猫</b></font><font color="#000000">
</font>的“正六面体五阶魔方” ？？？</font><br/> <br/> <b><font color="#990000">老猫</font></b> 先生，请问：</p><p> 如果有人在“魔方吧论坛”上证明了下面两个问题中的任意一个结论：</p><p> 1.对于 正六面体三阶魔方 旋转侧面（ 上、下、左、右、前、后 ） 90 度 或<br/>180 度 都算 1 步，正六面体三阶魔方的最远状态为 21 步（即：此时根本不存在<br/>22 步 的状态）；</p><p> 2.对于 正六面体三阶魔方 仅 旋转侧面（ 上、下、左、右、前、后 ） 90 度<br/>算 1 步，正六面体三阶魔方的最远状态为 22 步（即：当 180 度算 2 步时才存在<br/>22 步 的状态）。</p><p> 你的“正六面体五阶魔方”该如何处理 ？ </p></div> <p>8楼说“美专家证明任意状态魔方<font color="#ff0000">最多</font>只需 26 步，并<font color="#ff0000">没有</font>证明存在 26 步态。”</p><p>这话不好理解。我能不能这样想：</p><p>既然说的是魔方的“任意状态”，当然它们都是存在的咯？不见得会超出N（N约为四千亿亿个）个状态范围吧？如果连研究的对象存在不存在都未定，就有如何如何的结论了，会有这种事吗？</p> <p>1楼中说：“……找到任意魔方状态不超过26步的解决方法。……”</p><p>既然是“解决方法”应该就是具体的复原步骤。此外，这话就是说魔方的最远状态离开初态不超过26步；或者说任意两态之间距离不超过26步。</p><p>对吧？</p>