Admissibility of A*
Following are the three conditions which should be satisfied for A* to find the optimal least cost path.
- All nodes in the graph have a finite number of successors (or 0).
- All arcs of graph have costs greater than some constant positive amount, says e.
- The heuristic condition: For each node in the graph, n, h'(n) < h(n). That is, the heuristic guess of the cost of getting from node n to the goal is never an overestimate.
If these three conditions are met, then A* is guaranteed to find the least cost path and is said to be admissible.
A very interesting observation about A* algorithm is that it is admissible for any node on such path, h'(n) is always less than or equal to h(n). This is possible only when the evaluation function value never overestimates the distance of the node to the goal. Although the admissibility condition requires h'(n) to be a lower bound on h(n), it is to be expected that the more closely h'(n) approaches h(n), the better is the performance of the algorithm. We have already discussed that if h(n) were identically equal to h'(n),
an optimal solution path would be found without over expanding a node off the path (assuming of course only one optimal solution exists). If h'(n) is identically zero, A* reduces to blind uniform cost algorithm (or breadth first).
Admissible heuristics are by nature optimistic, because they think that the cost of solving the problem is less than it actually is since g(n) is-the exact cost for each n. We have an immediate consequence that f(n) should never overestimate the true cost of a solution through n.
This becomes clear by the following example. Consider a road map linking various cities . If the problem Is to find a path between two distant cities which minimizes the mileage (and therefore fuel cost) then an admissible heuristic would be to use "as the crow flies" distances to estimate the costs from a given city to the goal city. The air distance will always be either equal or underestimate the real distance, i.e., h'(n) ≤ h(n).
