我对术语“高估/低估”感到困惑。我完全了解A *算法的工作原理，但是我不确定具有高估或低估启发式算法的影响。
取直接鸟瞰图线的平方是否高估了？为什么会使算法不正确？所有节点都使用相同的试探法。
当您采用直接鸟瞰图线的平方根时，低估了吗？为什么算法仍然正确？
我找不到一篇文章能很好地解释它，所以我希望这里的人有一个好的描述。
最佳答案
当试探法的估算值高于实际最终路径成本时，您就高估了。您会低估何时较低(您不必低估，就不必高估；正确的估计就可以了)。如果图形的边缘成本全部为1，则您给出的示例将提供高估和低估的结果，尽管纯坐标距离在笛卡尔空间中也很有效。
高估并不能完全使算法“不正确”。这意味着您不再具有可允许的试探法，这是保证A *产生最佳行为的条件。如果使用不允许的启发式算法，该算法可能会完成大量多余的工作，以检查它应忽略的路径，并可能由于探索这些路径而找到次优路径。是否实际发生取决于您的问题空间。之所以会发生这种情况，是因为路径成本与估算成本“脱节”，这从本质上使算法弄乱了有关哪些路径比其他路径更好的想法。
我不确定您是否会找到它，但是您可能想看看Wikipedia A* article。我之所以提到(和链接)，主要是因为Google几乎不可能做到这一点。
关于algorithm - A *启发式，高估/低估？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1012691/