魔方吧·中文魔方俱乐部

标题: 计算机证明魔方还原步数小于23 [打印本页]

作者: wangyuan01 时间: 2008-6-7 18:19:15 标题: 计算机证明魔方还原步数小于23

 转载：Solidot 作者：Solidot 编辑：Kaiputer　
      Rubik's Cube的中文名叫魔方，是匈牙利的Rubik教授在1974年发明的智力玩具。去年两位东北大学学生用了一点手上的空闲时间证明任何结构的魔方都能在26步内还原。两个月前Tomas Rokicki，在斯坦福大学受过训练的数学家更胜一筹，他证明没有一种结构的魔方需要26步才能还原，因此他将还原最少步骤降至25步。 Rokicki的证明完全依靠计算机科学，他使用立方体的对称来研究集合内的转换，这允许他将“立方体空间”分割成20亿个集合，每个集合包含200亿个项。
他发现许多集合与其它集合本质上是相同的，因此可以去除。为了完成整个计算，他需要一个8GB内存、1.6GHz Q6600处理器的的工作站运行1500小时。 
       日前，Tomas Rokick个人主页的更新，他宣布任意结构的魔方都可以在23步内解决。他之前进行运算的工作站为8G内存和1.6GHz Q6600 CPU，现在已经升级为一台超级计算机，索尼图形图像运作公司（Sony Pictures Imageworks）提供给他使用（当然是在电影制作空闲时间内）。在这个曾经制作了《蜘蛛侠3》和《冲浪企鹅》的工作室的帮助下，新的计算结果暗示任意结构的魔方可能的解决步数是21、22或23步。

作者: hzhenr 时间: 2008-6-7 18:31:43

太强大了............顶

作者: 刘超 时间: 2008-6-7 18:35:19

已经差不多达到神的境界了

太厉害了

作者: 魔№鬼 时间: 2008-6-7 18:50:34

实战中没法用，打乱就有用了。用计算机算会越算越少？

作者: 水泮居 时间: 2008-6-7 20:17:58

不是说官方说计算机最少还原也只能是26步吗?怎么变成23了?

作者: cpp1701 时间: 2008-6-7 20:18:00

支持一下。。。。。。。。。。。。。。

作者: bbshanwei 时间: 2008-6-7 20:50:56

8G内存的工作站预算1500小时！！真是。。。。。

作者: Atato 时间: 2008-6-7 20:53:29

支持一下....真是越算越小步了

作者: 魔鱼儿 时间: 2008-6-7 21:10:17

这么厉害，要是实战中人类也能这样解决，那就太强大了

作者: 鱼吖 时间: 2008-6-7 21:17:14

又刷了啊...最小步数还原我还一点不会呢..哈哈~~

支持啦..

作者: kexin_xiao 时间: 2008-6-7 21:18:34

23步啊，人脑什么时候能做到啊！

作者: 鱼吖 时间: 2008-6-7 21:23:15

不太可能..1个集合200E个元素....谁要能算出来我把那魔方吃了.....我说的是在规定时间...

作者: kennyleelee 时间: 2008-6-7 21:27:18

还是电脑强啊，不过电脑是人发明的

作者: 鱼吖 时间: 2008-6-7 21:30:54

青出于蓝而胜于蓝...8G的内存...都那么长时间...

不过如果换1TB的内存(我是说如果可能/)..那时间能减少125倍,也就是不到一天的时间啊~~这样就厉害了~~~

作者: kexin_xiao 时间: 2008-6-9 15:40:19

任意结构的魔方可能的解决步数是21、22或23步——以后可能在20步以内吗？

作者: tarzan 时间: 2008-6-9 15:56:29

任意结构，包括二十阶吗？

作者: noski 时间: 2008-6-9 18:38:25

26到25到23，有超级计算机的帮助，进展很神速啊。任意结构应该是指三阶魔方的任意打乱的状态。三阶不可能少于20步，这也是证明出来了的。。

作者: 刘超 时间: 2008-6-9 18:46:52

没错，我是有看过三阶不可能少于20步还原，所以才说现在已经接近神的境界了

作者: kexin_xiao 时间: 2008-6-9 20:19:50

