泡泡破坏者游戏解决者比贪心更好？

Question

对于心理锻炼,我决定尝试解决在许多手机上发现的泡泡破坏者游戏以及这里的一个例子:泡泡破坏游戏

• 随机(N,M,C)板包括具有C颜色的N行×M列
• 目标是通过选择最终导致最高分数的泡沫组序列来获得最高分
• 气泡组是在x或y方向上彼此相邻的2个或更多相同颜色的气泡.对角线不计算在内
• 挑选一组时,气泡消失,任何孔首先从上方充满气泡,即向下移动,然后通过向右移动填充任何孔
• 气泡组分数= n*(n - 1)其中n是气泡组中气泡的数量

第一种算法是一种简单的穷举递归算法,它通过逐行和逐列选择气泡组来探索逐行扫描.一旦选择了泡泡组,我们就会创建一个新的电路板并尝试解决该电路板,递归下降

我使用的一些想法包括规范化的记忆.一旦电路板解决了,我们将电路板和最佳分数存储在记忆表中.

我在python中创建了一个原型,它显示了一个(2,15,5)板需要8859块板才能在大约3秒内解决.一台(3,15,5)板在50分钟内在服务器上占用12,384,726块板.求解速率约为3k-4k板/秒,随着记忆搜索需要更长时间逐渐减少.记忆表增长到5,692,482个板,达到6,713,566次.

除了详尽的搜索之外,还有哪些其他方法可以获得高分？

我没有看到任何明显的分裂和征服方式.但趋向于越来越大的泡沫团体似乎是一种方法

感谢David Locke发布了一个纸质链接,该链接在一个使用恒定深度前瞻启发式的窗口求解器之上进行讨论.

Answer 1

根据本文,确定是否可以清空电路板(与您要解决的问题相关)是NP-Complete.这并不意味着你将无法找到一个好的算法,它只是意味着你可能找不到一个有效的算法.