A* Search-Artificial intelligence:
A* search combines the best parts of uniform cost search that called the fact that it's optimal and complete, and the best parts of greedy search that called its speed. This search method simply combines the path cost function g(n) and the heuristic function h(n) by summing them to form a new heuristic measure f(n):
f(n) = h(n) + g(n)
Remembering that g(n) gives the path cost from the began state to state n and h(n) estimates the path cost from n to a goal state, we see that f(n) estimates the cost of the cheapest solution which passes through n.
The most essential aspect of A* search is that, given one limitation on h(n), it is possible to prove that the search strategy is complete and optimal. The limitation to h(n) is that it might always underestimate the cost to achieve a goal state from n. Such heuristic measures are called admissible. See Norvig and Russell for verification that A* search with an admissible heuristic is complete and optimal.