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

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

看板Prob_Solve (計算數學 Problem Solving)作者subset (子集合)時間6年前 (2017/08/16 10:39)推噓8(8推 0噓 22→)

留言30則, 5人參與討論串1/1

※ [本文轉錄自 Python 看板 #1PawwIPf ] 作者: subset (子集合) 看板: Python 標題: [問題] 搜尋演算法的問題時間: Wed Aug 16 10:31:43 2017 最近在玩一個小遊戲叫做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 ) ================== 以下補充一下數學模型 ==================== There are 7 colors: R,G,B,Y,M,C,W Type 1. 三原色：Red, Green, Blue Type 2. Combined 2 colors: Yellow (R+G), Magenta (R+B), Cyan(G+B) Type 3. White is original color. White也可以是三原色相加 (R+G+B) Chessboard is a 6 x 4 matrix: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 圖形一: 正三角形可以表示成matrix: (position 0) [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 圖形一選轉第一個60度，則變成 (Position 1) [[0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 圖形一塗上紅色變成: [[0, 0, 0, 0], [R, R, R, R], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 圖形二: 鑽石型: [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 1], [0, 0, 0, 1], [0, 1, 0, 1]] 總共會有16種圖形，都可以用類似的matrix表示，這裡就不一一列出。每種圖案都只能被用一次，也可以選擇不使用。因此每個圖案(形狀)的選擇是 6(個方向) x 3(種顏色) + 1(不選這個圖案) = 19 假設答案是在底部的藍色正三角形: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [B, B, B, B], [0, 0, 0, 0], [0, 0, 0, 0]] 就是圖形一的Position 3, Color B，加上其他圖形的Position 0, Color W組成的。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.156.158 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1502850706.A.669.html ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: subset (101.139.156.158), 08/16/2017 10:39:34

→

subset

08/16 10:40, , 1^F

08/16 10:40, 1^F

推

FRAXIS

08/16 11:16, , 2^F

08/16 11:16, 2^F

→

FRAXIS

08/16 11:17, , 3^F

08/16 11:17, 3^F