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

看板 Prob_Solve
作者
時間
留言 24則留言,8人參與討論
推噓 11  ( 11推 0噓 13→ )
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
1Fachicn3: 可以問楊老師 XD 05/21 01:55
2FFRAXIS: 不能把 3674160 個狀態找個 encoding 法 + perfect hash? 05/21 11:58
3FFRAXIS: 而且你真的需要 unordered_multimap 嗎? 05/21 12:15
4Ffatcat8127: 雙向BFS嗎? 05/21 13:35
5Fnicknick0630: 回 F 大 :當然如果可以找到perfect hash 應該就可 05/21 16:03
6Fnicknick0630: 以解決問題了,只是這樣hash的方法的我真的設計不出 05/21 16:03
7Fnicknick0630: 來啊QQ 05/21 16:03
8Fnicknick0630: 回 fatcat 大:我有試過,不過同樣也要去檢查有沒 05/21 16:04
9Fnicknick0630: 有規則外的重複狀態,所以還是有一樣的問題 05/21 16:04
10Fcutekid: https://github.com/MeepMoop/py222 ←不知道有幫助嗎 05/21 17:48
11FFRAXIS: 應該不用設計吧 因為狀態數是固定的 只要隨機試幾個 05/21 21:10
12FFRAXIS: 自然就會找的到 perfect hash? 05/21 21:11
感謝大大XD 原來有這東西,不過我還要研究一下 ...
14Ffirejox: IDDFS ? 05/21 21:22
15FoToToT: 從解狀態跟待解狀態兩邊同時開始BFS/IDDFS會較佳,至少上 05/21 22:10
16FoToToT: 禮拜某個比賽這樣會過@@ 05/21 22:10
那這樣是不是也會需要一個 Table 呢 就等同於我的解法一,只是變成是點到為止的感覺XD 我來試試看,感謝你~ ※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 22:45:09
17Ffirejox: 如果擔心記憶體爆掉 就把資料壓在72個bit就好 05/21 23:03
18Ffirejox: 或許可以用A*,大概是計算頂點的曼哈頓距離之類的 05/21 23:20
19Fidiont: 雙向BFS可以過 剛剛測試過了 跑了0.720秒 05/21 23:30
20Fidiont: 6^24 < 2^63 所以可以靠long long存就好了 而且不會碰撞 05/21 23:38
我剛剛也有用雙向 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
21Fidiont: 一格有6種情況 24格就6^24種情況 不過實際上大部分都不存 05/22 01:26
22Fidiont: 在就是了 05/22 01:26
23Fidiont: 然後一個方塊會有24種擺放方式 我是每種都算出他的hash值 05/22 01:29
24Fidiont: 取最小的 05/22 01:29