看板 Rubiks 關於我們 聯絡資訊
※ [本文轉錄自 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
shikilo:演算法強者 08/12 21:48
ggyy940:20秒內195億.... 唉.... 08/12 21:48
DrPeace:當幸福來敲門 08/12 21:48
rexkimta:第一段的最後一句好幽默= = 08/12 21:49
sofaly:它 08/12 21:49
waterfrog302:3階行列式我們用喊的就秒掉啦!! 08/12 21:49
medama:而且不是靠撕掉小方塊的顏色貼紙再重新貼上。 08/12 21:49
pounil:竹中林浩正表示 08/12 21:49
digimaster:這才真的是在玩魔術方塊 不是知道解法純練速度 08/12 21:49
jodojeda:很簡單啊 拆掉重拼 08/12 21:49
qazsugf:魔方版一堆神手可以在10秒內解完所有組合... 08/12 21:49
bilinear:光用想的就很難,他們居然可以寫成程式 08/12 21:49
Pukau:明明手機有程式可以解了 電腦應該不可能要多久吧? 08/12 21:50
gg123sf:好厲害 演算法神手 08/12 21:50
veryawesome:撕掉在重新貼上這個也要花不少時間= = 08/12 21:50
eliteark:拿麥克筆塗可能最快 08/12 21:51
kio03:買新的比較快... 08/12 21:51
k85097ok:我只會一層一層慢慢解...最快也要一分鐘 08/12 21:51
sorrycar:難在可以各種情況都可以在20步驟內完成 08/12 21:52
heliosheep64:電腦王國...他家是用電腦蓋的嗎 08/12 21:52
taco20:先拆再組合 可以樂勝很多人 08/12 21:52
tt2:I said google, not sizzler! 08/12 21:52
-- 當你減肥幾公斤在高興時~~ 老實說在別人眼中~你還是個胖子唷 ^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.115.15.10
powerice:(驚訝的說不出話來) 08/12 21:58
TyrYawiaj:qazsugf:魔方版一堆神手可以在10秒內解完所有組合... 08/12 21:58
LLN858:20步啦,不是20秒^^""" 08/12 22:01
aegius1r:20秒比20步簡單多了吧XDDDDD 08/12 22:29
karte577:Google工程師出動了... 08/12 22:47
aegius1r:speedsolving上 rokichi本人的回應: http://0rz.tw/eyzFP 08/12 23:05
aegius1r:(這種暴力證明法果然有人不滿..像lars petrus..) 08/12 23:06
aegius1r:(還拿四色定理證明來類比 XD) 08/12 23:06
JiDung:algorithms的世界 是很深奧的....老師講NP 我完全聽不懂 08/12 23:20
DavidGuo:我上課也是以四色問題來比較說… 08/13 00:24
lightninglu:尬的!! 35年~~XD 08/13 11:42
cubefan:20秒簡單多了+1.... 08/13 17:32