求解游戏“globs”/“flood fill/”flood it“的算法和数据结构

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

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

当谈论一个*时,它的有效性实际上归结为您选择的启发式估计。越接近于猜测实际距离,为达到目标而必须展开的节点就越少。对于这个问题,我讨论了一些估计的方法,但是大多数方法都违反了A*规则,即不能过度估计实际距离,否则就破坏了A*的最优性。

不过,也有一些是可行的。这条线中的其他人已经发布了仅以剩余颜色的数量作为估计,这是可以接受的,因为它不能过度估计(您必须为每个剩余颜色至少更改一次颜色,而不是主“洪水”区域的一部分)。这种启发式方法的问题在于,它对实际距离的估计非常差。以第一步为例,它通常估计颜色的数量,6。它通常扩展为2个动作,每个动作通常有7个估计值,依此类推。以这5层为例,对于一个10x10的板子,大多数叶子估计有11层。这种启发式搜索基本上是一种广度优先搜索的实现,直到您从目标移动到4到5步之内。这不是很有效,在我自己的测试中,指数运行在9号电路板上,这通常需要在解决方案中进行14次移动。应该注意的是,我的解决方案是非常高的水平,但没有采取太多的措施来加快速度。

问题是,只有当每个步骤对整体解决方案的实际距离进行显著的改进时,*才是真正的好方法。直接看问题,你可能找不到一个好的启发式方法,它可以在不过度估计成本的情况下做得更好。然而,如果你把问题转化成另一个问题,更好的启发式方法就会跳到你身上。启发式的“剩余颜色数”正在回答这个问题,剩余的最小可能移动数是多少。为了回答这个问题,我问自己,“在董事会的哪个位置需要达到最大的步骤数”?我最终决定用启发式的方法回答“到底有多少个步骤是在右下角”。通过运行另一个A*搜索(更像是查找地图方向,然后计算解决方案中的步骤数),这是相当容易实现的。我意识到这是板上要选择的任意点,但是它在测试中工作得很好,在剩余的每个点上运行一个*在我的单处理器测试机上花费了相当长的时间。

然而,这种启发式方法在右下角成为淹没区域的一部分后有倒塌的趋势,因此最终的结果是max(右下角最小步数,剩余的颜色数不是主洪水的一部分)。通过我的高级实现,这最终能够在不到一秒钟的时间内实现一些非常大的电路板尺寸。

我会把记录留给你。

另一种方法是使用遗传算法。 因为任何(部分)解决方案都包含一系列颜色,所以它很好地转化为一个基因。一个适应度函数可以是连接成分减去所用颜色总数(基因长度)的4倍。

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

考虑到固定的启动状态和有限的移动次数,我认为您可以充分探索决策树。对于每一轮,只有5个可能的移动和浪费的移动(选择一个颜色,不会'地球'任何邻居,如此以来)可以消除树的建设。一旦建立了决策树,我认为你可以探索每一条路径的点值,但是如果你需要更多的优化,A*绝对会让你接近。

对于每一轮,我都将基本状态作为非全局位置状态的位数组矩阵(因为颜色在全局位置不再重要,您可以通过去掉颜色位来保存状态数据结构上的内存)以及每个可能的决策的点值。然后,您的A*或广度优先算法可以像正常一样最大化路径值。保存路径,分析完成后,进行所有确定的移动。

一个强力的递归搜索将找到最大分数。您最多可以考虑5^25个结束状态。许多中间状态是等效的;识别这些状态并删减重复项的搜索空间可能更快。跟踪你搜索到的最高分数,以及它到达那里的路径(移动顺序)。

1. 如果可以,消除一种颜色。
2. 选择为您生成更多新邻居的颜色!
3. 转到步骤1。

一个好的启发式方法是生成颜色连接的距离图。例如,当前洪水位于零距离处。一组颜色在距离“i”处连接到一个正方形,在距离“i+1”处。

接下来,观察最大距离处有多少颜色。我们需要最大距离移动以消除最大距离处的一种颜色,并且我们需要额外移动以消除最大距离处的每种其他颜色。如果所有颜色都不在最大距离处,请考虑上一个距离处尚未消除的颜色。在进行“最大距离”移动时,我们可能会消除其中一种颜色,但我们需要移动以消除每种附加颜色。

这提供了一个相当好的估计。在最初的14x14板位置,我倾向于得到17到18的估计值,同时需要20到22个移动来获得最佳解决方案。一个14x14板通常可以通过这个下限来解决,同时查看大约10000个板的位置。(使用优化的移动方式,如果可以使用这种移动方式,则消除颜色。)

另一个优化是有些颜色斑点不需要立即清除。在网络距离图中,一个颜色斑点没有另一个邻居时,可能存在leafs。在相同颜色的最远斑点出现之前,不需要取这个颜色斑点。使用这种方法,我们可以调整距离图,以获得必须采取颜色斑点的最短时间。

对于某些董事会职位,我们将能够证明下一轮不需要采用符合条件的颜色。我们可以避免这种颜色,减少分支因子。