如何以最佳方式解决洪水填充拼图？ [英] How to optimally solve the flood fill puzzle?
问题描述
我喜欢玩益智游戏，在Flood-It，它可在网上播放：
I like playing the puzzle game Flood-It, which can be played online at:
这也可以作为一种iGoogle小工具。这样做的目的是为了填补整板用最少数量的连续洪水填充。
It's also available as an iGoogle gadget. The aim is to fill the whole board with the least number of successive flood-fills.
我试图写一个程序，可以解决这个难题，优化。什么是解决这个问题的最好方法是什么？理想情况下我想用A *算法，但我不知道什么应该是函数估计的左步数。我没有写它进行了一次深度4蛮力搜索最大化填充区域的程序。它的工作相当不错，在解决难题打败我，但我不完全满意的算法。
I'm trying to write a program which can solve this puzzle optimally. What's the best way to approach this problem? Ideally I want to use the A* algorithm, but I have no idea what should be the function estimating the number of steps left. I did write a program which conducted a depth-4 brute force search to maximize the filled area. It worked reasonably well and beat me in solving the puzzle, but I'm not completely satisfied with that algorithm.
有什么建议？先谢谢了。
Any suggestions? Thanks in advance.
推荐答案
作为一个启发式，可以构造的曲线图，其中每个节点再presents一组连续的，相同颜色的正方形，并且每个节点都连接到这倒是。 （权重为1每条边）。然后，您可以使用路径寻找算法来计算从左上角的距离到所有其他节点。然后，通过观察使用每个其他5种颜色洪水填充的结果，确定哪一个最小化到最远节点的距离，因为这很可能是瓶颈。
As a heuristic, you could construct a graph where each node represents a set of contiguous, same-colour squares, and each node is connected to those it touches. (Each edge weighted as 1). You could then use a path-finding algorithm to calculate the "distance" from the top left to all other nodes. Then, by looking the results of flood-filling using each of the other 5 colours, determine which one minimizes the distance to the "furthest" node, since that will likely be your bottleneck.
补充一点，计算罢了，迄今所做的一些结果，并用其作为您的A *启发式。
Add the result of that calculation to the number of fills done so far, and use that as your A* heuristic.
这篇关于如何以最佳方式解决洪水填充拼图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
