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

[subset (子集合)]

※ [本文轉錄自 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: 這個問題感覺應該在這個版問，轉過來。
推 FRAXIS: 建議你最好把玩法寫清楚 最好用數學來表示
→ FRAXIS: 不然除非有人真的下載來玩 才能回答你問題
→ moebear: 我剛剛玩了一下 玩法大概是給定目標圖形及顏色 然後利用
→ moebear: 給定的圖形去組合成目標圖 小圖形可以轉60度*5
→ subset: 我晚點再用數學符號描述詳細點
→ moebear: 小圖形的顏色有三種，可自選
※ 編輯: subset (39.8.197.20), 08/16/2017 12:41:58
※ 編輯: subset (39.8.197.20), 08/16/2017 12:43:09
→ subset: 補充一下抽象化題目成二維矩陣的方式
推 JameC: Android 沒有這個遊戲QQ，光看模型還真搞不懂這遊戲在幹嘛
推 FRAXIS: 如果選了兩個圖形 不同顏色 但是有 overlap， overlap
→ FRAXIS: 的顏色是按照你定義的加法？ 那如果有三個圖形的 overlap
→ FRAXIS: 加法是怎麼定義的？
→ FRAXIS: 像Yellow + Red 是什麼？
→ moebear: 應該還是yellow?
推 FRAXIS: 那 Yellow + Cyan 是什麼？
→ moebear: 大概會變白色?
→ subset: 一個顏色不管重疊幾次都算一次 Y+R=R+G+R=R+G=Y
→ subset: Y+C=R+G+G+B=R+B+G=W
推 FRAXIS: Yellow + White 是 Yellow 還是 White?
→ subset: 如果W是原始的白色Y+W=Y; 若W=RBG組成的 那Y+W=W
推 FRAXIS: 但是原始的白色跟 RBG 的白色可以 match.. 這地方有點麻煩
推 FRAXIS: https://cs.stackexchange.com/q/47870 這些 heuristic
→ FRAXIS: 你都試過了嗎？
→ subset: 感謝你!! 我先朝Constraint Satisfaction Problems去讀
→ yvb: match 不是問題, pieces 和 puzzle 的 colors 用不同數值,
→ yvb: 且使用 bitwise AND operator, 不為 0 即 match.
→ yvb: PIECE_*:  R=1   G=2   B=4   W=8       C=G|B M=B|R Y=R|G
→ yvb: PUZZLE_*: R=1|8 G=2|8 B=4|8 W=1|2|4|8 C=G|B M=B|R Y=R|G
→ yvb: 當然, pieces 的顏色加成, 即使用 bitwise OR operation.
推 FRAXIS: 我說match有點麻煩是因為我想寫出 integer linear program