A* Pathfinding & Heuristics Notes & Questions | Class 12 Future Skills & AI | Drishti OS

What you'll learn

What graph search is and why it matters for AI
The A* evaluation function f(n) = g(n) + h(n)
What makes a heuristic admissible
How A* uses open and closed sets
Manhattan vs Euclidean heuristics and when to use each
How A* compares to Dijkstra's algorithm and BFS

Key concepts

Graph Search

Many AI problems — navigation, puzzle solving, route planning — can be modelled as finding a path through a graph of nodes (states) and edges (transitions).

Goal: Find the optimal (lowest-cost) path from a start node to a goal node.

The A* Evaluation Function

A* assigns a score to every node it considers:

f(n) = g(n) + h(n)

Term	Meaning
f(n)	Total estimated cost of the cheapest path through node n
g(n)	Actual cost from the start node to node n (known)
h(n)	Heuristic estimate of cost from n to the goal (estimated)

A* always expands the node with the lowest f(n) next.

Admissible Heuristic

A heuristic h(n) is admissible if it never overestimates the true cost to the goal.

h(n) ≤ h(n)* for all n, where h*(n) is the true optimal cost.

If h is admissible, A* is guaranteed to find the optimal path.

Admissible: straight-line distance (never longer than the actual road distance)
Not admissible: an estimate that sometimes exceeds the true cost

Open and Closed Sets

Set	Contents
Open set	Nodes discovered but not yet fully explored (priority queue ordered by f)
Closed set	Nodes already expanded (no need to revisit)

A Algorithm:*

Add start node to the open set with f = h(start).
Remove the node with lowest f from the open set.
If it is the goal → return the path.
Otherwise: add it to the closed set; expand its neighbours.
For each neighbour: calculate g, h, f; if not in closed set, add/update in open set.
Repeat from step 2.

Manhattan vs Euclidean Heuristics

Heuristic	Formula	Grid type
Manhattan	h =	x₁−x₂
Euclidean	h = √[(x₁−x₂)² + (y₁−y₂)²]	Any direction (diagonal movement allowed)

Manhattan distance is preferred for grid maps where diagonal movement is not allowed (e.g., many game maps, tile-based worlds). It is always admissible in this setting.

Euclidean distance is admissible when diagonal movement is permitted.

Comparison with Dijkstra and BFS

Algorithm	Heuristic?	Finds optimal path?	Speed
BFS	No (uniform cost)	Yes (for unweighted graphs)	Slow (explores in all directions equally)
Dijkstra	No	Yes (for weighted graphs)	Moderate (explores by cost, no goal direction)
A*	Yes (h guides search)	Yes (if h is admissible)	Fast (focuses search toward goal)

Key insight: Dijkstra is A* with h(n) = 0. A* with a perfect heuristic (h = h*) expands the minimum number of nodes possible.

Example: Grid Pathfinding

S . . . .
. # # . .
. . . # .
. . . . G

S = Start, G = Goal, # = Wall

BFS: explores many wrong directions before finding G.
Dijkstra: finds optimal path but explores widely.
A* (Manhattan): focuses search toward G efficiently, visiting far fewer nodes.

Quick check

Write the A* evaluation function and explain what each term (f, g, h) represents. Why does A* expand the lowest-f node first?
A heuristic h(n) for a road navigation problem estimates travel time as "straight-line distance ÷ speed limit." Is this admissible? Justify your answer.
On a grid where only up/down/left/right moves are allowed, why is Manhattan distance preferred over Euclidean distance as a heuristic?
How does Dijkstra's algorithm differ from A*? Under what condition does A* reduce to Dijkstra's algorithm?
An A* search with an inadmissible heuristic finds a path quickly but the path is not optimal. Explain why an overestimating heuristic causes this problem.

A* Pathfinding & Heuristics