作者subset (子集合)
看板Prob_Solve
标题Fw: [问题] 搜寻演算法的问题
时间Wed Aug 16 10:39:34 2017
※ [本文转录自 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://webptt.com/cn.aspx?n=bbs/Python/M.1502850706.A.669.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: subset (101.139.156.158), 08/16/2017 10:39:34
1F：→ subset: 这个问题感觉应该在这个版问，转过来。 08/16 10:40
2F：推 FRAXIS: 建议你最好把玩法写清楚 最好用数学来表示 08/16 11:16
3F：→ FRAXIS: 不然除非有人真的下载来玩 才能回答你问题 08/16 11:17
4F：→ moebear: 我刚刚玩了一下 玩法大概是给定目标图形及颜色 然後利用 08/16 11:56
5F：→ moebear: 给定的图形去组合成目标图 小图形可以转60度*5 08/16 11:57
6F：→ subset: 我晚点再用数学符号描述详细点 08/16 11:58
7F：→ moebear: 小图形的颜色有三种，可自选 08/16 11:58
※ 编辑: subset (39.8.197.20), 08/16/2017 12:41:58
※ 编辑: subset (39.8.197.20), 08/16/2017 12:43:09
8F：→ subset: 补充一下抽象化题目成二维矩阵的方式 08/16 12:45
9F：推 JameC: Android 没有这个游戏QQ，光看模型还真搞不懂这游戏在干嘛 08/16 19:18
10F：推 FRAXIS: 如果选了两个图形 不同颜色 但是有 overlap， overlap 08/16 20:51
11F：→ FRAXIS: 的颜色是按照你定义的加法？ 那如果有三个图形的 overlap 08/16 20:51
12F：→ FRAXIS: 加法是怎麽定义的？ 08/16 20:51
13F：→ FRAXIS: 像Yellow + Red 是什麽？ 08/16 20:52
14F：→ moebear: 应该还是yellow? 08/16 21:17
15F：推 FRAXIS: 那 Yellow + Cyan 是什麽？ 08/16 21:29
16F：→ moebear: 大概会变白色? 08/16 22:02
17F：→ subset: 一个颜色不管重叠几次都算一次 Y+R=R+G+R=R+G=Y 08/16 22:37
18F：→ subset: Y+C=R+G+G+B=R+B+G=W 08/16 22:39
19F：推 FRAXIS: Yellow + White 是 Yellow 还是 White? 08/17 08:07
20F：→ subset: 如果W是原始的白色Y+W=Y; 若W=RBG组成的 那Y+W=W 08/17 08:20
21F：推 FRAXIS: 但是原始的白色跟 RBG 的白色可以 match.. 这地方有点麻烦 08/17 08:44
23F：→ FRAXIS: 你都试过了吗？ 08/17 08:51
24F：→ subset: 感谢你!! 我先朝Constraint Satisfaction Problems去读 08/18 14:24
25F：→ yvb: match 不是问题, pieces 和 puzzle 的 colors 用不同数值, 08/18 20:15
26F：→ yvb: 且使用 bitwise AND operator, 不为 0 即 match. 08/18 20:15
27F：→ yvb: PIECE_*: R=1 G=2 B=4 W=8 C=G|B M=B|R Y=R|G 08/18 20:16
28F：→ 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 08/18 20:16
29F：→ yvb: 当然, pieces 的颜色加成, 即使用 bitwise OR operation. 08/18 20:23
30F：推 FRAXIS: 我说match有点麻烦是因为我想写出 integer linear program 08/18 21:30