algorithm - 为什么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 添加到我的示例中的所有值，并将其作为更大图表的一部分，但最终仍然会错误地选择右侧上方的左侧。

这里更普遍的结论是，您可以在 2 个节点 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) )，然后从那里我们只会继续选择最佳路径上的节点。