A*启发式,过高估计/低估？

Question

我对高估/低估这些术语感到困惑.我完全了解A*算法是如何工作的,但我不确定具有高估或低估的启发式算法的效果.

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

当你采用直接鸟瞰线的平方根时会被低估吗？为什么算法仍然正确？

我找不到一篇解释得很好而且清晰的文章,所以我希望这里的人有一个很好的描述.

Answer 1

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

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

我不确定你是否会找到它,但你可能想看一下维基百科的A*文章.我提到(和链接)主要是因为Google几乎不可能.

Answer 2

从Wikipedia A*文章中,算法描述的相关部分是:

算法继续,直到目标节点的f值低于队列中的任何节点(或直到队列为空).

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

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

Answer 3

简答

@chaos 回答有点误导 imo（应该突出显示）

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

正如@AlbertoPL 暗示的那样

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

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

长答案

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

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

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

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

1.零（蓝色）

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

2. 乌鸦飞翔（黄色）

• 节点扩展：658
• 路径长度：89.669

3.理想（绿色）

• 没有障碍物的最短路径（如果你遵循八个方向）
• 不高估的最高可能估计（因此是“理想的”）
• 节点扩展：854
• 路径长度：89.669

4.曼哈顿（红色）

• 没有障碍物的最短路径（如果您不沿对角线移动；换句话说：“对角线移动”的成本估计为 2）
• 高估
• 扩展的节点：562
• 路径长度：92.840

5. 乌鸦飞十圈（青色）

• 高估
• 节点扩展：188
• 路径长度：99.811

Answer 4

直观的答案

为了使 A* 正常工作（始终找到“最佳”解决方案，而不是任何解决方案），您的估计函数需要是乐观的。

这里的乐观意味着您的期望总是比现实好。

乐观主义者会尝试许多最终可能会令人失望的事情，但他们会找到所有好的机会。

悲观主义者期待糟糕的结果，因此不会尝试很多事情。因此，他们可能会错过一些黄金机会。

所以对于 A* 来说，乐观意味着永远低估成本（即“可能不会那么远”）。当你这样做时，一旦你找到了一条路径，那么你可能仍然会对几个未探索的选项感到兴奋，那可能会更好。这意味着您不会停留在第一个解决方案上，而是继续尝试其他解决方案。大多数人可能会失望（不是更好），但它保证您总能找到最佳解决方案。当然，尝试更多的选择需要更多的工作（时间）。

一个悲观的A *将总是高估成本（例如，“该选项可能是非常糟糕”）。一旦它找到了一个解决方案并且知道了这条路径的真实成本，其他每条路径都会看起来更糟（因为估计总是比现实更糟），一旦找到目标，它就永远不会尝试任何替代方案。

最有效的 A* 是永远不会低估的 A*，而是完美地或略微过度乐观地估计。那么你就不会天真并尝试太多糟糕的选择。

给大家上了一堂很好的课。永远保持乐观！