作者nicknick0630 (NICK)
看板Prob_Solve
標題[問題] UVa 11007 魔術方塊 最少步驟解
時間Tue May 21 00:09:53 2019
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
推 achicn3: 可以問楊老師 XD 05/21 01:55
推 FRAXIS: 不能把 3674160 個狀態找個 encoding 法 + perfect hash? 05/21 11:58
推 FRAXIS: 而且你真的需要 unordered_multimap 嗎？ 05/21 12:15
推 fatcat8127: 雙向BFS嗎? 05/21 13:35
→ nicknick0630: 回 F 大 ：當然如果可以找到perfect hash 應該就可 05/21 16:03
→ nicknick0630: 以解決問題了，只是這樣hash的方法的我真的設計不出 05/21 16:03
→ nicknick0630: 來啊QQ 05/21 16:03
→ nicknick0630: 回 fatcat 大：我有試過，不過同樣也要去檢查有沒 05/21 16:04
→ nicknick0630: 有規則外的重複狀態，所以還是有一樣的問題 05/21 16:04
推 FRAXIS: 應該不用設計吧 因為狀態數是固定的 只要隨機試幾個 05/21 21:10
→ FRAXIS: 自然就會找的到 perfect hash? 05/21 21:11
感謝大大XD
原來有這東西，不過我還要研究一下 ...
推 firejox: IDDFS ? 05/21 21:22
推 oToToT: 從解狀態跟待解狀態兩邊同時開始BFS/IDDFS會較佳，至少上 05/21 22:10
→ oToToT: 禮拜某個比賽這樣會過@@ 05/21 22:10
那這樣是不是也會需要一個 Table 呢
就等同於我的解法一，只是變成是點到為止的感覺XD
我來試試看，感謝你~
※ 編輯: nicknick0630 (140.117.183.79), 05/21/2019 22:45:09
推 firejox: 如果擔心記憶體爆掉 就把資料壓在72個bit就好 05/21 23:03
→ firejox: 或許可以用A*，大概是計算頂點的曼哈頓距離之類的 05/21 23:20
推 idiont: 雙向BFS可以過 剛剛測試過了 跑了0.720秒 05/21 23:30
→ idiont: 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
推 idiont: 一格有6種情況 24格就6^24種情況 不過實際上大部分都不存 05/22 01:26
→ idiont: 在就是了 05/22 01:26
→ idiont: 然後一個方塊會有24種擺放方式 我是每種都算出他的hash值 05/22 01:29
→ idiont: 取最小的 05/22 01:29