The A Algorithm

In its simplest form as described above, best first search is useful, but doesn't take into account the cost of the path so far when choosing which node to search from next. So, you may find a solution but it may be not a very good solution. There is a variant of best first search known as A which attempts to find a solution which minimizes the total length or cost of the solution path. It combines advantages of breadth first search, where the shortest path is found first, with advantages of best first search, where the node that we guess is closest to the solution is explored next.

In the A algorithm the score which is assigned to a node is a combination of the cost of the path so far and the estimated cost to solution. This is normally expressed as an evaluation function f, which involves the sum of of the values returned by two functions g and h, g returning the cost of the path (from initial state) to the node in question, and h returning an estimate of the remaining cost to the goal state:

f(Node) = g(Node) + h(Node)

The A algorithm then looks the same as the simple best first algorithm, but we use this slightly more complex evaluation function. (Our best node now will be the one with the lowest cost/score). To illustrate what A buys us, consider the following search tree where successor links are labelled with the cost of getting between nodes and the scores attached to nodes are again an estimate of the cost to solution:

If we use simple best first search we would search the nodes in the following order: A, B, D, E, F. As F is our goal state we'd have a solution, but it would not be a particularly good one. It will have a path cost of 13 (2+4+3+4). If we use A, then the nodes will be searched in the following order: A, B, C, G, F', with the solution path found being the better right hand path with cost 7. In fact, the A algorithm guarantees to find the shortest path first. However, to make this true we have to ensure that h(Node) does not overestimate the cost to the solution. The definition of the A algorithm includes this requirement.