algorithm - Flood It 游戏算法

Question

游戏链接在这里: http://floodit.appspot.com/

规则很简单，你必须从邻居中选择一种颜色，起点是左上角，然后颜色发生变化，你就淹没了更多的区域。目标是淹没整个网格。

stackoverflow 上有一些关于这个游戏的主题，但我找不到我的问题的答案。我的目标是找到淹没整个网格的最佳方式。现在我处于这个位置:

我正在尝试通过 A* 解决这个问题。我的启发式方法是选择颜色，以最小化到最远组件的距离(在这种情况下，图像上带有红色的 2、4、1、3 是最远的)，如果几种颜色最小化到最远组件之一的距离，那么我选择其中包含最多点的颜色(在这种情况下，我的算法选择“0”，因为它最小化到所有最远节点的距离并且其中包含更多点，然后是“2”)。

我的老师给了我们最佳解决方案，在这种情况下，他的最佳解决方案是:2, 0, 1, 4 ,3, 2, 5；这是 7 个单位。但根据我的启发，我选择“0”，最好的方法是:0、2、4、5、3、1、0、2、4；还有9个单位。任何人都可以回答我，我必须在这个位置选择“2”而不是“0”吗？提前谢谢你。

Answer 1

我想您将 A* 算法与简单的 greedy best-first search 混淆了您只需计算启发式 h(n)，它会以某种方式估计从当前状态到目标状态的成本(或距离)。

在 A* 中，您正在扩展使函数 f(n) = g(n) + h(n) 最小化的节点，其中 g(n) 提供从起点开始的(路径)成本直到当前状态(并提醒 A* 可以在状态图 before finding the optimal one 上探索多个方向)。

在你的情况下，我可以想象 g(n) 可以等于从根状态开始的路径长度，因为你对最短路径感兴趣(每个新状态的成本为 1) .为了找到最优路径，A* 的 h(n) 永远不会高估最优解。出于这个原因，一种想法是使用表中剩余颜色的数量来计算它(事实上，您总是至少需要移动多少才能达到全彩色最终状态)。

请注意，这种启发式方法提供的信息不多，即它会让您在收敛到解决方案之前展开许多状态。