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

Question

4

我正在尝试理解为什么在理论上，A*搜索算法被认为比A搜索算法更好。

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

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

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

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

谢谢 :)

- Cheshie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

由于您通常不知道h(n)的确切值。要计算这个值，您需要对从该节点到目标的所有路径进行完全搜索，而对每个节点都进行此操作将非常昂贵。

考虑通过道路相连的城市。如何知道到达目标城市所需的旅行距离？如果没有搜索，您无法做到这一点。相反，您可以使用直接距离作为实际旅行距离的估计，如果您有两个城市的坐标，则这是一个非常简单且快速的计算。