我对高估和低估这两个术语感到困惑。我完全理解 A* 算法的工作原理，但不确定使用高估或低估的启发式算法会产生什么影响。

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

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

我找不到一篇清晰地解释它的文章，所以我希望这里有人能给出好的描述。

回答：

当启发式算法的估计值高于实际最终路径成本时，您就是在高估。 当它较低时，您就是在低估（您不必低估，您只需要不高估；正确的估计是可以的）。 如果图的边成本都为 1，那么您给出的示例将提供高估和低估，尽管简单的坐标距离在笛卡尔空间中也能很好地工作。

高估并不完全使算法“不正确”；它的意思是您不再具有可采纳的启发式算法，这是 A* 保证产生最佳行为的条件。 使用不可采纳的启发式算法，该算法最终可能会进行大量多余的工作，检查它应该忽略的路径，并且可能由于探索这些路径而找到次优路径。 实际上是否发生这种情况取决于您的问题空间。 发生这种情况是因为路径成本与估计成本“不一致”，这本质上使算法对哪些路径比其他路径更好产生了错误的认识。

我不确定您是否会发现它，但您可能想看看维基百科 A* 文章。 我提到（并链接）主要是因为它几乎不可能在 Google 上搜索到它。