推 LinkCar:問題就是N越大 CASE越多...所以NP 10/18 18:35
推 weijiunn:拿 Square-1 來思考會比較好理解 10/18 18:43
→ weijiunn:Sq1 恢復成正方形最多需要七步 10/18 18:44
→ weijiunn:所以在 "最亂" 的情形下，不管轉什麼動作都有幫助 10/18 18:44
※ 引述《Debug (rubiks.tw/timer)》之銘言：
: 現在研究上對魔術方塊最長步數還是未定論
: 對於任意亂的方塊，是否存在一個最短路徑的解法？
: 這個答案是肯定的，那麼如果存在一個這樣的解法，
: 那麼將之推廣的話，對於所有的狀態，是否都能在n轉之內將其復元呢？
: 有人說大概是 22 or 23 之譜，但是從來就沒有人能證明
: 因為這個問題在 NP-hard 裡面~
: 這是一個 open problem 喔！！
這個問題好難喔^^
換一個角度想
如果所有的case一定可以在N步之內還原
假設N=23好了
那能不能推算出來
這個23步才能還原的case(可能不只一個)，其花色是長什麼樣子呢？
為什麼這樣就是"最亂的"
這應該有某些原理才對
就像我們用骰子(六面體)來看
1點向上時，滾動零步
2345點向上時，最少要滾動1步，才能使1點向上
6點向上時，則要滾動兩步
所以，6點向上的case，就是最複雜的
(不過這個例子總共也只有6個cases，很容易就算出來了)
另一個例子：
D(010)●-----●C(011)
A(000)●-----●B(001)
｜ ｜ ｜
｜ 。 ｜ ●G(111)
E(100)●-----●F(101)
A不用走(即：零步)就可以回到A
B,D,E最少要經過一個邊(1步)才能回到A
C,F...則需要兩步
G點則要三步才可回到A，所以展開成樹狀圖(或是更複雜的格子圖)時
就可以算出所有的case各需要多少步
然後按照類似座標編號的原理，我們可以了解，為什麼G是"最遠離A"的case
同理
把方塊所有的組合也排成一個樹狀圖(格子圖)，整個展開：
|- case 2.1 (R+R)
|- case 2.2 (R+R'= case0)
|- case 1 (R) ----|- caee 2.3 (R+U)
|- case 2 (R') |- ：
|- case 3 (U) |- ：
case 0(已完成)--|- case 4 (U')
| ：
| ：
： ：
只要先了解"最複雜"的case應該長什麼樣
應該就可以慢慢推導回來
當然，樹狀圖展開之後，會產生次方級數(非多項式)個點，自然是屬於NP的問題了
另外，補充一個好玩的
假設 case N是"最複雜"的case，最少需要N步才能還原
那麼，當你拿到case N時，不管你怎麼轉，都"不會更糟"
也就是說，如果你轉一個U，那麼，此時的case，只會有兩種情形：
1．需要N-1步，也就是"倒數第二難"的case
2．仍是N步，與case N一樣難
同理，你轉一個R，或是轉一個F'，也是一樣的
(理由就很簡單啦
如果你轉一個U之後，發現此時只需要再k步能完成，那表示case N只要k+1步
而case N已證明最少要N步才能完成
所以k不可能超過N，不然這個case不就比case N更複雜了嗎
k也不能少於N-1，不然case N就不需要花到N步就能完成了)
因此，最複雜的case，肯定不只一個，而且還有一大群
不過，這一大群cases當中，一定有特殊的"共同點"
只要找出此共同點，也許就能破解了吧
: 另外一個是我最近自己想到的
: MIT 有一位天才教授叫 Erik Demaine，目前 24 歲吧~
: 搞出了一個摺紙的領域，給他一張 2D 的紙
: 他可以用電腦算出該怎麼摺，可以摺出任何你想要的 3D model
: 這個超炫，原理用到了組合數學
: 我就在想，有沒有可能把這個東西推廣到 3D 上面
: 給你一個 cube，有沒有辦法對這個 cube 的內部做切割
: 然後產生出另一個不同的 model 出來，但還是可以轉~~
: 我妹家幫我想想吧 Orz..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.203.19