A* is a pathfinding algorithm that uses heuristics to guide its search. It can be considered as a generalization of Dijkstra’s algorithm. A* only finds a path between two given nodes, where as Dijkstra’s algorithm finds the shortest path tree from a start node.
¶ Variables and Functions
A* formulates the problem space using a weighted directed graph and uses the following variables and functions:
- cij: cost of the arc going out from node i to node j.
- g(n): the cost of the path from start node s to n with minimum cost so far found by A*.
- h(n): heuristic function that estimates the cost of the cheapest path from n to the goal node. If the heuristic function is admissible, A* is guaranteed to find an optimal path. If h(n) is also consistent, nodes never need to be reopened once closed.
- f(n): evaluation function or f-value. Defined as follows: f(n)=g(n)+h(n)
- OpenSet: a min-priority queue containing all currently open nodes, ordered by their f-values.
- Γ(ni): successor operator. Yields all the successors nj of ni and the arc costs cij.
Following pseudocode is adapted from the original article :
- First mark s as open, calculate the f(s) and add it to the priority queue.
- Select the open node n whose f-value is smallest from the queue. Resolve ties arbitrarily, but always in favor of any goal node.
- If n is a goal node, mark n as closed and terminate the algorithm.
- Otherwise, mark n as closed and apply the successor operator Γ to n. Calculate f-values for each successor of n and mark as open each successor not already marked closed. Go to Step 2.