Re: [閒聊] 與魔術方塊相關的研究

[weijiunn (http://kuso.cc/xXD )]

感謝大邪  XD

終於有人認真的提到這個網頁

我大概解釋一下 2-phase-algorithm 的運作方式


首先名詞解釋：

2-phase-algorithm

是作者使用的演算法，  字面意思就是，把解方塊的程序分成兩個部分

1. phase 1
2. phase 2

詳細情形下面會說


god's algorithm

這則是最佳解的集合

對於某一個 scramble 而言， 他的最佳解法叫做 optimal solution

而 Rubik's Cube 的 4.3 x 10^19 種排列， 全部的 optimal solutions 集合起來

就是  god's algorithm




※ 引述《auk109 (大邪)》之銘言：
: 而且，耐心花時間讀完後
: 發現，此作者用的 二階演算法...比 神之演算法(God's Algorithm) 步數還少
: 而且依照文意，在任何情況下都只需要20步以內即可完成六面

作者的假設是這樣的沒錯

但是他尚沒有辦法 證明 所有的 pattern 都能在 20 步 之內解開

他曾經用電腦隨機產生了  50 萬組 scramble

並且用他的演算法去找最佳解，  發現這 50 萬組 都可以在 20 步 之內被解開


隨機一千組 scramble 的最佳解 步數 分布如下圖
http://kociemba.org/pics/opt1000.gif


作者利用軟體計算發現，

隨機方塊的 最佳解 所需要的步數分布， 需要 21 步以上的  機率尚未明瞭

但預期應該是 0


不過這些都不足以作為證明， 但我們可以大膽的說，

所有的方塊，  「應該」 都能在 20 步以內解開，  最多 20 步


: (好吧~我沒認真看還沒完全了解這兩階段在幹嘛...)

名詞解釋


maneuver

隨意一組轉動方塊的動作例如  R U' D2 L   ， 我們稱他做 maneuver



關於 2-phase-algorithm 的運作方式大致如下：


首先是方塊組合的分布

如果你把一個方塊轉亂

但是只用  U D R2 L2 F2 D2  (也就是前後左右不能轉 90 度)

這些動作的話，  那麼你能夠轉出的最多 pattern 是有限的

這個集合我們稱他做  G1 = <U,D,R2,L2,F2,D2>


而同時在這個集合中

我們會發現所有 corner 和 edge 的 orientation 都不能被改變
(會盲解的應該比較能理解原因)


而 phase-1 要做的事，  就是找出一組 maneuver

讓目標的方塊進入  G1 這個集合中




phase-2  所做的，則是估計一個 G1 當中的方塊

需要多少步數才能被解開

他並不會找出正確的動作， 因為自由度太高，要找出解法太花時間


接著就是下面 auk 所說的

要找最佳解的方法，

就是對於一個隨機的方塊

先任意找出一組  maneuver ， 使方塊進入 G1

接著估計 phase-2 所需要的步數


假設 分別是 10 和 12 步


接著程式會重新計算， 想辦法讓 phase-2 需要的步數減少

同時 phase-1 需要的步數會增加


一直到最後 ， phase-2 的步數會變成 0

那麼程式就停止， 而 phase-1 所找到的 maneuver  則是解法



: 但是文中有提到，在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


先降吧，有興趣的可以自己看看網頁  :p



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 203.73.247.203
推 auk109:manerver那邊懂了..看懂了..XD
→ auk109:感謝鄭咩講解~~~~!
推 CHOIP:推一下~~~解釋的很清楚:)
推 Zidane5:推，非常有趣:)
推 Andyuki:推~ 其實我只看懂八成 :P
推 Andyuki:意思是說只要有辦法找到21步以上的scramble  就有趣了??
推 weijiunn:scramble 在這裡的意思相當於原文的  case
→ weijiunn:scramble 是轉亂的方法，現在規則是  25 步
→ weijiunn:solution 或 manerver  是對於 任意 scramble 的解法
→ weijiunn:目前嘗試證明的，就是所有 optimal solution 皆 < 20步