Algorithms A and A*:
Algorithm A is a version of
best-first search that tries to find shorter paths to the goal than regular
best-first. The algorithm is exactly the same as in best-first; it is the heuristic that differs.
The value used to sort the nodes in the agenda becomes the sum of the best-first heuristic and the length of the path to get to the node. That is, if you have two alternative routes:
Start ------------------------- Node A - - - - Goal
7 branches Heuristic
estimate: Sum: 10
3 branches
Start ------- Node B - - - - - - Goal
4 branches Heuristic
estimate: Sum: 8
4 branches
Then ordinary best-first search will look at node A first (it has a better heuristic estimate). Algorithm A, however, will sum the two values together, and look at node B first.
Algorithm A* is almost identical to algorithm A. However, it has one more condition; the heuristic for estimating the distance still to go must be optimistic. That is, it must never overestimate how far away the goal is. In the picture above, the goal must be at least 3 branches away from node A, and at least 4 branches away from node B.
The effect of this condition is that algorithm A* always finds the shortest path to the goal. (As opposed to best-first, which finds the most obvious path, and algorithm A, which finds a fairly short path, but not neccessarily the shortest.)
The only disadvantage to algorithms A and A* is that they take up a lot of memory; almost as much as breadth-first search. This can be fixed in an algorithm similar to iterative deepening, known as 'IDA(*)' (Iterative Deepening A / A*).