A* search algorithm

“A* search is an informed search algorithm used for path-finding and graph traversal. It combines the advantages of both Dijkstra’s algorithm (in that it can find a shortest path) and Greedy Best-First-Search (in that it can use a heuristic to guide search). It combines the information that Dijkstra’s algorithm uses (favoring vertices that are close to the starting point) and information that Best-First-Search uses (favoring vertices that are closer to the goal).

Let g(n) represent the exact cost of the path from the starting point to any vertex n, and h(n) represent the heuristic estimated cost from vertex n to the goal. Dijkstra’s algorithms builds a priority queue of nodes ordered on their g(n) values. Best-First-Search employs a priority queue of nodes ordered on h(n) values. A* balances the two as it moves from the starting point to the goal. It builds a priority queue of nodes ordered on f(n) = g(n) + h(n) which is the total estimated path cost through the node n…”

https://kartikkukreja.wordpress.com/2013/12/28/a-star-search/

Advertisements