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

Question

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

我想知道，对于给定的源和目的地，是否所有3种算法都应该提供最短路径(只需探索不同数量的城市？)或者他们能提供一条不同的路径。

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

Answer 1

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

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

Answer 2

事实上，启发式应该是可接受的，否则A*将找到一个次优解。我认为队列不应该由下一个节点的距离来协调，而应该使用启发式方法，将最有希望的节点放在下一个节点。可以这样想:下一个节点可能离当前节点最远，但同时它也可以是离目的地最近的节点。