我试图理解为什么从理论上讲，A*搜索算法被认为比A搜索算法更好。

在这两种算法中，节点都是根据函数f(n)来展开的。

在A中：f(n) = g(n) + h(n)

在A*中：f(n) = g(n) + h*(n)（*表示该函数是一个估计值）。

A*应该能减少需要生成和比较的路径数量。我的问题是：使用h*(n)代替h(n)是如何减少路径数量的？

谢谢 🙂

回答：

因为你通常不知道h(n)的准确值。要计算这个值，你必须从那个节点开始进行一次完整的搜索到目标节点，而对每个节点都这样做将非常耗费资源。

考虑城市之间由道路连接的情况。你如何知道从任何一个城市到达目标城市的旅行距离是多少？没有进行搜索你是无法知道的。相反，你可以例如使用直接距离作为实际旅行距离的估计值，如果你有两个城市的坐标，这是一个非常简单且快速的计算方法。