A* 启发式，高估/低估？

StackOverflow https://stackoverflow.com/questions/1012691

题

我对高估/低估这两个词感到困惑。我完全了解 A* 算法的工作原理，但我不确定高估或低估启发式的效果。

当你取直接鸟瞰线的平方时，是否高估了？为什么它会使算法不正确？所有节点都使用相同的启发式。

当你取直接鸟瞰线的平方根时，是否低估了？为什么算法仍然正确？

我找不到一篇文章可以很好地解释它，所以我希望这里有人有一个很好的描述。

有帮助吗？

解决方案

您高估了启发式算法的估算何时高于实际最终路径成本。你低估了什么时候它低了（你不必低估，你只需要高估; 正确的估计没问题）。如果你的图的边缘成本都是1，那么你给出的例子会提供高估和低估，尽管普通坐标距离在笛卡尔空间中也很有效。

过高估计并不能使算法“不正确”;这意味着您不再拥有可接受的启发式，这是A *保证产生最佳行为的条件。由于不可接受的启发式算法，该算法最终可以完成大量多余的工作，检查它应该忽略的路径，并且可能因为探索这些路径而找到次优路径。是否实际发生取决于您的问题空间。之所以发生这种情况，是因为路径成本与估算成本“脱节”，这实际上让算法搞砸了哪些路径比其他路径更好的想法。

我不确定你是否会找到它，但你可能想看一下维基百科A *文章。我提到（和链接）主要是因为谷歌几乎不可能为它做准备。

其他提示

从维基百科A *文章中，算法描述的相关部分是：

  

算法继续，直到目标节点的值 f 低于队列中的任何节点（或直到队列为空）。

关键的想法是，A *只有在知道路径的总成本将超过目标的已知路径的成本时，只有低估，A *才会停止探索到目标的潜在路径。由于路径成本的估算值始终小于或等于路径的实际成本，因此只要估算的成本超过已知路径的总成本，A *就可以丢弃路径。

由于过高估计，A *不知道何时可以停止探索潜在的路径，因为可能存在实际成本较低但估计成本高于目标最佳路径的路径。

据我所知，您通常希望低估，以便您仍然可以找到最短的路径。您可以通过高估来更快地找到答案，但您可能找不到最短的路径。因此，为什么过高估计是“不正确”，而低估仍然可以提供最佳解决方案。

对不起，我无法对鸟瞰线提供任何见解......

简短回答

@chaos 的答案在我看来有点误导（可以应该突出显示）

高估并不会让算法“不正确”；这意味着你不再有可接受的启发式，这是保证 A* 产生最佳行为的条件。通过不可接受的启发式，该算法 能 最终做了大量多余的工作

正如@AlbertoPL 所暗示的

通过高估你可以更快地找到答案，但你可能找不到最短路径。

最后（除了数学最优之外），最优解决方案很大程度上取决于您是否考虑计算资源、运行时间、特殊类型的“地图”/状态空间等。

长答案

作为一个例子，我可以想到一个实时应用程序，其中机器人通过使用高估的启发式方法更快地到达目标，因为较早开始的时间优势大于采用最短路径但等待更长的时间来计算该解决方案的时间优势。

为了给您更好的印象，我分享了一些我用 Python 快速创建的示例结果。结果源自相同的 A* 算法，只是启发式不同。每个节点（网格单元）都有到除墙之外的所有八个邻居的边。对角线成本 sqrt(2)=1.41

第一张图显示了一个简单示例案例的算法返回路径。您可以通过高估启发法（红色和青色）看到一些次优路径。另一方面，存在多个最佳路径（蓝色、黄色、绿色），这取决于首先找到哪一个的启发式。

不同的图像显示达到目标时所有扩展的节点。颜色显示使用该节点的估计路径成本（也考虑从开始到该节点的“已采取”路径；从数学上讲，它是到目前为止的成本加上该节点的启发式）。在任何时候，算法都会扩展估计总成本最低的节点（如上所述）。

Paths

1.零 （蓝色的）

  • 对应Dijkstra算法
  • 节点扩展：2685
  • 路径长度：89.669

Zero

2.当乌鸦飞翔时 （黄色的）

3.理想的 （绿色的）

  • 没有障碍物的最短路径（如果你沿着八个方向走）
  • 尽可能最高的估计，但不高估 （因此“理想”）
  • 节点扩展：第854章
  • 路径长度：89.669
  • https://i.stack.imgur.com/VqMtF.png

4.曼哈顿 （红色的）

  • 没有障碍物的最短路径（如果你不沿对角线移动；换句话说：“对角移动”的成本估计为 2)
  • 高估
  • 节点扩展：第562章
  • 路径长度：92.840
  • https://i.stack.imgur.com/gD9t4.png

5.乌鸦飞十次 （青色）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top