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

问题描述

我已经阅读了有关该主题的一些stackoverflows以及A *上的Wikipedia，但我仍然有些困惑.我认为这篇文章几乎可以完全向我解释: 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?

我唯一剩下的困惑是，A *如何知道最佳解决方案?在允许的启发式方法看来，您可以抛出超出已知最佳解的路径，因为可以保证启发式方法小于或等于.但是A *会如​​何提前知道最优值?

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 *不知道最佳解决方案，该启发式方法仅提供了有根据的猜测，有助于加速搜索过程.看到您已经阅读了一些理论上的解释，让我们在这里尝试一个不同的方法，并举一个例子:

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. 从绿色节点开始，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，这意味着我们认为这是为达到目标而剩余的额外成本...这显然是错误的，无法从成本为2的"b"中达到目标！但这对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 *采取了错误的探索路径.

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.

如果您正在寻找证明，这里是Wikipedia的非正式证明，以供受理:

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

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

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.

为求最佳:

现在假设其他某种搜索算法B终止搜索的路径，该路径的实际成本不小于通过某个开放节点的路径的估计成本.基于其具有的启发式信息，算法B无法排除通过该节点的路径成本较低的可能性.因此，尽管B可能考虑的节点少于A *，但它是不可接受的.因此，A *会考虑所有允许的搜索算法中最少的节点.

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.

您可能还需要观看以下视频: A *最优性证明.

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

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