algorithm - 为什么 A* 搜索算法比 A 更好？

Question

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

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

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

在 A* 中:f(n) = g(n) + h*(n)(* 表示该函数是一个估计).

A* 应该可以减少必须生成和比较的路径数量。我的问题是:使用 h*(n) 而不是 h(n) 如何减少路径数量？

谢谢:)

Answer 1

因为你一般不知道h(n)的确切值。要计算此值，您必须从该节点到目标进行完整搜索，并且对每个节点执行此操作将非常昂贵。

---

考虑由道路连接的城市。您如何知道从任何给定城市到达目标城市的旅行距离是多少？不搜索就无法做到这一点。相反，例如，您可以使用直接距离作为实际行驶距离的估计值，如果您有两个城市的坐标，这是一个非常简单和快速的计算。