A-Star

A* is a widely used graph traversal and pathfinding algorithm that finds the path from a given initial node to a given final node while minimizing the total cost (distance plus any other costs). It uses a combination of Best First Search and Dijkstra’s algorithm.

Demo

See this Jupyter notebook for an example of A* in action:

Basics of A*

\(g(n)\): the exact cost of the path from the starting point to any vertex \(n\).
\(h(n)\): the estimated cost from vertex \(n\) to the goal. This is the heuristic part of the algorithm.
\(f(n)\): the estimated total cost of the cheapest path from the start to the goal that goes through \(n\). It's computed as: \(f(n) = g(n) + h(n)\)

How A* works:

Initialize the open list with the starting node.
While the open list is not empty:
- Find the node with the lowest \(f(n)\) in the open list.
- Pop the node from the open list.
- Generate the node's successors and set their parents to the current node.
- For each successor:
  - If successor is the goal, reconstruct and return the path.
  - Else, compute its \(f(n)\) value and place it in the open list.
If the open list is empty and we haven't found the goal, a path doesn't exist.