An admissible heuristic is used to estimate the cost of reaching the goal state in an informed search algorithm.
A* algorithm (pronounced ``Astar'') an algorithm for heuristic search, using an 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*.
(**) This should never happen if you have an monotone . 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
