A* (A-star) is a search algorithm that can be thought of as an improved version of Dijkstra’s Algorithm that uses heuristics to obtain the shortest path.
It uses the evaluation function to decide which path to follow next.
- refers to the distance of the node (the property that Dijkstra’s uses)
- is a heuristic function. Different heuristics can be used for different cases.
The heuristic must be admissible i.e. does not overestimate costs. So long as the heuristic function provides an estimate that is less than or equal to the actual cost, A* will always find an optimal path, generally faster than Dijkstra’s algorithm.
Heuristic Function
The better suited the heuristic, the better A* outperforms Dijkstra’s. Some common heuristics include:
- Euclidean Distance: The straight line distance:
- Manhattan Distance: The grid distance:
Pseudocode
Algorithm A*(Graph,source,goal):
unexplored_nodes ← Set ADT
cwn ← Node ADT
For each vertex v in G do: #O(|V|)
v.dist ← ∞
v.h ← None
v.value ← v.h + v.dist
v.parent ← None
Add v to unexplored_nodes
End do
source.dist ← 0
v.h ← h(v,goal) #Where h is the heurstic function
v.value ← v.h + v.dist
While unexplored_nodes is not empty do: #O(|V|)
cwn ← node in unexplored_nodes with lowest value
Remove cwn from unexplored nodes
For each neighbour n of cwn do: #O(|V|)
if n not in unexplored_nodes then:
this_dist ← cwn.dist + weight(cwn-n)
if this_dist < n.dist then:
n.dist ← cwn.dist + weight(cwn-n)
n.h ← h(n, goal)
n.value ← n.h + n.dist
n.parent ← cwn
End if
End if
End do
End do
Return nodes.dist, nodes.parent
End Algorithm