比贪心算法更好的泡泡破坏者游戏求解器？
为了锻炼思维，我决定尝试解决一个在很多手机上都能找到的泡泡破坏者游戏，下面这个链接就是一个例子：泡泡破坏游戏
- 这个随机生成的(N,M,C)棋盘有N行M列，里面有C种颜色的泡泡。
- 游戏的目标是通过选择泡泡组合来获得最高分。
- 泡泡组合是指两个或更多相同颜色的泡泡，它们在横向或纵向上是相邻的。对角线上的泡泡不算。
- 当选择一个组合后，这些泡泡会消失，空出来的位置会先由上面的泡泡填补，也就是向下移动，然后再由右边的泡泡填补。
- 一个泡泡组合的得分是 n * (n - 1)，其中 n 是这个组合中泡泡的数量。
第一个算法是一个简单的穷举递归算法，它会逐行逐列地遍历棋盘，选择泡泡组合。一旦选择了组合，就会创建一个新的棋盘，然后尝试解决这个新棋盘，继续递归下去。
我使用的一些思路包括规范化的备忘录技术。一旦棋盘被解决，我们就会把棋盘和最佳得分存储在一个备忘录表中。
我创建了一个Python原型，显示一个(2,15,5)的棋盘需要8859个棋盘来解决，大约花费3秒钟。而一个(3,15,5)的棋盘则需要12,384,726个棋盘，耗时50分钟在服务器上。解决的速度大约是每秒3千到4千个棋盘，随着备忘录搜索时间的增加，速度会逐渐下降。备忘录表的大小增长到5,692,482个棋盘，访问次数达到6,713,566次。
除了穷举搜索，还有什么其他方法可以获得高分呢？
我没有看到明显的分治方法。但似乎朝着更大泡泡组合的方向发展是一个可行的思路。
感谢David Locke分享的论文链接，里面提到了一种使用固定深度前瞻启发式的窗口求解器。
7 个回答
在我的国际象棋程序中，我用了一些想法，这些想法可能也能适用于这个问题。
移动排序。首先找出所有可能的移动，把它们放在一个列表里，然后根据某种规则对它们进行排序。把“好”的移动放在前面，把“差”的移动放在后面。例如，可以根据棋子数量来判断（偏向中等数量的棋子），或者根据相邻颜色、棋子组等的数量来排序。
迭代加深。与其进行纯粹的深度优先搜索，不如在达到一定深度后停止搜索，然后用某种规则来评估结果。接着优先搜索那些“更好”的移动。
剪枝。不要搜索那些看起来“明显”不好的移动，这也是根据某种规则来判断的。这可能会有风险，导致你找不到最优解，但根据你的规则，你很可能会更早找到一个不错的解。
哈希表。没必要存储你遇到的每一个棋盘，只需记住一定数量的棋盘，并覆盖掉旧的棋盘。
你可以把这个问题看作是在图上寻找最短路径的问题。详细信息可以参考这个链接：http://en.wikipedia.org/wiki/Shortest_path_problem
我会尝试使用A*算法，启发式方法可以考虑岛屿的数量。
根据这篇论文，判断你是否能把棋盘清空（这和你想解决的问题有关）是一个NP完全的问题。这并不是说你找不到好的算法，只是说你可能找不到一个高效的算法。