作者LLN858 (我好饿~我想吃人!)
看板Rubiks
标题[转录][新闻] 三阶魔术方块 20步数内解决
时间Thu Aug 12 21:52:52 2010
※ [本文转录自 Gossiping 看板 #1CO_jtU0 ]
作者: str8g () 看板: Gossiping
标题: [新闻] 三阶魔术方块 20步数内解决
时间: Thu Aug 12 21:47:31 2010
http://udn.com/NEWS/WORLD/BREAKINGNEWS5/5782416.shtml
三阶魔术方块 20步数内解决
【中央社╱台北12日电】
2010.08.12 06:07 pm
花了15年才达到这一步，但
最新研究证明，三阶魔术方块的任何组合，都能够在20个步数
之内破解，而且不是靠撕掉小方块的颜色贴纸再重新贴上。
「新科学家杂志」（New Scientist）电子版报导，
一名谷歌（Google）工程师和数名数
学家携手，破解了魔术方块的43,252,003,274,489,856,000种组合，每种排列组合都能够
在20步里还原。
来自加州巴罗艾托（Palo Alto）罗区奇（TomasRokicki）花了15年寻找破解魔术方块的
最少步骤。他说：「基本的突破，就是找出一个方法破解所有组合，不仅要一次解决，而
且还要快。」
这个步数被称为「上帝的数字」（God's number），意味着连上帝都不能在更少步数里破
解。「新科学家杂志」曾在2008年报导罗区奇将「上帝的数字」减少到22，但显然要将数
字再度缩小，需要一些聪明捷径。
为了简化问题，罗区奇和他的团队利用从「群论」（group theory）延伸出来的技巧。
首先将所有可能的排列组合归纳成22亿组，每组底下有195亿种组合。
他们在网站上写道：「
我们把问题分成2,217,093,120个小问题，每个问题底下有
19,508,428,800种不同组合，因此每个小问题能够用现代电脑运算。我们把它们分解，因
此能够快速运算。」
你可以把他的演算法想像成这样：想像你要去一个不熟悉的城市拜访朋友。他们给你画了
地图，告诉你右转左转，但是忘了告诉你起点。如果你随机找个点开始走，几乎不可能到
达目的地，但若对照上起点，你就绝对能走到。
因此，这个团队的快速演算法能够在
20秒内解决195亿种组合。
但是即使按照这个速度，要完成任务，一般电脑仍旧需要花上35年，因此需要另一个捷径
：谷歌工程师达斯瑞吉（John Dethridge）。利用他的电脑王国去计算，所有演算得以在
数星期内解决。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.229.247.13
1F：→ shikilo:演算法强者 08/12 21:48
2F：推 ggyy940:20秒内195亿.... 唉.... 08/12 21:48
3F：推 DrPeace:当幸福来敲门 08/12 21:48
4F：推 rexkimta:第一段的最後一句好幽默= = 08/12 21:49
5F：推 sofaly:它 08/12 21:49
6F：推 waterfrog302:3阶行列式我们用喊的就秒掉啦!! 08/12 21:49
7F：推 medama:而且不是靠撕掉小方块的颜色贴纸再重新贴上。 08/12 21:49
8F：→ pounil:竹中林浩正表示 08/12 21:49
9F：推 digimaster:这才真的是在玩魔术方块 不是知道解法纯练速度 08/12 21:49
10F：→ jodojeda:很简单啊 拆掉重拼 08/12 21:49
11F：→ qazsugf:魔方版一堆神手可以在10秒内解完所有组合... 08/12 21:49
12F：推 bilinear:光用想的就很难，他们居然可以写成程式 08/12 21:49
13F：推 Pukau:明明手机有程式可以解了 电脑应该不可能要多久吧？ 08/12 21:50
14F：推 gg123sf:好厉害 演算法神手 08/12 21:50
15F：推 veryawesome:撕掉在重新贴上这个也要花不少时间= = 08/12 21:50
16F：→ eliteark:拿麦克笔涂可能最快 08/12 21:51
17F：→ kio03:买新的比较快... 08/12 21:51
18F：→ k85097ok:我只会一层一层慢慢解...最快也要一分钟 08/12 21:51
19F：→ sorrycar:难在可以各种情况都可以在20步骤内完成 08/12 21:52
20F：推 heliosheep64:电脑王国...他家是用电脑盖的吗 08/12 21:52
21F：→ taco20:先拆再组合 可以乐胜很多人 08/12 21:52
22F：推 tt2:I said google, not sizzler! 08/12 21:52
--
当你减肥几公斤在高兴时~~
老实说在别人眼中~你还是个胖子唷 ^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.115.15.10
23F：推 powerice:(惊讶的说不出话来) 08/12 21:58
24F：→ TyrYawiaj:qazsugf:魔方版一堆神手可以在10秒内解完所有组合... 08/12 21:58
25F：→ LLN858:20步啦,不是20秒^^""" 08/12 22:01
26F：推 aegius1r:20秒比20步简单多了吧XDDDDD 08/12 22:29
27F：推 karte577:Google工程师出动了... 08/12 22:47
29F：→ aegius1r:(这种暴力证明法果然有人不满..像lars petrus..) 08/12 23:06
30F：→ aegius1r:(还拿四色定理证明来类比 XD) 08/12 23:06
31F：推 JiDung:algorithms的世界 是很深奥的....老师讲NP 我完全听不懂 08/12 23:20
32F：推 DavidGuo:我上课也是以四色问题来比较说… 08/13 00:24
33F：推 lightninglu:尬的!! 35年~~XD 08/13 11:42
34F：推 cubefan:20秒简单多了+1.... 08/13 17:32