[轉錄][新聞] 三階魔術方塊 20步數內解決

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