Editing A* search algorithm (section)

===Admissibility===
A search algorithm is said to be ''admissible'' if it is guaranteed to return an optimal solution. If the heuristic function used by A* is [[admissible heuristic|admissible]], then A* is admissible. An intuitive "proof" of this  is as follows:

Call a node ''closed'' if it has been visited and is not in the open set.  We ''close'' a node when we remove it from the open set.  A basic property of the A* algorithm, which we'll sketch a proof of below, is that when {{tmath|n}} is closed, {{tmath|f(n)}} is an optimistic estimate (lower bound) of the true distance from the start to the goal.  So when the goal node, {{tmath|g}}, is closed, {{tmath|f(g)}} is no more than the true distance.  On the other hand, it is no less than the true distance, since it is the length of a path to the goal plus a heuristic term.

Now we'll see that whenever a node {{tmath|n}} is closed, {{tmath|f(n)}} is an optimistic estimate.  It is enough to see that whenever the open set is not empty, it has at least one node {{tmath|n}} on an optimal path to the goal for which {{tmath|g(n)}} is the true distance from start, since in that case {{tmath|g(n)}} + {{tmath|h(n)}} underestimates the distance to goal, and therefore so does the smaller value chosen for the closed vertex. Let {{tmath|P}} be an optimal path from the start to the goal.  Let {{tmath|p}} be the last closed node on {{tmath|P}} for which {{tmath|g(p)}} is the true distance from the start to the goal (the start is one such vertex).  The next node in {{tmath|P}} has the correct {{tmath|g}} value, since it was updated when {{tmath|p}} was closed, and it is open since it is not closed.