A* Search (A-Star)

A\* ("A-star") was published in 1968 and remains the workhorse of route-planning, game AI, and any search problem with a sensible distance heuristic. It extends Dijkstra's algorithm by adding a heuristic estimate **h(n)** — an optimistic guess of the remaining cost from node **n** to the goal. At each step, A\* expands the frontier node with the lowest **f(n) = g(n) + h(n)**, where **g(n)** is the known cost from start to **n**.

## Why A* is important

When the heuristic is *admissible* (never overestimates the true remaining cost), A\* is guaranteed to find the optimal path. When it is also *consistent* (satisfies the triangle inequality), A\* expands each node at most once — efficient in both time and memory.

The heuristic is what separates A\* from brute-force search. For a road network, straight-line distance is admissible — actual road distance is never shorter than the crow-flies distance. For a grid, Manhattan distance works. For chess, piece-value differentials serve as an approximate heuristic. The quality of the heuristic determines how much of the search space A\* can prune.

## Limitations and alternatives

A\* struggles in very large state spaces where even the pruned search tree does not fit in memory. Variants address this:
- **IDA\*** (Iterative Deepening A\*): explores iteratively with increasing cost bounds, using O(depth) memory instead of O(nodes).
- **SMA\*** (Simplified Memory-Bounded A\*): drops the worst frontier nodes when memory is exhausted.
- **Bidirectional A\***: simultaneously searches from start and goal, meeting in the middle.

## Relevance to modern AI

Modern deep learning systems largely replaced explicit graph search with learned policies. But A\* still powers:

- **Navigation**: every mapping and logistics system routes on graph search variants — Google Maps, Waze, and DHL's routing layer all use heuristic search under the hood.
- **Planning in agentic AI**: multi-step AI agents doing task planning (chain-of-thought + tool use) implicitly perform search. Explicit A\* or Monte Carlo Tree Search (MCTS) is sometimes combined with neural value functions (AlphaGo-style).
- **Game AI**: pathfinding in real-time strategy games, puzzle solvers, and simulation environments.

For APAC enterprise teams, the practical relevance is in **logistics optimisation**: delivery route planning, warehouse picking paths, and supply chain scheduling all reduce to graph search at scale. When data volumes exceed what A\* can handle interactively, learned heuristics (neural networks that estimate h(n)) replace hand-crafted ones.