我试图理解为什么理论上 A* search algorithm 被认为比 A search algorithm 更好。

在这两种算法中,节点都根据函数 f(n) 进行扩展。

A 中:f(n) = g(n) + h(n)
A* 中:f(n) = g(n) + h*(n)(* 表示该函数是一个估计值)。
A* 应该减少必须生成和比较的路径数量。我的问题是:如何使用 h*(n) 而不是 h(n) 减少路径数量?

谢谢 :)

最佳答案

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

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

10-08 05:37
查看更多