为什么A星算法需要g(n)？

Question

Dijkstra的算法是f(n) = g(n)

A*是f(n) = g(n) + h(n)。

g( n )是从起始节点到n的路径的代价。

h(n)是一个启发式函数，它估计从n到目标的最便宜路径的代价。

需要g(n)？它不能找到没有g(n)的最短路径吗？

为什么A*需要g(n)？

Answer 1

我们需要g(n)

考虑这样的情况:对于目标的给定路径上的所有节点(这是一个完全有效的，即可接受的、启发式的)和所有其他节点的非零，h(n)是0。

如果我们忽略到目前为止的成本(g(n))，那么显然无论实际成本是多少，我们都会选择这条路径上的节点，因此我们最终得到的路径比其他路径的代价要大得多。

               start
       g(n)=0    O --
               5 |   \ 1
h(n)=0,g(n)=5    O    O h(n)=1,g(n)=1
               5 |   / 1
h(n)=0,g(n)=10   O --
               goal

在上面的例子中，我们将选择左边的节点，然后是目标，因为这两个节点都是h(n) = 0 (这比右边节点的h(n) = 1要大)。这将为我们提供一条成本为10的路径，其中最便宜的路径是选择右边的节点，代价是2。

这可能是一个极端的例子，但同样的想法适用于许多其他情况。例如，您还可以将10添加到我的示例中的所有值中，并使其成为较大图的一部分，并且它最终仍然会错误地选择右侧上方的左侧。

这里更普遍的结论是，您可以在两个节点n1和n2之间选择h(n1) < h(n2)，因此我们将选择n1，但是n2在最便宜的路径上，而不是n1。

如果包含g(n)，我们也可能选择错误的节点。但是，在这种情况下，对于路径上的某些节点n (包括n1 )，f(n)将大于最便宜的路径(在最坏的情况下，n将是目标，而f(n)将是通过n1实现该目标的真正成本，这显然比实际最便宜的路径更昂贵)，因此也比f(n2)更大(因为启发式需要低估成本)，所以我们在达到目标之前先探索n2。

如果h(n)是真正的成本(而不是一个估计)

这样我们就不需要g(n)了。

但在这种情况下，只有考虑h(n)才会使其成为一个贪婪的算法(假设非负的边缘权重)，因为对于我们选择的每个节点(因为我们正在接近目标)，h(n)会减少，所以在最优路径上我们会选择一个节点(因为它的h(n)最低)，然后我们将继续选择最优路径上的节点。