23

我对高估/低估这些术语感到困惑。我完全了解 A* 算法的工作原理，但我不确定高估或低估启发式算法的影响。

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

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

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

4

6 回答 6

36

当启发式的估计值高于实际的最终路径成本时，您就高估了。当它较低时你低估了（你不必低估，你只需要不要高估；正确的估计很好）。如果您的图表的边成本都是 1，那么您给出的示例将提供高估和低估，尽管普通坐标距离在笛卡尔空间中也很有效。

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

我不确定您是否会找到它，但您可能想查看Wikipedia A* 文章。我提到（和链接）主要是因为谷歌几乎不可能做到这一点。

于 2009-06-18T14:11:00.747 回答
13

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

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

关键思想是，在低估的情况下，只有当 A* 知道路径的总成本将超过通往目标的已知路径的成本时，它才会停止探索通往目标的潜在路径。由于路径成本的估计值总是小于或等于路径的实际成本，因此只要估计成本超过已知路径的总成本，A* 就可以丢弃一条路径。

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

于 2009-06-18T14:21:35.780 回答
6

简短的回答

@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

于 2018-05-05T22:00:35.700 回答
4

直观的答案

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

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

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

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

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

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

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

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

于 2019-12-18T14:43:16.627 回答
2

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

很抱歉，我无法提供有关鸟瞰线的任何见解...

于 2009-06-18T13:50:18.573 回答
0

考虑启发式，实际成本从f(x)=g(x)+h(x)哪里到，预测成本从哪里到。假设最优成本为：g(x)start-nodecurrent-nodeh(x)current-nodegoalR

  1. 这在搜索的早期阶段h(x)有所不同。给定三个节点 A,B,C

    (*)                               => current pos: A
 A -------> B - 。。。 -> C
 |_______________________|        => the prediction range of h(x)

    一旦你踩到 B，从 A 到 B 的成本是真值，预测h(x)不再包括它：

               (*)                    => current pos: B
 A -------> B - 。。。 -> C
            |____________|        => the prediction range of h(x)

  2. 当我们说低估时，它意味着你的h(x)意志在前进f(x) < R的x路上goal。

  3. 高估确实使算法不正确：

    假设R是19。鉴于这两个成本20，21是已经达到目标的路径的成本：

    Front                  Rear
 -------------------------        => This is a priority queue PQ.
| 20 | 20 | 30 | ... | 99 |
  ^--------                       => This is the "fake" optimal.

    但是说f(y)=g(y)+h(y)，并且y确实在实现最优成本的正确路径上R，但是由于h(y)被高估了，所以f(y)当前30在PQ，所以在我们可以更新30到之前，算法已经从 中19弹出并错误地假设它是“最佳”解决方案。20PQ

于 2021-04-10T06:16:12.403 回答