A* is an informed graph-search algorithm for finding routes between nodes. It expands the most promising unexpanded node by combining the cost already incurred, g(n), with an estimate of the remaining cost, h(n): f(n) = g(n) + h(n). This balances the actual route cost with guidance toward the destination. section 4.3.3 section 4.1
A practical A* search proceeds by:
- Initializing a frontier priority queue with the source node and tracking explored nodes. section 4.3.3
- Selecting the frontier node with the smallest combined path cost and heuristic estimate. section 4.3.3
- Expanding its children, recording routes, and stopping when the destination is found. section 4.3.3
- Choosing h(n) carefully: straight-line distance is one option, while an admissible heuristic never overestimates the remaining cost. section 4.3.3
- Using weighted A* when faster, potentially near-optimal search matters more than strict optimality; weighting increases the influence of h(n). section 4.3.3
Routing through a road network
A* can route between points of interest in a real road graph. A Python implementation uses NetworkX and OSMnx to obtain a local graph, maps geographic coordinates to graph nodes, expands neighboring nodes, and applies a routing cost and heuristic. A straight-line or Haversine distance can guide the search. The resulting route may be non-optimal when speed is prioritized over a highly accurate heuristic. section 4.4.3 section 4.3.3
Figure 4.22 The A* steps to find the shortest path between the source node S and goal node G in an 8 POIs road network. The sum of the already incurred costs and the distance to the goal is used as the heuristic value to determine whether to expand a certain node.
Trace how accumulated route costs and estimated distances determine successive node expansions from source S to goal G. section 4.3.3
