java - A* 总是提供最短路径吗？

Question

我正在尝试了解 A*、统一成本和贪婪搜索算法的工作原理。我知道探索节点的方式在所有 3 种算法中都发生了变化(贪婪将基于启发式值进行探索，A* 基于启发式加距离，统一基于距离)。

我想知道对于给定的源和目的地，所有 3 种算法是否应该提供最短路径(只是探索了不同数量的城市？)还是它们可以提供不同的路径。

我最困惑的是实现部分 - 如果你将节点存储在队列中，那么当你要探索目标节点时，你将拥有它的最短路径，但如果你有路径队列(并且这个队列是现在根据启发式 + 距离排序)那么你可能不会总是得到最短路径。

Answer 1

不一定，这取决于你的启发式。参见 this section in Wikipedia详细解释了它。

总而言之，如果启发式方法可接受(意味着它永远不会高估成本)，A* 会给出最佳解决方案。