algorithm - 为什么A-star算法需要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)？

标签： algorithma-star

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和n2where之间进行选择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)），然后我们将继续在最佳路径上选择节点。