求解游戏"Globs"/flood填充/“FloodIt”的算法和数据结构

Question

提出了求解游戏全局(http://www.deadwhale.com/play.php?game=131)的算法和数据结构。用一种古怪的方式很有趣。

状态您的方法的时空复杂性(大-O)，以N表示，网格的大小(N>=14)。--高效率的低复杂度算法是首选。

(MatrixFrog正确地指出这个游戏也被称为FloodIt，Smashery在3个月前在他引用的链接中给出了一个解决方案。大家都建议修剪/贪婪，只要向前看一看，这就给出了次优解。)

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

显然，有很多方法可以分解这个问题，使用14x14网格进行递归回溯的默认选择是一个可行的竞争者；这会给其他类型的数据结构带来什么好处呢？A*？不要被最优性所困扰，我想知道是否有一个“足够好”的算法。

(我认为这可能是一个有趣的项目，编码一个机器人，得到愚蠢的高分。虽然我的3.5E+12得分都是靠我自己的肉制品。)

Answer 1

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

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

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

不过，也有一些行之有效的办法。在这个帖子中的其他人已经发布了关于仅仅以剩余颜色的数量作为估计值，这是可以接受的，因为它不能过高估计(你必须至少对每一个剩余的颜色改变一次，而不是主要的“洪水”区域的一部分)。这个启发的问题是它估计不了实际的距离。举个例子，第一步通常有颜色数的估计，6。它通常扩展成两个动作，每个动作的估计值一般是7，等等。以这5个层次为例，对于10x10的棋盘大小，大多数leafs的估计值为11。这种启发式基本上是一种先搜索宽度的实现，直到你到达目标4或5步内。这不是很有效，在我自己的测试中，指数运行在9左右，这通常需要14步左右的解决方案。应该指出的是，我的解决方案是非常高的水平，但并没有采取太大的注意，以加快速度。

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

然而，在右下角成为淹水区域的一部分后，这种启发式就有崩溃的倾向，因此最终的结果是最大(右下角最小步数，颜色数目仍然不是主洪水的一部分)。通过我的高级实现，这终于能够在一秒钟内实现一些非常大的板大小。

我会把记录留给你。

Answer 2

考虑到固定的启动状态和有限的移动次数，我认为您可以完全探索一个决策树。对于每一轮，只有5种可能的移动和浪费的移动(选择一种颜色，不会‘地球’任何邻居-任何任何时候都可以消除，因为树是建立。一旦建立了决策树，我认为您可以探索每条路径的点值，但是如果需要更多的优化，A*肯定会使您接近。

对于每一轮，我将使用基本状态作为未全局位置状态的位数组矩阵(因为颜色在全局位置不再重要，您可以通过省略颜色位来节省状态数据结构上的内存)和每个可能的决策的点值。然后你的A*，或宽度优先算法，就可以最大化的路径值作为正常。保存路径，一旦分析完成，就进行所有确定的移动。

Answer 3

另一种方法是使用遗传算法。由于任何(部分)解决方案都由一组颜色组成，所以它很好地翻译成一个基因。一个适应度函数可以是连接分量的4倍，减去使用的总颜色数(基因长度)。

我用一个非常没有优化的算法在10×10板上试用了这个方法，并且很快就得到了一个简短的解决方案。我并不认为它是最优的，但如果有足够的时间，基因突变过程中的随机性将确保最终得到一个最优解。