data-structures - 解决游戏的算法和数据结构 "Globs"/洪水填充/"FloodIt"

Question

建议解决游戏 Glob ( http://www.deadwhale.com/play.php?game=131 ) 的算法和数据结构。它以一种极客的方式非常有趣。

以 N 的形式说明您的方法的时空复杂度 (big-O) ，网格的大小(N>=14)。 具有低复杂性的足够好的有效算法是首选。

(MatrixFrog 正确地指出这个游戏也被称为 FloodIt，并且 Smashery 在 3 个月前在他引用的链接中给出了一个解决方案。你们所有的家伙都建议修剪/贪婪只有 1 个前瞻，这给出了次优的解决方案。)

游戏会生成一个由 nxn 个节点组成的随机方形网格，其中每个节点的颜色都是六种颜色中的一种(Grn=1、Ylw=2、Red=3、Blu=4、Pur=5、Orn=6)。级别 1 有 9x9 网格，然后每级增加 n，最多 14 个。
每个级别您最多可以进行 25 回合，否则您将失败。
在每一回合中，您可以选择将左上角节点更改为的颜色，例如Grn->Red，这样新颜色的任何连接的相邻(水平/垂直)节点都被同化为一个形状，每个同化的节点 1 pt 将添加到您的分数中。
评分目标是在尽可能少的回合内完成每个网格，例如如果你在 16 回合内完成，那么你的 9 个未使用的 Action => 2*9 乘数乘以你的总得分。

显然，有很多方法可以分解它，而使用 14x14 网格的递归回溯的默认选择是一个可行的竞争者；
这适用于哪些其他类型的数据结构？一种* ？
不要卡在最优性上，我想知道是否有一个“足够好”的算法。

(我认为编写机器人代码并获得愚蠢的高分可能是一个有趣的项目。
虽然我的肉件自己考了3.5E+12。)

Answer 1

这个游戏真的引起了我的兴趣，所以我花了几天的时间来研究它。

我注意到的第一件事是，很容易证明在第一个棋盘(在某些情况下可能是 2 个棋盘)之后，提高分数的最快方法是使用乘数。正因为如此，我建立了一个系统，目标是用最少的步骤解决每个板。我开始想使用 A*，因为它通常是为这些类型的搜索问题而构建的……但是，这个问题仍然是个麻烦事。

在谈论 A* 时，它的有效性确实归结为您对启发式估计的选择。您越接近猜测实际距离，为达到目标而必须扩展的节点就越少。对于这个问题，我经历了很多估计的想法，但大多数都违反了 A* 规则，即不能高估实际距离，否则会破坏 A* 的最优性。

然而，有一些工作。该线程中的其他人发布了关于仅将剩余颜色的数量作为估计值的帖子，这是可以接受的，因为它不能高估(对于不属于主要“洪水”区域的每种剩余颜色，您必须至少更改一次颜色。这种启发式的问题是它对实际距离的估计很差。以第一步为例，它通常对颜色数量进行估计，为 6。它通常扩展为 2 步，每个步通常估计为 7 ，依此类推。以这 5 个级别为深度，对于 10x10 的棋盘大小，大多数叶子的估计值为 11。这种启发式方法基本上是广度优先搜索的实现，直到您在 4 或 5 步内到达目标。这不是很有效，在我自己的测试中，指数在棋盘大小 9 附近运行，这通常需要在解决方案中进行大约 14 次移动。应该注意的是，我的解决方案非常高水平，但是并没有太注意指定编好了。

问题是 A* 只有在每一步都对整体解决方案的实际距离进行显着改进时才真正有效。直接看问题，你可能不会找到一个很好的启发式方法，它可以做得比这更好，而不会高估成本。但是，如果您将问题转化为另一个问题，则更好的启发式方法会突然出现。启发式“剩余颜色数”正在回答这个问题，剩余的最小可能移动数是多少。为了回答这个问题，我问自己“黑板上的哪个位置需要最多的步数才能到达”？对于我的启发式方法，我最终确定了“到右下角有多少步”的答案。这很容易通过运行另一个 A* 搜索来实现，该搜索更像是查找 map 方向，然后计算解决方案中的步骤数。我意识到这是板上的任意点可供选择，但是它在测试中运行良好，并且在每个剩余点上运行 A* 在我的单处理器测试机器上花费了相当多的时间。

然而，在右下角成为泛滥区域的一部分后，仅此启发式就有崩溃的趋势，因此最终结果是 MAX(右下角最小步长，剩余的颜色数量不属于主泛滥的一部分)。通过我的高级实现，这终于能够在一秒钟内实现一些非常大的电路板尺寸。

我将把记录设置留给你。