为什么A-star算法需要g（n）？ [英] Why does the A-star algorithm need g(n)?

问题描述

Dijkstra的算法为 f（n）= g（n）

并且A *为 f（n）= g（n）+ h（n）。

Dijkstra's algorithm is f(n) = g(n)
and A* is f(n) = g(n) + h(n).

g（n）是从起始节点到n的路径成本。 br>
h（n）是一种启发式函数，用于估算从n到目标的最便宜路径的成本。

g(n) is the cost of the path from the start node to n.
h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.

是否需要g（n）？它找不到g（n）的最短路径吗？

Is g(n) needed? Can't it find the shortest path without g(n)?

为什么A *需要g（n）？

Why does A* need g(n)?

推荐答案

我们需要 g（n）

当 h（n）为目标的某个给定路径上的所有节点的 0 时的情况（这是完全有效的，即所有其他节点的可接受性，启发式）和非零值。

We need g(n)

Consider the case when h(n) is 0 for all nodes on some given path to the goal (which is a perfectly valid, i.e. admissible, heuristic) and non-zero for all other nodes.

如果到目前为止我们忽略了成本（ g（n）），很明显，无论实际成本是多少，我们都将选择该路径上的节点，因此最终的路径可能比其他路径具有更高的成本。

If we ignore the cost so far (g(n)), clearly we will pick the nodes on this path no matter what the actual cost is, so the path we end up with can have a much greater cost than some other path.

               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 。

In the above example, we will pick the node on the left, and then the goal, since h(n) = 0 for both (which is greater than h(n) = 1 for the node on the right). This will give us a path with cost 10, where the cheapest path involves picking the node on the right, for a cost of 2.

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

This is perhaps an extreme example, but the same idea applies in many other cases. For example, you could also add 10 to all values in my example and have it be part of a larger graph and it would still end up incorrectly picking the left side above the right.

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

The more general conclusion here is that you can have a choice between 2 nodes n1 and n2 where h(n1) < h(n2), thus we'll pick n1, but n2 is on the cheapest path, not n1.

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

We can also pick the wrong node if we include g(n). But, in that case, for some node n on the path including n1, f(n) will be greater than the cheapest path (in the worst case n will be the goal and f(n) will be the true cost to reach it through n1, which is clearly more expensive than the actual cheapest path), and thus also greater than f(n2) (since a heuristic needs to underestimate the cost), so we'll explore n2 before reaching the goal.

那么我们确实不需要 g（n）。

但是在这种情况下（假设非负边权重），仅考虑 h（n）会使它成为一个贪婪算法，因为 h（ n）对于我们选择的每个节点都会减少（因为我们正在接近目标），所以在起始节点，我们会在最佳路径上选择一个节点（因为它将具有最低的路径） h（n）），然后从那里继续选择最佳路径上的节点。

But only considering h(n) will make it a greedy algorithm in this case (assuming nonnegative edge weights), since h(n) will decrease for each node we pick (since we're moving close to the goal), so at the starting node we'd pick a node on the optimal path (since it will have the lowest h(n)), and from there we'll just keep picking nodes on the optimal path.

这篇关于为什么A-star算法需要g（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！