我试图理解为什么理论上 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)
的确切值。要计算它,您必须从该节点到目标进行完整的搜索,并且为每个节点执行此操作将非常昂贵。
考虑由道路连接的城市。您如何知道从任何给定城市到达目标城市的旅行距离是多少?不搜索就无法做到这一点。相反,例如,您可以使用直接距离作为实际行驶距离的估计值,如果您拥有两个城市的坐标,这是一种非常简单且快速的计算。