A*启发式算法，过高估计/低估计？

Question

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

过度估计是当你对直接鸟瞰线平方处理时吗？为什么会使算法不正确？同样的启发式被用于所有节点。

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

我找不到一个清晰易懂的文章来解释这个问题，所以希望这里有人能够提供一个好的描述。

- Mads Andersen

Answer 1

当启发式估计值高于实际最终路径成本时，你会高估。当它低于实际成本时（你不必低估，只需不高估，正确 估计是可以的），你会低估。如果你的图的边缘成本都是1，那么你提供的例子将提供高估和低估，尽管在笛卡尔空间中，普通坐标距离也很好用。

高估并不一定使算法“不正确”，它意味着你不再拥有一个可接受的启发式，这是保证A *产生最优行为的条件。使用不可接受的启发式，算法可能会进行大量多余的工作来检查应该忽略的路径，并可能由于探索这些路径而找到次优路径。是否发生这种情况取决于你的问题空间。这是因为路径成本与估算成本“不匹配”，这基本上让算法对哪些路径更好产生混乱的想法。

我不确定你是否已经找到了它，但你可能想看看Wikipedia A* article。我之所以提到（并链接）主要是因为在谷歌搜索它几乎是不可能的。

- chaos

---

使用过度估计的启发式算法，相较于使用低估计的启发式算法，应该更快地找到一个（次优）解，不是吗？如果使用极度低估的启发式算法（例如始终返回0），可以得到最优解，但本质上只是进行广度搜索。 - chtz

@chtz 是的，这是真的。你会更快地得到一个解决方案，尽管不是最优的。相反的，这也是为什么Djisktra算法通常比A*算法慢，因为启发式函数始终为0（我知道，三年晚了，但可能会帮助将来阅读此内容的其他人）。 - Ayush

@chtz：不，低估了反而会使搜索可能次优解的速度更快。 - VimNing

我没有在Rainning发表评论时被提醒，但今天重新访问了一下。低估并不会“使搜索次优解更快”。低估实际上提供了最优解。 - Ayush

Answer 2

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

该算法会一直执行，直到目标节点的f 值小于队列中任何节点的值（或队列为空）。

关键思想是，使用低估计值，A*只有在已知路径总成本超过通往目标的已知路径成本时才停止探索通向目标的潜在路径。由于路径成本的估计值始终小于或等于路径的实际成本，因此一旦估计成本超过已知路径的总成本，A*就可以丢弃该路径。

使用高估计值，A*不知道什么时候可以停止探索可能的路径，因为可能存在实际成本更低但估计成本更高的路径，而这些路径比通往目标的最佳已知路径还要差。

- Eric

---

理解了，但我引用的那部分是正确且与我的回答相关。 - Eric

Answer 3

简短回答

@chaos的回答有点误导（应该强调“可以”），高估并不一定使算法“不正确”；它意味着你不再拥有一个可接受的启发式，这是保证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. 乘以10的直线距离（青色）

• 过高估计
• 扩展的节点数：188
• 路径长度：99.811

- Felix

Answer 4

直观的答案

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

这里的乐观主要指您的期望始终比现实好多了。

乐观主义者会尝试很多可能最终会让人失望的事情，但他们会发现所有好的机会。

悲观主义者预期结果不佳，因此不会尝试很多事情。由于这个原因，他们可能会错过一些绝佳的机会。

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

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

最有效的A*是永远不低估，但是要么完美地估计，要么只是稍微过于乐观。然后您将不会天真地尝试太多糟糕的选项。

对于每个人的一个好教训。始终保持一点乐观！

- Bouke Versteegh

Answer 5

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

很抱歉我不能提供有关鸟瞰线的任何见解...

- AlbertoPL

---

如果高估了潜在成本，这意味着该分支的预测成本更高，__不太可能__被选择。你确定这会加速搜索吗？ - VimNing

Answer 6

考虑启发式函数为 f(x) = g(x) + h(x)，其中g(x) 是从 起点 到 当前节点 的实际花费，h(x) 是从 当前节点 到 目标 的预测花费。假设最优花费为 R，则：

1. h(x) 在搜索的早期阶段起着重要作用。假设有三个节点 A、B、C：

   (*)                               => 当前位置：A
    A -------> B - 。。。 -> C
    |_______________________|        => h(x) 的预测范围
   

   一旦你到达 B，从 A 到 B 的代价是真实的，而预测的 h(x) 不再包括它：

              (*)                    => 当前位置：B
    A -------> B - 。。。 -> C
               |____________|        => h(x) 的预测范围
   

2. 当我们说低估时，意味着你的 h(x) 会导致所有通往目标的路径上的 x 都满足 f(x) < R。

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

   假设 R 是 19。并且给定两个代价为 20、21 的路径已经到达了目标：

   前面                  后面
    -------------------------        => 这是一个优先队列 PQ。
   | 20 | 20 | 30 | ... | 99 |
     ^--------                       => 这是“虚假”的最优解。
   

   但是假设 f(y)=g(y)+h(y)，并且 y 确实在通向最优代价 R 的正确路径上，但由于 h(y) 被高估了，所以 PQ 中的 f(y) 目前是 30，因此在我们能够将 30 更新为 19 之前，算法已经会从 PQ 中弹出 20 并错误地认为它是一个“最优”的解。

- VimNing