首頁(yè) > 圖片新聞

2010年08月13日09:30 | 中國(guó)發(fā)展門戶網(wǎng) www.chinagate.cn | 給編輯寫信 字號(hào)：T|T

盡管擁有43,252,003,274,489,856,000種不同的可能組合狀態(tài)，但魔方都可以在20步內(nèi)還原。

據(jù)國(guó)外媒體報(bào)道，相信許多人都玩過(guò)魔方，但是此前沒(méi)有人知道任意組合的魔方的最小還原步數(shù)究竟是多少。這一問(wèn)題困擾了數(shù)學(xué)家長(zhǎng)達(dá)三十多年，這個(gè)最小還原步數(shù)也被稱為“上帝之?dāng)?shù)”。美國(guó)加利福尼亞州科學(xué)家近日利用計(jì)算機(jī)破解了這一謎團(tuán)，研究人員證明任意組合的魔方均可以在20步之內(nèi)還原，“上帝之?dāng)?shù)”正式定為20。

這支研究團(tuán)隊(duì)位于美國(guó)加利福尼亞州帕洛阿爾托市?？茖W(xué)家們通過(guò)計(jì)算機(jī)計(jì)算和證明，任意組合的魔方都可以在20步內(nèi)還原。這一結(jié)果表明，大約有10萬(wàn)多種的起始狀態(tài)恰好可以在20步內(nèi)還原。

利用谷歌公司計(jì)算機(jī)強(qiáng)大的計(jì)算能力，研究人員檢驗(yàn)了魔方任何可能的混亂狀態(tài)(確切數(shù)字為43,252,003,274,489,856,000)。美國(guó)俄亥俄州肯特州立大學(xué)數(shù)學(xué)家莫雷-戴維德森教授也是研究人員之一，他表示，“我們現(xiàn)在可以肯定，這個(gè)‘上帝之?dāng)?shù)’就是20。對(duì)于我來(lái)說(shuō)，我也回到了原地。魔方伴隨著我成長(zhǎng)，這也是我為什么深入研究這個(gè)數(shù)學(xué)問(wèn)題的原因。這個(gè)謎團(tuán)引起了人們的廣泛關(guān)注，它也許是人類歷史上最受歡迎的謎語(yǔ)了?！笨茖W(xué)家們的初步研究成果發(fā)表于在線網(wǎng)站上，但戴維德森表示，他們準(zhǔn)備將研究成果提交給雜志正式發(fā)表。

程序員托馬斯-羅基花了15年的時(shí)間，致力于尋找這個(gè)謎團(tuán)的答案。據(jù)羅基介紹，研究團(tuán)隊(duì)所采用的算法可以在1秒鐘內(nèi)嘗試10億種可能，此前的計(jì)算機(jī)算法1秒鐘內(nèi)只能處理4000種可能。

為了讓問(wèn)題簡(jiǎn)單化，研究團(tuán)隊(duì)采用了一種所謂“群論”的數(shù)學(xué)技術(shù)。他們首先將魔方所有可能的起始狀態(tài)集分成22億個(gè)集合，每個(gè)集合包含了195億個(gè)可能的狀態(tài)。集合的分配原則是這些可能的狀態(tài)是如何應(yīng)對(duì)一組10個(gè)可能的還原步驟。再通過(guò)魔方不同的對(duì)稱性，這種分組技術(shù)使得研究團(tuán)隊(duì)將集合數(shù)減少到5600萬(wàn)個(gè)。

研究人員所采用的算法可以快速將這些還原步驟與恰當(dāng)?shù)钠鹗键c(diǎn)匹配起來(lái)，從而實(shí)現(xiàn)在20秒內(nèi)處理一個(gè)集合中的195億種可能。對(duì)于普通的家用電腦來(lái)說(shuō)，以這樣的速度完成整個(gè)處理任務(wù)需要大約35年時(shí)間。

2007年，《每日電訊報(bào)》曾經(jīng)報(bào)道稱，任意組合的魔方均可在26步內(nèi)還原。當(dāng)然，還有其他的報(bào)道稱已證明出更少的還原步驟。魔方由匈牙利埃爾諾-魯比克教授于1974年所發(fā)明，曾經(jīng)是世界上最暢銷的智力玩具。

返回頂部文章來(lái)源： 中國(guó)經(jīng)濟(jì)網(wǎng)綜合