算法和数据结构，用以解决游戏"水珠"/泛填补/"FloodIt"

Question

建议的一个算法和数据结构，用于解决水珠游戏(http://www.deadwhale.com/play.php?game=131).这是非常有趣的，在一个令人讨厌的一种方式。

状态的时间-空间的复杂性(big-O)方法方面的N, 大小电网(N>=14条)。 好足够高效率的算法与低复杂性是优选的。

(MatrixFrog正确地指出了这个游戏也称为FloodIt，并Smashery给了一个解决方案3个月前在本链接，他列举如下。所有你们的建议修剪/贪婪只有1lookahead，这给了次优的解决方案。)

游戏产生一种随机方形网格的n节点，其中每个节点是彩色的一个六种颜色(Grn=1,免费=2,Red=3、Blu=4,飘=5,生于=6).1级有9×9格，然后n增加了每个级别，多达到14个。每个级别可以采取多达25变，否则你会失去。在每个回合你选择哪种颜色的改变左上节点，例如Grn->红色，例如，任何连接邻(地平线/vert)节点的新的颜色，得到同化成一个形状、和1pt每个节点被同化是加入到你的分数。评分的目标是完成的每个电网的几个原因可能的，例如如果你这样做在16个转弯，然后你的未使用的9动=>2*9的乘数次你的总的累积分。

显然有一吨的方式来分解这一和默认选择的递归回溯有14×14网是一个可行的竞争者;什么其他类型的数据结构不该借给自己?A*?不要挂了优化，我想知道如果有一个"足够好的"算法。

(我想这可能是一个有趣的项目的代码一个机器人，并获得愚蠢-高分。虽然我打进了3.5E+12全部由我的fleshware的自我。)

Answer 1

这个游戏还是引起了我的兴趣，所以我花了几个上个工作日。

我注意到的第一件事情，是很容易显示，前板后（也许在某些情况下2），提高成绩的最快方法是使用倍增。正因为如此，我建立了一个系统，在最少的步骤解决每块板的目标。我开始想用A *，因为它一般建只是这些类型的搜索问题......但是，这个问题仍然被证明是一个doozie。

在谈到A *，它的效果真的归结您的启发式估计的选择。你越接近猜测的实际距离，这将有更少的节点，以便达到目标进行扩展。对于这个问题，我经历了许多用于估计思想去，但大多打破了A *的规则，这是你不能高估的实际距离，否则你打破的最优*。

有几个是工作但是。在这个线程其他人张贴了关于只是把其余颜色的数量估计，这是容许的，因为它不能高估（你要改变颜色至少一次，其余每个颜色不是主要的“洪水”区域的一部分，与此启发式问题是它非常差估计的实际距离。就拿第一移动，其通常具有的颜色的数量的估计，6.经常扩展到2个移动，其中的每一个通常具有7的估计，等等等等。拿这个5级深，为10×10板尺寸，最叶子有11估计这种启发式基本上是一个广度，实现先搜索，直到距离4点或5移动到您的的目标。这是不是很有效，并以我个人的测试中，指数运行一个多围绕董事会规模9，这往往需要大约在溶液14个移动。应该指出我的解决方案是非常高的水平但是并没有太多小心到SPE编事情。

的问题是，A *是真的只有好的当每个步骤使得一个显著细化的整体解决方案的实际距离。直接在问题看，你可能不会找到一个很好的启发，可以比这更好做不超过估算成本。但是，如果转换问题到另一个问题，更好地试探你跳出来。启发式“的其余颜色数”回答这个问题，什么是剩余的可能移动的最小数目。要回答这个问题，我问自己“这点在黑板上需要的步骤，以获得最大数量”？我最终解决的答案为“是多少步是将右下角的”我的启发。这是很容易通过运行一次A实现*搜索该作品更像是寻找地图的方向，然后计算在溶液的步数。我意识到这是在黑板上选择任意点，但是它的工作相当不错的测试和每个其余点运行A *把我的单处理器测试机上的时间会比较大。

此启发式单独有一个倾向崩溃后右下角成为然而洪泛区的一部分，因此最终结果为MAX（右下角分钟的步骤，其余的不主要洪水的一部分的颜色数）。这次终于能够实现一些非常大的电路板尺寸符合我的高水平实施第二下。

我会留下记录设置你。

Answer 2

另一种方法是使用遗传算法。 由于任何（局部的）的解决方案包括颜色的列表的，它转换非常漂亮的基因。适应度函数可以是这样的4倍的连接分量减去使用的颜色总（基因的长度）的数目。

我在数学尝试这个10×10上板，具有非常非优化算法， 并得到了短期的解决方案，而迅速。 我不要求它是最佳的，但有足够的时间，在变异的基因会保证你最终与最佳的解决方案结束的过程中的随机性。

Answer 3

由于招式我觉得你可以充分发掘决策树固定的起始状态和数量有限。对于每一轮中，只有5个可能的行动和浪费的举动（选择不会“水珠”任何邻居们那么永远的颜色），可以作为树是建立淘汰。一旦决定树建我认为你可以探索每个路径的点值，但如果你需要更多的优化A *铁定让你靠近。

对于每一轮，我会的基本状态比特串为unglobbed位置的状态的矩阵（因为在匹配替换的位置，你可以留下掉在你的状态数据结构保存记忆的颜色不再是问题色位）和用于每个决策可能的点值。然后你的A *，或广度优先算法可以只最大限度的路径值正常。保存路径，一旦你的分析完成后，使所有的确定移动。

Answer 4

一个蛮力递归搜索将会找到最高得分。你有最多5 ^ 25个结束国家考虑。许多中间状态将是相当的;它可以更快地识别这些和修剪重复的搜索空间。跟踪得分最高的发现，只要你搜索，与路径（举动序列），它采取了到那里一起。

Answer 5

1. 如果可以的话，消除一种颜色。
2. 选择颜色，产生更多的新邻居你！
3. 转到第1步。

Answer 6

一个好的启发式是产生颜色连接距离图。例如。目前洪水在距离为零。连接到在距离正方形的一组颜色的“i”是在距离“i + 1的”。

接着，观察多少颜色是在最大距离。我们需要最大距离移动，以消除在最大距离一个颜色，我们需要一个额外的举措，以消除在最大距离每增加色彩。如果所有颜色都没有的最大距离，考虑在尚未被淘汰之前的距离的颜色。我们可能会消除这些颜色之一，同时使“最大距离”的动作，但我们需要移动，以消除每个额外的颜色。

这提供了相当好的估计。在初始14×14板位置，我倾向于得到的估计值17至18，而需要20〜22为最佳的解决方案移动。一个14×14板通常可以解决的，这个下限，一边看着约10000董事会职位。 （使用制造此举消除了色，如果这样的举动是可用的最优化。）

Answer 7

另一种优化是，有一些并不需要马上采取一些做颜色的斑点。可以有在网络距离图，其中一种颜色的斑点不具有进一步邻居叶子。这种颜色的斑点确实不需要采取直到相同颜色的斑点最远。使用这种方法，我们可以调整距离图来获得将在哪个颜色斑点必须采取的最小时间。

对于一些仓板，我们将能够证明符合条件的颜色并不需要采取的下一回合。我们能够避免颜色和降低的支化因子