A* Search
A search technique that finds minimal cost solutions and is also directed towards goal states is called “A* (A-star) search”. (The “star” comes from the notation that the inventors of this technique used when they described it. I think that their typewriter didn’t have many options.)
To see how A* works, consider using the following quantity as the heuristic value H(state) for a given state:
H(state) = Cost(state) + Estimate(state)
Where:
Cost(state) = actual cost incurred in reaching the state
Estimate(state) = estimate of cost needed to get from state to goal
In Best-First search and Hill Climbing, the estimate of the distance to the goal was used alone as the heuristic value of a state. In A*, we add the estimate of the remaining cost to the actual cost needed to get to the current state.
To prove that A* search will find the minimal cost solution, if one exists, we need to show that it will consider the solution with the minimal cost before it considers any states with higher cost. If this can be proved, then it follows that A* will find the lowest cost solution.
Suppose, as above, that the minimal cost solution has cost Cmin. We need to show that A* will only examine states with cost less than Cmin before it examines any with greater cost. In the following diagram, I have shown two sequences of states in a search space. One, involving the states S1 and S2, is, we shall assume, the minimal cost solution, and has cost Cmin. The other, involving the states S3 and S4, has some other cost, Calt, which is greater than Cmin, and has not yet found a solution.

We need to prove that state S2 will be expanded before any state like S4, whose cost is greater than the cost of the minimal solution.
To assure that this will happen, it must be the case that:
Cost(S4) + Estimate(S4) > Cost(S2) + Estimate(S2)
But we know that the cost of S4 is Calt, so this would mean that:
Calt + Estimate(S4) > Cost(S2) + Estimate(S2)
We assumed that Calt > Cmin, so if it is the case that
Cost(S2) + Estimate(S2) <= Cmin
then there is no way that state S4 could be expanded before S2 is, no matter what value that Estimate(S4) has (even if it is zero).
Let us use Actual(state) to represent the actual distance from state to a goal. For state S2, we know that:
Cost(S2) + Actual(S2) = Cmin
So to ensure that state S2 will be expanded before any states that would led to a more costly solution, it is necessary to have a way to estimate the distance to the goal such that:
Estimate(state) <= Actual(state)
That is: The heuristic estimate of the distance from the state to the goal must be less than or equal to the actual minimal distance from that state to the goal. If it is, then A* search is guaranteed to find the minimal cost solution.
One way that Estimate(state) could be less than Actual(state) would be if Estimate(state) is always zero. In that case we have the minimal cost based search described above. It too will find the minimal cost solution, but is not guaranteed to find it in any reasonable amount of time.
The A* search technique combines being “guided” by knowledge about where good solutions might be (the knowledge is incorporated into the Estimate function), while at the same time keeping track of how costly the whole solution is.
One domain in which it is possible to find an estimate function that satisfies the requirement above happens to be the driving domain. The straight-line distance between two points will always be less than or equal to the distance it actually takes you to drive between those two points. And in fact A* was designed to find optimal solutions to navigation problems. But there are other domains in which heuristic estimate functions that satisfy the above constraint can be found, and A* has been applied to them also.