A* finds a shortest path by prioritizing each vertex with an f-score: the cost already incurred from the source plus a heuristic estimate of the remaining cost to the goal. This combines distance information with domain knowledge to focus the search on promising routes. section 14.5 section 14.5.2
Implement A* around these operations:
- Accept a graph, a start vertex, a goal predicate, an edge-distance function, and a heuristic function. section 14.5
- Initialize a priority queue, tentative distances, f-scores, and parent links; assign the start vertex its heuristic score. section 14.5
- Repeatedly remove the highest-priority vertex, stop when it satisfies the goal predicate, and otherwise relax its outgoing edges. section 14.5
- Use compatible units for edge distances and heuristic estimates; rescale estimates when they represent time, speed, or another related metric. section 14.5.2
Route planning with live traffic
A delivery navigator can use travel time as its distance metric while using typical route times as a heuristic. When traffic makes one route slower than usual, the heuristic helps balance live conditions against longer-term route expectations. section 14.5.2
Listing 14.7 The A* algorithm
function aStar(graph, start, isGoal, distance, heuristic) #1
queue ← new PriorityQueue() #2
queue.insert(start, 0) #3
distances[v] ← inf (∀ v ϵ graph | v <> start) #4
fScore[v] ← inf (∀ v ϵ graph | v <> start) #5
parents[v] ← null ( v ϵ graph) #6
distances [start] ← 0 #7
fScore[start] ← heuristic(start)
while not queue.empty() do #8
v ← queue.top() #9
if isGoal(v) then #10
return (v, parents)
else
for e in graph.adjacencyList[v] do #11
u ← e.dest
if distances[u] > distances[v] + distance(e) then #12
distances[u] ← distance(e) + distances[v] #13
fScore[u] ← distances[u] + heuristic(u) #14
parents[u] ← v
queue.update(u, fScore[u])
return (null, parents) #15
Inspect the pseudocode for A* initialization, priority-queue processing, goal detection, and neighbor updates. section 14.5
