魔方是匈牙利人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
好像不大可能背得下来。因为，一个三阶魔方，离初态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编辑过]
我猜想应该是：把一种状态输入电脑，电脑就计算出一种不多于26步的公式。此公式原则上只适用于这一种或一类状态，对其它状态无效。
电脑的程序应该是万用的，但每次输出的公式则不是万用的。
不知这种猜想是否对。
[此贴子已经被作者于2007-6-4 21:06:12编辑过]
cube4 好像不用1秒就能找到20步的算法呢？
集合庞大的电脑资源，来个穷举好了
[em06]cube4 好像不用1秒就能找到20步的算法呢？
集合庞大的电脑资源，来个穷举好了
[em06]cube4 好像不用1秒就能找到20步的算法呢？
如果这个状态为 21 步，cube4 等工具 要用 多少 秒（天、月、年）找到 20 步 ？[em07]
人们怎么把某一态到初态的最少步骤“背下来”呢？许许多多个26步态（最远态），它们有各自不同的复原回去的、26步路线。这个问题，一条复原路线的步数倒不大，最多26步，但是路线数目极多极多。
另：乌木 先生的概念有点混乱。美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。
相关主题，请大家另参考：魔方的最远状态要几步复原
？？？ 老猫
的“正六面体五阶魔方” ？？？
老猫 先生，请问：
如果有人在“魔方吧论坛”上证明了下面两个问题中的任意一个结论：
1.对于 正六面体三阶魔方 旋转侧面（ 上、下、左、右、前、后 ） 90 度 或
180 度 都算 1 步，正六面体三阶魔方的最远状态为 21 步（即：此时根本不存在
22 步 的状态）；
2.对于 正六面体三阶魔方 仅 旋转侧面（ 上、下、左、右、前、后 ） 90 度
算 1 步，正六面体三阶魔方的最远状态为 22 步（即：当 180 度算 2 步时才存在
22 步 的状态）。
你的“正六面体五阶魔方”该如何处理 ？[em07]
8楼说“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”
这话不好理解。我能不能这样想：
既然说的是魔方的“任意状态”，当然它们都是存在的咯？不见得会超出N（N约为四千亿亿个）个状态范围吧？如果连研究的对象存在不存在都未定，就有如何如何的结论了，会有这种事吗？
1楼中说：“……找到任意魔方状态不超过26步的解决方法。……”
既然是“解决方法”应该就是具体的复原步骤。此外，这话就是说魔方的最远状态离开初态不超过26步；或者说任意两态之间距离不超过26步。
对吧？
8楼说“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”
这话不好理解。我能不能这样想：
既然说的是魔方的“任意状态”，当然它们都是存在的咯？不见得会超出N（N约为四千亿亿个）个状态范围吧？如果连研究的对象存在不存在都未定，就有如何如何的结论了，会有这种事吗？
呵呵，这正是 乌木 先生对数学概念理解模糊混乱的地方呀！
很愿意与大家讨论这样的问题，玩理论的魔友对数学概念的理解应该比其他魔友更强些。
打个比方， 2 ～ 100 以内（对比：正六面体三阶魔方魔方） 质数（对比：最远状态）
的 个数 （对比：最少步数）为 25 （对比：现在不知道） 。
假如现在人类比较“弱智”，很多科学家在攻克 “ 2 ～ 100 以内 质数 的 个数 ”
（对比：现代科学家在攻克“正六面体三阶魔方魔方 最远状态 的 最少步数”）“难题”。
美国科学家曾经证明： 2 ～ 100 以内 质数 的 个数 最多 不超过 56 个！
韩国科学家继而证明： 2 ～ 100 以内 质数 的 个数 最多 不超过 49 个！
中国科学家再而证明： 2 ～ 100 以内 质数 的 个数 最多 不超过 39 个！
..........................................................
他们都在证明（缩小）“ 2 ～ 100 以内 质数 的 个数 ”的上界，但并不等于真的得出
“ 2 ～ 100 以内 质数 的 个数 ” 就是 56 个、 49 个、 39 个 ..................
因为 “ 2 ～ 100 以内 质数 的 实际 个数 为 25 ”
1楼中说：“……找到任意魔方状态不超过26步的解决方法。……”
既然是“解决方法”应该就是具体的复原步骤。此外，这话就是说魔方的最远状态离开初态不超过26步；或者说任意两态之间距离不超过26步。
对吧？
对！
另一方面，即便美专家给出了 正六面体三阶魔方魔方 某一状态的 26 步 公式（可能很长
时间人们无法打破 这一状态的 26 步 公式）但这并不说明 正六面体三阶魔方魔方 最远状态
的 最少步数 真的就为 26 步。因为这一状态有可能被 20 、18 等等 更少步数 的 公式 取代。
因为 美专家并没有证明存在 26 步 的 正六面体三阶魔方魔方 状态。仅仅是用计算机证明了
正六面体三阶魔方 任意状态 最多 只需 26 步 解开！ 26 步 只是一个 上界，并非最远状态的
步数！
有关这个问题，请大家参考 还猪哥哥 先生（老猫、还猪哥哥、大烟头 等都有很深的数学造诣）
的： 把任意拧乱的魔方的角块全部归位，理论上最少步数的上限是多少步？
很愿意与大家讨论这样的问题，玩理论的魔友对数学概念的理解应该比其他魔友更强些。
谢谢。谢什么？谢您让我知道自己有“对数学概念理解模糊混乱的地方”。
尽管对此我目前还不明白，但至少会引起注意，争取明白。这过程应该会有不亦乐乎的事情的吧。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
是不是这么一回事：1楼中此时此人说“……找到任意魔方状态不超过26步的解决方法。……”，也许彼时彼人会找到小于26步的方法。
此外，以前不是说有人研究后认为最远态是“21～22步”吗？怎么现在来了个“26步”？是一回事吗？是进步还是退步呢？
蛮感兴趣。
明华说的很正确。
美国专家只是证明了他们可以在26步内能够还原魔方，也就是说任何魔方都可以在26步内还原（或者说魔方任意两个状态之间的步数小于等于26步），并没有证明26步是魔方最远的状态。就如同一个人采用层先法，他可以宣布200步内能够还原魔方（我随便说的一个步数，没计算过），也就是任何魔方都可以在200步内还原，这时另一个人使用了CFOP，然后他可以宣布任何魔方它都可以80步之内还原……美国专家能做的也跟上面的差不多，只是证明了26步可以还原魔方，也就是魔方最远状态肯定在26步或26步以内。
至于我们经常见到的说魔方的最远状态是21步或22步，很可能是一个猜想，尽管可能是正确的，但没有被证明。
“……并没有证明26步是魔方最远的状态。”
“……魔方最远状态肯定在26步或26步以内。”
楼上的话蛮深奥，尤其这两句话，不管这些了。且谈谈我的想法。
一个初态放在北极，12个子代态布于四周（90×12/13）°的维度圈上，百多个第三代态置于（90×11/13）°纬度圈，…………第13代密布到赤道上，…………多少多少个第26代态“压缩”进南极点。反正是几何点，济济一堂没事的。有多少个最远态（第26代）就有多少条北南之间的经线联系着，每一条经线的长度就是26步，这些经线也就是26步的一个个公式。（当然，除了这些最短路线以外，北南极之间还可以有许许多多条非最短路线。这是另一码事。）
照有人的说法是，现在证明了的仅仅是如此这般的“26步”，但是还没有26步的、具体的一些公式（当然也就没有相应的第26代（之一或之几）的、具体的状态）。
对吗？否则，总该给出个把有关公式和“南极之花”的吧？
[此贴子已经被作者于2007-6-15 0:39:07编辑过]
当然，真要给出了某个“最远态”，也决不会是三头六臂的模样，也许您会说，啊，好像见过……
四千亿亿个状态中的每个状态（A）都是它对应的最远态（一大批B）的最远态，也就是说，任一状态A放到北极点，设想四千亿亿个态会自动对号入座，南极点的一大批B，它们的模样应该是各位魔友司空见惯的模样。问题是有关的26步公式要具体知道。
当然还要有理由表明这26步是最短路线，否则，谁都会转它26步说得到的H态是最远态，却不料被某个高手用（比如说）10来步就复原了，表明H态不是最远态。
这就引出一个问题，如果有人给出一个或一些26步公式，声称是到达最远态的步骤，读者看了如何证实或证伪呢？是不是这里也需要“谁主张，谁举证”？即使举证了，谁来判断？[此贴子已经被作者于2007-6-15 15:03:34编辑过]
比方说，我胡说下面26步是到达最远态的公式之一，行吗？[em01][em01]
U' L2 R2 D2 U B' L R' D2 U' B F' L2 D2 U B' F' D U2 F U B' L D2 L2 R
计算机解魔方不会像人这样去分几个步骤完成的。
它是一气呵成，基本同时使角块和棱块归位且色向正确。
用CUBE EXPLORLE可以计算出最短步骤，但人看了这步骤，就理解不了。
我只是那么举了一个例子，不必太深究：）
8楼说“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”
这话不好理解。我能不能这样想：
既然说的是魔方的“任意状态”，当然它们都是存在的咯？不见得会超出N（N约为四千亿亿个）个状态范围吧？如果连研究的对象存在不存在都未定，就有如何如何的结论了，会有这种事吗？
回24楼,我那是举例，以说明“研究的对象存在不存在都未定，怎么就有如何如何的结论”，同时质问8楼说的“美专家证明任意状态魔方最多只需 26 步，并没有证明存在 26 步态。”。
现在，我再想想，8楼说得蛮奥妙，因为“任意状态魔方最多只需 26 步”和“（是否）存在 26 步态”这两个概念放在一句话中并不见得有多大的矛盾。
我就我目前的认识大概说说这个问题。
三阶魔方的状态数有约四千亿亿个，任一状态都可以从复原态出发一步、一步……地转得。反之，从除了复原态的任一状态出发，都可以一步、一步……复原。
有一种理论任为这一步、一步……最多为22步，即距离最远的两个状态之间的变化步子为22步。此外，一个态所对应的最远态可以有许多个。也就是说，一个初态，可以有许多个第X代“后代”。
如果某一态和复原态的最短距离为n步（n≤22），但不知道具体哪n步，我们往往用不止n步来复原它，那是没办法的办法，只好走迂回曲折的路线。可以保证成功，但不敢说是最少步数。
即使用某种电脑软件来求得某一复原路线，它比一般人工复原方法的步数少，但也没有人敢说它属于最少步数，或者说了也是不见得能给出证明的。
现在有人证明了可以不超过26步复原魔方，这和22步尚有一定差距。据说，今后或许会有更接近22的新研究结果。
请各位指正。
[此贴子已经被作者于2007-10-22 15:26:57编辑过]
| 欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) | Powered by Discuz! X2 |