贊助廠商

娛樂城推薦

首頁

電腦與網際網路/其他:電腦列表

計算數學 Problem Solving- UVa 11007 魔術方塊 最少步驟解

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 11 62 273 1204 5345 22566 89697 330588 8700729 36050810 93050811 135085212 78253613 9028014 276所以我就將這 3674160 利用 BFS 由上到下暴力列舉出來列舉方法:以 Front、Right、Bottom 三面相交的那塊方塊為基準點可以做的轉動只有 6 種 : U Up L Lp B BpU : 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--
  • 發問日期:2021-06-09 16:40:12

友站連結