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

Question

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

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

直接鸟瞰线取平方根算低估吗？为什么算法仍然正确？

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

Answer 1

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

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

我不确定你是否会找到它，但你可能想看看 Wikipedia A* article .我提到(和链接)主要是因为它几乎不可能通过谷歌搜索。