科學家15年證明還原任意魔方最多需20步(圖)

發表：2010-08-13 20:46

儘管有43,252,003,274,489,856,000(約合4.3×1019) 種不同的可能組合狀態，但魔方都能在20步內還原。

據國外媒體報導，相信許多人都玩過魔方，但是此前沒有人知道任意組合的魔方的最小還原步數究竟是多少。這一問題困擾了數學家長達三十多年，這個最小還原步數也被稱為「上帝之數」。美國加利福尼亞州科學家近日利用計算機破解了這一謎團，研究人員證明任意組合的魔方均可以在20步之內還原，「上帝之數」正式定為20。

這支研究團隊位於美國加利福尼亞州帕洛阿爾托市。科學家們通過計算機計算和證明，任意組合的魔方都可以在20步內還原。這一結果表明，大約有10萬多種的起始狀態恰好可以在20步內還原。

利用谷歌公司計算機強大的計算能力，研究人員檢驗了魔方任何可能的混亂狀態(確切數字為43,252,003,274,489,856,000 約合4.3×1019)。美國俄亥俄州肯特州立大學數學家莫雷-戴維德森教授也是研究人員之一，他表示，「我們現在可以肯定，這個 ‘上帝之數’就是20。對於我來說，我也回到了原地。魔方伴隨著我成長，這也是我為什麼深入研究這個數學問題的原因。這個謎團引起了人們的廣泛關注，它也許是人類歷史上最受歡迎的謎語了。」科學家們的初步研究成果發表於在線網站上，但戴維德森表示，他們準備將研究成果提交給雜誌正式發表。

程序員托馬斯-羅基花了15年的時間，致力於尋找這個謎團的答案。據羅基介紹，研究團隊所採用的演算法可以在1秒鐘內嘗試10億種可能，此前的計算機演算法1秒鐘內只能處理4000種可能。

為了讓問題簡單化，研究團隊採用了一種所謂「群論」的數學技術。他們首先將魔方所有可能的起始狀態集分成22億個集合，每個集合包含了195億個可能的狀態。集合的分配原則是這些可能的狀態是如何應對一組10個可能的還原步驟。再通過魔方不同的對稱性，這種分組技術使得研究團隊將集合數減少到 5600萬個。

研究人員所採用的演算法可以快速將這些還原步驟與恰當的起始點匹配起來，從而實現在20秒內處理一個集合中的195億種可能。對於普通的家用電腦來說，以這樣的速度完成整個處理任務需要大約35年時間。

2007年，《每日電訊報》曾經報導稱，任意組合的魔方均可在26步內還原。當然，還有其他的報導稱已證明出更少的還原步驟。魔方由匈牙利埃爾諾-魯比克教授於1974年所發明，曾經是世界上最暢銷的智力玩具。

来源:新浪科技

【誠徵榮譽會員】溪流能夠匯成大海，小善可以成就大愛。我們向全球華人誠意徵集萬名榮譽會員：每位榮譽會員每年只需支付一份訂閱費用，成為《看中國》網站的榮譽會員，就可以助力我們突破審查與封鎖，向至少10000位中國大陸同胞奉上獨立真實的關鍵資訊，在危難時刻向他們發出預警，救他們於大瘟疫與其它社會危難之中。