早晚可以达到极致啊，厉害！

作者: ggglgq 时间: 2008-6-9 20:56:04

原帖由 <A href="http://bbs.mf8-china.com/viewthread.php?tid=514&extra=page%3D8&page=2">ggglgq 于 2005-2-21 08:57  20 楼</A> 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=5746&ptid=514" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>   
1.对于正六面体三阶魔方旋转侧面（上、下、左、右、前、后） 90 度或 180 度都算 1 步，正六面体三阶魔方的最远状态为 21 步（即：此时根本不存在 22 步的状态）；   
2.对于正六面体三阶魔方仅旋转侧面（上、下、左、右、前、后） 90 度算 1 步，正六面体三阶魔方的最远状态为 22 步（即：当 180 度算 2 步时才存在 22 步的状态）。

希望有人（国内外人士运用各种方法）能证明，呵呵！

作者: 鱼吖 时间: 2008-6-9 22:03:57

那个,任意结构是指什么,阶数么?

作者: 乌木 时间: 2008-6-10 10:01:39

本帖20楼中的引用帖子应是 <LABEL> </LABEL> <A href="http://bbs.mf8-china.com/viewthread.php?tid=514&extra=page%3D1">魔方的最远状态要几步复原</A>（<A href="http://bbs.mf8-china.com/viewthread.php?tid=514&extra=page%3D1&page=2" target=_blank>http://bbs.mf8-china.com/viewthread ... tra=page%3D1&page=2</A>）这一帖的20楼的内容吧？到那里可以看看它的上下文。

作者: 还猪哥哥 时间: 2008-6-10 13:08:04

现在已经不关心三阶最远状态的步数了。关心纯色四阶的最远步数是多少。现在参加三阶最少步数复原比赛的高手一般可以三十步出头复原了，给多一点时间算到三十步内也并非不可能。相比之下四阶复原的步数，现在能达到的水平和极限差很远吧。CUBE EXPLORER用的两步骤复原法基本都能很快算出最优解了。那四阶要用多少步骤复原法才能得到接近极限的优化解呀。据我所知，现在用8步骤法求解四阶的步数大概在64步，用7步骤法求解大概是60步左右。这样看来四阶的最远状态估计不到60步了。

作者: xianjizxj 时间: 2008-6-10 13:20:39

晕这才几天呐又少了三步。

作者: wacllffd 时间: 2008-6-14 18:51:30

想也想不到。。。。。。。

作者: wangyuan01 时间: 2008-6-14 19:05:19

最近看《魔方的科学盒计算机表现》发现“有一些复杂的群论设计估计，从初始状态到最远的状态只需要22或23转”，自己编个魔方还原程序动不动就算死机了，看来编程还是难啊～～

作者: Xwam 时间: 2008-7-12 09:05:00

支持。。。。

作者: 152762222 时间: 2008-7-12 20:40:03

牛！

人脑还是没电脑快吖

作者: earthengine 时间: 2008-8-17 15:43:12

这个结果估计是纯色的。要是全色的，不知道要多少步。

作者: 乀猎神族づ释 时间: 2008-8-19 16:47:17

晕,难过世界记录才几秒~

作者: 咖啡味的茶 时间: 2008-8-20 08:52:53

其实这个最少还原步数需要定义什么是一步才可以，到底转动中间层是否可以算做一步？

作者: 7阶4分 时间: 2008-10-28 18:12:44

最小步数还原我还一点不会呢

作者: xiangping 时间: 2008-10-28 22:46:01

实在是强大啊，不过说来也是，咱们好歹转几下就得花转好多次的时间恢复

作者: versionxp 时间: 2008-11-23 11:41:13

知道了，也许会更少

作者: hwh19361 时间: 2008-11-27 23:04:17

呵呵，强呀，估计没人能做到

作者: RainYu 时间: 2008-11-28 11:24:01

人脑估计达不到这样的程度吧。

作者: hzhenr 时间: 2008-11-28 12:05:57

强贴，再顶.....

作者: rokilly 时间: 2008-11-28 12:30:38

26變23 差距那麼大?!真正證明了嗎?

作者: lvita 时间: 2008-11-29 11:13:34

不是吧..那么牛X??

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