An admissible heuristic is used to estimate the cost of reaching the goal state in an informed search algorithm. In order for a heuristic to be admissible to the search problem, the estimated cost must always be lower than or equal to the actual cost of reaching the goal state.
A* algorithm (pronounced ``Astar'') an algorithm for heuristic search, using an admissible heuristic function f(n) = g(n) + h(n), where g(n) is the known cost to reach node n from the start, and h(n) is the estimated cost from node n to a goal.
The classic algorithm for finding shortests paths given an admissible heuristic. We'll deal with the notion of admissibility (summary: admissible = optimistic). We show how you can prove properties of A*. We'll also briefly discuss IDA* (iterative deepening A*). ...
(**) This should never happen if you have an monotone admissible heuristic. However in games we often have inadmissible heuristics. Source code ...
In addition, an admissible heuristic function such as the cost of the minimum spanning tree of the remaining unvisited cities, can be added to the cost so far of a partial tour to increase the amount of prunin.
See also: Algorithm, Bidirectional search, Search algorithm, System, AI
