Does A* need to know the optimal solution cost whi

Question

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?

Answer 1

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.

Answer 2

It achieves it by passing through all possible variants/chances using heuristic method. So you will have all needed tiles/vertices/waypoints in you closed list.