我喜欢玩益智游戏的Flood-It，其可在网上进行播放：
https://www.lemoda.net/javascript/flood-it/game.html
它也可作为一种iGoogle小工具。 其目的是填充整个板用连续洪水填充的数量最少。
我试图写一个能够最佳解决这个难题的程序。 什么是解决这个问题的最好方法是什么？ 理想的情况是我想用A *算法，但我不知道什么应该是估计的左步数的功能。 我也写一个进行深度4蛮力搜索最大化填充区域的程序。 它的工作相当不错，在解决难题打败我，但我并不完全满意，该算法。
有什么建议？ 提前致谢。
作为启发式，可以构建其中每个节点代表一组连续的，相同颜色的正方形的曲线图，每一个节点被连接到那些倒是。 （加权为1的每个边缘）。 然后，您可以使用路径搜索算法来计算到所有其他节点从左上角的“距离”。 然后，通过查看使用每个其他5种颜色填注的结果，确定哪一个最小化到“最远的”节点的距离，因为这将有可能是你的瓶颈。
添加结果计算迄今所做填充的数量，并使用它作为你的A *启发。
玩游戏了几次后，我发现一个好的策略是总是去“深”，该在哪去最远的到被淹没版图的颜色。
幼稚“贪婪的”算法是选择最大化主区域的总周长的下一步。
（一对夫妇的我的聪明朋友们在思考这个有一天，决定optimium可能是NP难的（例如，你必须蛮力的话） - 我不知道，如果他们是正确的（是不是围绕听到推理和没有经过我自己）认为。）
请注意，计算步骤，我相信工会找到的算法是你的朋友，它使计算“一步到位”非常快的（例如参见这篇博客文章 ）。
A *只是一个优先图搜索。 每个节点是一个游戏的状态，你的排名基于启发式节点，始终扩大预期最低的最终成本的节点。 只要你的启发并没有低估成本，你会发现第一个解决方案是保证最佳的。
玩游戏了几次后，我发现，试图深入到对面的角落，然后各个角落往往导致胜利。 所以一个好的开始成本估计会（成本到目前为止）+填充足够数量达到对角[注意：不是最低，就足够了。 只需填写贪婪地朝角落计算启发。
我一直在做这个，我有我的工作求解后，我看了看在他人的方法采取了。
大多数求解出有启发性，不保证最优。 启发式看广场和颜色分布的数量左未选中，或以“最远”广场的距离。 在相当快的标准14×14网格解决方案结合了很好的启发与有界DFS（或BFS与前瞻）的结果。
我参加了一个稍微不同的方法，因为我感兴趣的是找到可证明的最优路径，而不只是一个“好”的一个。 我观察到的搜索空间居然长得比搜索树的分枝因子慢得多，因为有相当多的重复的位置。 （采用深度优先的策略是很重要的维护历史，以避免重复工作。）有效分枝因子似乎比5更接近3。
我把搜索策略是高达执行BFS的“中点”的深度，其中国家的数目将变得不可行，地方11个13之间的移动效果最好。 然后，我检查在中点深度的每个状态，并执行开始与作为根新BFS。 这两个BFS搜索可以通过消除以前的深处发现的状态被修剪，而后者搜索可以由最知名的解决方案的深度为界。 （A启发式施加到在所述第二步骤中检查的子树的顺序可能会帮助一些，以及。）
这被证明是关键，快速解算器的其他修剪技术简单地检查是否有超过左N种颜色，如果你是N或更少的步骤远离当前最佳的解决方案。
一旦我们知道这中点状态是道路上的最佳解决方案，该方案可以使用中点状态为目的，进行DFS（整枝，在中点选择方没有任何路径）。或者，它可能是可行的，只是建立在BFS步骤的路径，在一些额外的存储器的成本。
我的求解器是不是超级快，但它可以在不超过两分钟保证最佳的解决方案。 （参见http://markgritter.livejournal.com/673948.html ，或在代码http://pastebin.com/ZcrS286b 。）
Smashery的回答可以稍微调整了。 对于移动的总数估计，如果有在最大距离数“k”颜色，添加“K-1”的动作的次数估计。
更一般地，对于每种颜色，考虑在其中颜色可以被清除的最大距离。 这给了我们一个字典映射一些最大距离为非零数字的颜色，可以在这个距离被清除。 和值-1在按键之间，这增加了最大距离得到了一些移动估计。
此外，也有一定的自由的情况。 如果在任何时候，我们可以在一个举动清除颜色，我们可以采取的举动不考虑其他动作。
Here's an idea for implementing the graph to support Smashery's heuristic.
Represent each group of contiguous, same-colour squares in a disjoint set, and a list of adjacent groups of squares. A flood fill merges a set to all its adjacent sets, and merges the adjacency lists. This implicit graph structure will let you find the distance from the upper left corner to the farthest node.
我觉得你可以考虑匹配或者不当前颜色相匹配的平方数。 所以，你的“距离”启发式措施是在黑板上的正方形被-not-相同的颜色作为你选择的颜色的数量，而不是步数。
一个天真的启发可能是使用的左颜色数（减1） - 这是容许的，因为这至少需要许多点击明确了董事会。
我不能肯定，但我相当肯定，这可以贪婪地解决。 你试图色域的数量减少到1，这样减少了更多的色彩领域较早应不大于减少更少的早期任何效率较低。
1）定义已有相同颜色组的集合。
2）对于每一个集合，通过计算邻近色收集的次数。 用单一颜色相邻集合的最大数量是这个系列的重量。
3）采取与单色邻居的最高计数的收集，并填写该颜色。 合并的集合，并更新排序为受到合并（所有合并收集的新邻居）的所有集合。
总的来说，我认为这应该为O实际计算（N log n）的时间，其中n是像素数和日志（N）只来自于保持权重的排序列表。
我不知道是否需要有一个决胜于当多个字段具有相同的重量，但。 也许决胜去那很常见的地图上的大多数组的颜色。
无论如何，注意，游戏的目的是为了减少不同颜色字段的数量，而不是最大限度的周边，因为不同的配色方案可以偶尔做更大的领域的次优选择。 考虑领域：
3 3 3 3 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
颜色1具有通过任何措施最大周长，但颜色2是最优选择。
编辑>
从头开始的。 这个例子：
3 1 3 1 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
我失效自己的贪心算法。 但我不认为这是一个简单的图遍历，因为改变成2楼的邻居共享的颜色访问2个节点，而不是1。
色彩消除可能应该起到一些启发作用。
1）这是从来没有正确的填充颜色，是不是已经在图形上。
2）如果有一个独特的颜色一种颜色字段，至少一个填充将需要它。 它不能与任何其他填充捆绑在一起。 我认为，这意味着它是安全的，宜早不宜迟填充它。
3）对于邻居字段计数的贪婪算法有意义2颜色映射。
