CodeWithYash

Advanced · Module 19 · Lesson 8

A* search

Guide shortest-path exploration with an admissible heuristic.

15–25 min readLesson 122 of 123

Lesson 122 of 123

1d streak

Theory lesson · Step-by-step

Understand A* search

Guide shortest-path exploration with an admissible heuristic.

Worked approach

Trace the reasoning step by step

  1. 1Store best known g-costs.
  2. 2Pop the smallest estimated total cost.
  3. 3Relax neighbors.
  4. 4Stop when the goal is settled only when the chosen heuristic and reopen policy make that termination rule sound.

Concrete example

Navigate a grid using Manhattan distance to the goal.

  1. 1Priority is g(n)+h(n).
  2. 2Expand the smallest estimated total path.
  3. 3Update a neighbor when a cheaper g is found.

Tree-search A* is optimal with an admissible heuristic. Graph-search A* also needs a consistent heuristic or must reopen a node when a cheaper path is found.

What must remain true (Loop Invariant)

The priority is g(node) + h(node). An admissible heuristic never overestimates remaining cost; graph search must also use a consistent heuristic or reopen nodes whose best g-cost improves.

Cost Model

Complexity & Trade-offs

Graph processing
Problem-dependent
O(V)
Assumes adjacency-list representation unless stated otherwise.

When to use it

  • Large constraints requiring specialized string, range, geometry, or network tools.
  • Repeated queries or updates that justify preprocessing.
  • Problems with a strong algebraic, heuristic, or residual invariant.

Common mistakes

  • Using a specialized structure without checking its operation assumptions.
  • Mixing zero-based and one-based indexes.
  • Memorizing formulas without proving what each stored value means.

Practice prompts

  • Reproduce the worked A* search example without looking at the trace.
  • Change one input condition and explain whether the A* search invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.