[問題] 搜尋演算法的問題

作者: subset (子集合)   2017-08-16 10:31:43
最近在玩一個小遊戲叫做colorcube,(本周免費app,非廣告XD)
https://itunes.apple.com/tw/app/colorcube/id1076402133
它的玩法很簡單,就是每個圖案可以旋轉六個方向,顏色可以選擇紅、綠、藍 (三原色)
圖案交疊的部分會變成兩個顏色的相加,例如紅 + 綠 = 黃
因此每個圖案(形狀)的選擇是 6(個方向) x 3(種顏色) + 1(不選這個圖案) = 19
在一開始的關卡圖案只有4種選擇,因此hypothesis set只有19 ^ 4其實跑很快。
但是我卡關的題目已經有16種圖案,用單純的深度搜尋或廣度搜尋會有19 ^ 16種組合,
根本跑不完。
是可以用一些heuristic rule去做一些刪減,
例如答案是紅色的方塊,不能被三原色的另外兩種方塊覆蓋。
不過單純這樣去做深度搜尋還是會跑太久。
以前學的演算法都忘光光了,是否可以推薦適合的演算法?
( P.S. 找不到演算法的版,不知道在這裡問有沒有人回答QQ )
作者: joj4211 (小學弟)   2017-08-19 03:17:00
Prob_Solve版
作者: s89227 (Kei)   2017-08-16 18:37:00
作者: flarehunter (Range)   2017-08-16 18:40:00
可以先求三原色分別的圖案再暴搜嗎
作者: subset (子集合)   2017-08-17 08:23:00
回1F 這不是最短路徑問題吧
作者: s89227 (Kei)   2017-08-17 18:52:00
貼錯網址了,我只是想說貼這個站你可以進去看裡面的演算法有哪些你覺得適合可以嘗試的結果不寫心貼到裡面內容的網址而不是首頁Orz

Links booklink

Contact Us: admin [ a t ] ucptt.com