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

看板Rubiks (魔術方塊)作者sch11 (一整個囧啊...囧rz)時間19年前 (2007/06/04 23:38)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/1

魔術方塊是匈牙利人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 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.59.168.73