美專家証明任意狀態魔方最多只需26步解開 - 魔術方塊

魔術方塊是匈牙利人Erno Rubik于20世紀70年代發明的，它能夠產生數十億種組合
狀態，是世界上最流行的組合遊戲之一。最近，美國計算機科學家對於魔術方塊的
一項研究証實，26步足以解開任意狀態的魔術方塊，這一結論打破了此前27步的最
好歷史証明，成為了一項新的紀錄。

　　1997年5月，UCLA的計算機科學家Richard Korf表示，任意狀態的魔方可以用
不超過20步解決。不過，他並不能証實這一觀點，此前也沒有人能夠証實魔方能以
少於27步解決。

　　在此次的研究中，美國東北大學的Gene Cooperman教授和研究生Dan Kunkle將
數學上群的概念應用於魔術方塊的組合狀態，在計算機上進行了模擬研究。他們的
成功離不開技術上的支持：作為內存擴展的7G分布式硬盤以及每秒1億次的超快計
算方式。此外，Kunkle表示，此次編寫的程序能夠進行大量的預先計算(pre-
computation)，這大大提高了研究中的計算速度，因此他們最終能夠在一秒鐘內找
到任意魔術方塊狀態不超過26步的解決方法。

　　此次研究的意義並不只限於進一步解開了一個謎團。Cooperman表示，魔術方塊
是探究和列舉問題的“實驗田”，許多不同領域的科研人員都有可能用到這一有效
的工具。(科學網 任霄鵬/編譯）

--
上文出自 2007-06-03 大陸新浪網新聞
http://financenews.sina.com/sinacn/304-000-106-109/2007-06-03/2228456445.html

--