在使用可接受的启发式算法时，A* 是否需要知道最佳解决方案成本? [英] Does A* need to know the optimal solution cost while utilizing an admissible heuristic?

问题描述

我已经阅读了一些关于这个主题的 stackoverflows，以及关于 A* 的维基百科，但我仍然有点困惑.我认为这篇文章几乎完全向我解释了它:

1. 从绿色节点开始，A* 探索具有最小成本 + 启发式(1.5 + 4 = 5.5，节点a")的节点.成本 + 启发式可以理解为到那里需要多少加上我认为留给目标的多少".换句话说，它是目标的估计总成本.所以我们选择最小值是有道理的.节点d"的成本较高(2 + 4.5 = 6.5)，因此我们将其留在队列中.
2. 通过扩展 'a' 邻居，我们将 'b' 添加到队列中并计算它的值，即 1.5 + 2 + 2 = 5.5(在粗体之前的成本，另一个术语是我认为还剩多少).它仍然比'd'的成本要好，所以我们继续探索这条路.请注意，'b' 中的启发式是 2，这意味着我们认为这是达到目标所需的额外成本......这显然是错误的，没有办法从 'b' 以成本 2 到达那里！但这对 A* 算法没有问题，因为我们低估了实际成本.
3. 扩展 'b'，我们添加它的邻居 'c' 以 1.5 + 2 + 3 + 4 = 10.5 的值做队列.现在，还记得 'd' 还在队列中吗?现在它具有最小值 (6.5)，因此我们将 'c' 留在队列中并尝试使用 'd'，因为这是一条更有希望的路径.这个决定是可能的，因为我们知道只有达到 'c' 的成本为 6.5，而我们认为达到目标仍然有 4 的成本.在这种情况下，启发式是正确的，这对于 A* 算法也是可以的.
4. 通过扩展 'd'，我们将 'e' 添加到队列中，值为 2 + 3 + 2 = 7.这里的启发式是正确的，我们已经知道这对 A* 来说是可以的.然后我们将探索e"并找到目标.但假设我们有 h(e) = 6，给 'e' 的值 2 + 3 + 6 = 11.这意味着 'c' 将是下一个最佳猜测(10.5)，我们将尝试一条无望的道路！这意味着高估启发式不可接受，因为它使A*走错了探索路径.

如果您正在寻找证据，这里是维基百科关于可采性的非正式证据:

<块引用>

当 A* 终止搜索时，它找到了一条路径，其实际成本低于通过任何开放节点的任何路径的估计成本.但由于这些估计是乐观的，A* 可以安全地忽略这些节点.换句话说，A* 永远不会忽视低成本路径的可能性，因此是可以接受的.

为了优化:

<块引用>

现在假设某个其他搜索算法 B 以一条路径终止其搜索，该路径的实际成本不小于通过某个开放节点的路径的估计成本.基于它所拥有的启发式信息，算法 B 不能排除通过该节点的路径具有较低成本的可能性.因此，虽然 B 考虑的节点可能比 A* 少，但它是不可接受的.因此，A* 考虑了任何可采用的搜索算法的最少节点.

您可能还想查看此视频:A* 最优性证明.

I've read through a few stackoverflows on this topic, as well as the wikipedia on A* but I'm still a little confused. I think this post almost explained it completely to me: A* heuristic, overestimation/underestimation?

My only confusion left is, how does the A* know the optimal solution? It seems like with an admissible heuristic, you can throw out paths that exceed the known optimal solution, because the heuristic is guaranteed to be less than or equal. But how would A* know the optimal ahead of time?

Would this search work and guarantee an optimal solution if you didn't know the optimal path cost?

解决方案

A* does not know the optimal solution, the heuristic gives only an educated guess which helps to accelerate the search process. Seeing that you already read some theoretical explanations, let's try a different approach here, with an example:

1. Starting at the green node, A* explores the node with the smallest cost + heuristic (1.5 + 4 = 5.5, node 'a'). Cost + heuristic can be read as "how much until there plus how much I think is left to the goal". In other words, it's the estimated total cost to the goal. So it makes sense that we select the smallest value. Node 'd' has a higher cost (2 + 4.5 = 6.5), so we just leave it at the queue.
2. By expanding 'a' neighbors, we add 'b' to the queue and compute its value, which is 1.5 + 2 + 2 = 5.5 (cost until there in bold, the other term is how much I think is left). It is still better than the cost for 'd', so we keep exploring this path. Note that the heuristic in 'b' is 2, which means that we think that this is the addional cost remaining to get to the goal... which is clearly wrong, there is no way to get there from 'b' with cost 2! But it poses no problem to the A* algorithm, because we are underestimating the real cost.
3. Expanding 'b', we add its neighbor 'c' do the queue with value 1.5 + 2 + 3 + 4 = 10.5. Now, remember that 'd' is still in the queue? And now it has the smallest value (6.5), so we leave 'c' in the queue and try 'd' because it is a more promising path. This decision is possible because we know that it has a cost of 6.5 only to get to 'c', and we think that there is still a cost of 4 to get to the goal. In this case, the heuristic is correct, which is also ok for the A* algorithm.
4. By expanding 'd' we add 'e' to the queue with value 2 + 3 + 2 = 7. The heuristic here is correct, which we already know that is ok for A*. Then we would explore 'e' and find the goal. But let's suppose we had h(e) = 6, giving 'e' a value of 2 + 3 + 6 = 11. It would mean that 'c' would be the next best guess (10.5) and we would try a hopeless path! It means that overestimating the heuristic is not admissible, since it makes A* take the wrong exploration path.

If you're looking for proofs, here is an informal one from Wikipedia for admissibility:

When A* terminates its search, it has found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A* can safely ignore those nodes. In other words, A* will never overlook the possibility of a lower-cost path and so is admissible.

And for optimality:

Suppose now that some other search algorithm B terminates its search with a path whose actual cost is not less than the estimated cost of a path through some open node. Based on the heuristic information it has, Algorithm B cannot rule out the possibility that a path through that node has a lower cost. So while B might consider fewer nodes than A*, it cannot be admissible. Accordingly, A* considers the fewest nodes of any admissible search algorithm.

You may also want to check this video: A* optimality proof.

这篇关于在使用可接受的启发式算法时，A* 是否需要知道最佳解决方案成本?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！