PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] UVa 11007 魔術方塊 最少步驟解

看板Prob_Solve (計算數學 Problem Solving)作者 (NICK)時間5年前 (2019/05/21 00:09), 5年前編輯推噓11(11推 0噓 13→)
留言24則, 8人參與, 5年前最新討論串1/1
UVa 連結 : https://reurl.cc/8OKXo 題目簡易說明 這題是要解一個 2x2x2 的二階魔術方塊 ( 6 面、6 顏色 ) 會給定一個魔術方塊的狀態 然後要找出可以還原魔術方塊的最少步驟是多少 輸入面的順序為 : Top , Front, Right , Bottom, Back , Left 且每面的初始色 : White, Red , Yellow, Blue , Orange, Green 我的解法一 參考維基百科 : https://reurl.cc/Ea3Qn 二階魔方最有只有 3674160 種狀態 而且最多只要 14 個步驟就能將方塊還原 以下是需要轉動步驟的狀態數: 所需步驟 狀態數量 0 1 1 6 2 27 3 120 4 534 5 2256 6 8969 7 33058 8 870072 9 360508 10 930508 11 1350852 12 782536 13 90280 14 276 所以我就將這 3674160 利用 BFS 由上到下暴力列舉出來 列舉方法: 以 Front、Right、Bottom 三面相交的那塊方塊為基準點 可以做的轉動只有 6 種 : U Up L Lp B Bp U : Top 那面面對自己做 順 時針旋轉 Up : Top 那面面對自己做 逆 時針旋轉 L : Left 那面 B : Back 那面 就從步驟 0 開始 ( 方塊還原狀態 ) 依序做 6 種轉動，並得到步驟 1 的方塊狀態 直到步驟 14 其中可以用一些規則去避免重複 ( 不然 6^14 = 7百多億 ) 1. L L L = Lp ( 轉 270度 = 轉 -90度 ) 2. 若上一步驟是 L，則這一步驟就不能為 Lp ( 做白工 ) 3. L L = Lp Lp ( 我選擇遇到 Lp Lp 就不要做 ) 但是除了以上三種，還是會有很多重複是抓不到的 所以我將每種狀態放入 Hash Table 中 ( C++ unordered_multimap ) key : 根據方塊的狀態 (每一面顏色) 所 "亂湊" 出來的數值 value : 該方塊的資訊 (狀態、還原所需步驟等等) 每新算出一種狀態 ( 不違反上面 3 個規則 ) 還要去 Hash Table 中檢查有沒有重複，沒有的話就同樣丟入 Table 中 最後 只要把題目輸入的方塊狀態同樣依據上面算 key 的方法算出來 再去 Hash Table 找，並得到該方塊的資訊，就可以知道最短步驟 缺點 這樣太慢，UVa 時限是 3 秒，我光是跑完列舉就要大概 10 秒了 其中大部分的時間都是花在 Hash Table 查找 ( 因為 hash 會碰撞，所以只能用 equal_range(key) 去查找，但還是剖慢) 我的解法二 為了避免掉 Hash Table 查找 所以直接對題目給的方塊狀態去做暴力 BFS 不過這次就不使用 Hash Table 來儲存找到的狀態 也不檢查除了上面 3 個規則以外是否還有重複的 這樣會比較快 但是因為數量增長太大，也是會很慢而且記憶體還會爆掉 問題 請問各位大大有沒有甚麼更快的做法呢? UVa 上的數據很多人都可以在 1 秒內 AC，但我一職 TLE ... 或是我還有哪裡可以再加快的呢? 謝謝 附上寫得不好的程式碼 ( 解法一 ) https://pastebin.com/embed_iframe/c2e3idba -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.183.79 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1558368596.A.153.html ※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 00:11:47 ※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 00:13:39 ※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 00:56:40
推
05/21 01:55, 5年前 , 1F
可以問楊老師 XD
05/21 01:55, 1F
推
05/21 11:58, 5年前 , 2F
不能把 3674160 個狀態找個 encoding 法 + perfect hash?
05/21 11:58, 2F
推
05/21 12:15, 5年前 , 3F
而且你真的需要 unordered_multimap 嗎？
05/21 12:15, 3F
推
05/21 13:35, 5年前 , 4F
雙向BFS嗎?
05/21 13:35, 4F
→
05/21 16:03, 5年前 , 5F
回 F 大 ：當然如果可以找到perfect hash 應該就可
05/21 16:03, 5F
→
05/21 16:03, 5年前 , 6F
以解決問題了，只是這樣hash的方法的我真的設計不出
05/21 16:03, 6F
→
05/21 16:03, 5年前 , 7F
來啊QQ
05/21 16:03, 7F
→
05/21 16:04, 5年前 , 8F
回 fatcat 大：我有試過，不過同樣也要去檢查有沒
05/21 16:04, 8F
→
05/21 16:04, 5年前 , 9F
有規則外的重複狀態，所以還是有一樣的問題
05/21 16:04, 9F
推
05/21 17:48, 5年前 , 10F
https://github.com/MeepMoop/py222 ←不知道有幫助嗎
05/21 17:48, 10F
推
05/21 21:10, 5年前 , 11F
應該不用設計吧 因為狀態數是固定的 只要隨機試幾個
05/21 21:10, 11F
→
05/21 21:11, 5年前 , 12F
自然就會找的到 perfect hash?
05/21 21:11, 12F
→
05/21 21:11, 5年前 , 13F
05/21 21:11, 13F
感謝大大XD 原來有這東西，不過我還要研究一下 ...
推
05/21 21:22, 5年前 , 14F
IDDFS ?
05/21 21:22, 14F
推
05/21 22:10, 5年前 , 15F
從解狀態跟待解狀態兩邊同時開始BFS/IDDFS會較佳，至少上
05/21 22:10, 15F
→
05/21 22:10, 5年前 , 16F
禮拜某個比賽這樣會過@@
05/21 22:10, 16F
那這樣是不是也會需要一個 Table 呢 就等同於我的解法一，只是變成是點到為止的感覺XD 我來試試看，感謝你~ ※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 22:45:09
推
05/21 23:03, 5年前 , 17F
如果擔心記憶體爆掉 就把資料壓在72個bit就好
05/21 23:03, 17F
→
05/21 23:20, 5年前 , 18F
或許可以用A*，大概是計算頂點的曼哈頓距離之類的
05/21 23:20, 18F
推
05/21 23:30, 5年前 , 19F
雙向BFS可以過 剛剛測試過了 跑了0.720秒
05/21 23:30, 19F
→
05/21 23:38, 5年前 , 20F
6^24 < 2^63 所以可以靠long long存就好了 而且不會碰撞
05/21 23:38, 20F
我剛剛也有用雙向 BFS 寫出來了，快很多( oT 大說的 2 種狀態各自 BFS ) 只是 UVa 網站掛掉還不知道可以跑多快XD 不過看起來我的寫法應該和你不太一樣 想請問你一下你的資料是怎麼存的呢? ( 6^24 是甚麼意思 ) 我的方法是: 6個顏色就是6種狀態，需要 4 個 bits 一面有 4 個顏色 --> 24 bits 一面 方塊有 6 個面 --> 最少 144 bits 一個方塊的狀態 不過我是用 6 個 int 去存的 ※ 編輯: nicknick0630 (140.117.183.79), 05/22/2019 01:10:34
推
05/22 01:26, 5年前 , 21F
一格有6種情況 24格就6^24種情況 不過實際上大部分都不存
05/22 01:26, 21F
→
05/22 01:26, 5年前 , 22F
在就是了
05/22 01:26, 22F
→
05/22 01:29, 5年前 , 23F
然後一個方塊會有24種擺放方式 我是每種都算出他的hash值
05/22 01:29, 23F
→
05/22 01:29, 5年前 , 24F
取最小的
05/22 01:29, 24F
‣ 更多 nicknick0630 的文章
文章代碼(AID): #1Suj5K5J (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 nicknick0630 的文章
文章代碼(AID): #1Suj5K5J (Prob_Solve)