作者auk109 (大邪)
看板Rubiks
標題Re: [閒聊] 與魔術方塊相關的研究
時間Wed Oct 18 20:03:21 2006
前幾天還在跟學長聊說
如果以後寫一個軟體,把六面的顏色輸入進去
就是不給他scramble..自己輸入顏色
然後給他跑一個公式出來轉...是可以轉回六面的公式
應該會很屌..
結果剛好昨天學長找到個有趣的軟體
「Cube Explorer 3.8」
原網址:
http://kociemba.org/cube.htm
演算法使用: Two-Phase Algorithm
而且,耐心花時間讀完後
發現,此作者用的 二階演算法...比 神之演算法(God's Algorithm) 步數還少
而且依照文意,在任何情況下都只需要20步以內即可完成六面
第一階段最多需要 12步
第二階段最多需要 18步
(好吧~我沒認真看還沒完全了解這兩階段在幹嘛...)
但是文中有提到,在1995年時已經有人證明出若是 Phase 1 往上遞增的話...
就有可能將 Phase 2的步數都消耗為 0
而轉法的概念有點像 Square one ...在 R, L, F, B 四個面..都只轉180度
調整角與邊的方向就在 U, D 兩面做處理
所以若是一般跑出來未最佳化的解法通常是 18~20步
這是用 Phase1 + Phase2 的結果
若是勾選最佳化(optimal)的話..可能要花 好幾分鐘跑一個 case
然後跑出個 16~18步的解法, 這是將 phase1遞增後 , 嘗試把 phase2減少步數後的結果
最理想話就是將 phase2 的步數減少為 0
軟體: Cube Explorer 3.8
大家可以使用看看他的軟體...非常有趣
可以自己輸入顏色 再給電腦運算
他會當場輸出一個約 18~20步的列表
若是勾選 optimal 再執行...
可能要跑好久..XD
文中有提到,使用 P4-3G的電腦跑,一般的case大約在 2~3分鐘解出
但理論上有可能有某些case會需要很久...可能以小時、天來做單位的
(剛剛跟學長在試一個 case..就花了1x分鐘..)
而且!!!!
最重要的是
這軟體還可以用 WebCam 來測定六個面的顏色
我們試過可以成功使用.而且判斷上沒問題
PS. 方塊為白底最好,其他底色因為在顏色使用平均值判斷時有可能出錯
說了這麼一堆...
有興趣研究的人,就快去看看吧..XD
另外,對於程式有興趣的,可以看左邊 Menu 下方...
有他對於此程式的說明與數學式等等的..
(我非常懶的看..orz...所以~~Debug , CHOIP大大們 ...靠你們啦..XD)
附上測試組 scramble
L2 D2 U F' L R F D2 U L2 R' F2 R2 D U L' R2 D' U L2 B2 L' R D' R2
最佳解 (16步)
L2 F R2 B U2 B R' L2 F D L2 B' R' B' D L'
所以~現在要說.....任何 case都可以在 20步內完成了...對嗎...XD
--
/\ \ /\__\ /\__\ 科 來
/::\ \ /:/ _/_ /:/ _/_ 技 自
/::\:\__\ /:/_/\__\ /::-"\__\ 始 於 墮
\/\::/ / \:\/:/ / \;:;-",-" 終 性
/:/ / \::/ / |:| | !
\/__/ \/__/ \|__|
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.127.112.149
→ auk109:補充一下..軟體安裝時會從網路下載約 65mb的資料..請耐心等 10/18 20:06
推 CHOIP:這實在太厲害了... 10/18 20:11
※ 編輯: auk109 來自: 140.127.112.149 (10/18 20:27)
→ rehearttw:EDIT,邊與邊換,角與角換,完成按Solve(無解會不給你 10/18 21:04
→ rehearttw:按,> Play 給你看 10/18 21:05
推 Andyuki:用Webcam判斷真的很屌 XDDD 不過周圍光線的影響要考慮進去 10/18 21:12
推 Andyuki:你的碩士論文就是找到一個比它更快、步數更少的方法投IEEE 10/18 21:16
推 auk109:囧...你想讓我在這待個十年嗎..XD 10/18 21:53
推 weijiunn:他也有提到 並沒有證明所有 case 都可以在 20 步內解開 10/18 22:27
→ weijiunn:他用電腦跑了幾十萬組 但數學上 只要有一組沒有證明 10/18 22:27
→ weijiunn:就等於沒有證明 所以這樣的證明是不充足的 10/18 22:28