Informed (Heuristic) Search

Unit 3: Search Techniques for Problem Solving — Section 3.4

Uninformed algorithms explore blindly, with no sense of direction. When you are navigating to a destination and can see the skyline, you naturally turn toward it. Informed search formalizes that intuition: use problem-specific knowledge to guide the algorithm toward the goal instead of expanding nodes in all directions equally.

Heuristic Function h(n): A function that estimates the cost of the cheapest path from node n to the nearest goal state. A heuristic is computed from the current state alone — it looks forward without actually expanding nodes. Example: for navigation, h(n) = straight-line distance from n to the destination.

A good heuristic should be:

Fast to compute — if computing h takes longer than expanding nodes, it defeats the purpose
Informative — the closer h(n) is to the true remaining cost, the better the search performs
Never an overestimate — more on this requirement in Section 3.5

Greedy Best-First Search

Greedy best-first search always expands the node that appears closest to the goal, as measured by h(n).

Evaluation function: f(n) = h(n)

Implementation: Priority queue ordered by h(n) (lowest h first).

The algorithm is "greedy" because it makes locally optimal choices — always reaching for what looks nearest — without considering the cost of the path already traveled.

Romania route-finding: Arad to Bucharest

Using straight-line distance to Bucharest as h(n):

h(Arad) = 366 km
h(Sibiu) = 253 km
h(Fagaras) = 176 km
h(Rimnicu) = 193 km
h(Pitesti) = 100 km
h(Bucharest) = 0 km

Greedy expansion sequence: Start at Arad → expand toward Sibiu (h = 253, lowest among neighbors) → expand toward Fagaras (h = 176) → reach Bucharest.

Path found: Arad → Sibiu → Fagaras → Bucharest = 450 km

Optimal path: Arad → Sibiu → Rimnicu → Pitesti → Bucharest = 418 km

Greedy found a solution quickly, but missed the 32 km savings available via Rimnicu and Pitesti.

Property	Value	Explanation
Complete	No	Greedy can enter infinite loops or dead ends if not using graph search.
Optimal	No	Ignores path cost g(n) — finds the first solution, not the cheapest.
Time / Space	O(b^m)	Worst case explores entire space; depends heavily on heuristic quality.

Property

Value

Explanation

Complete

Greedy can enter infinite loops or dead ends if not using graph search.

Optimal

Ignores path cost g(n) — finds the first solution, not the cheapest.

Time / Space

O(b^m)

Worst case explores entire space; depends heavily on heuristic quality.

Greedy search fails at optimality because it ignores how much it cost to reach the current node. It sees only the estimated remaining distance and charges ahead, potentially accumulating a large actual cost to reach a seemingly close node.

When greedy search shines: real-time constraints, very large state spaces where any solution is acceptable, and situations where the heuristic is excellent and near-perfect guidance is available.

A* Search

A* (pronounced "A-star") is the most widely used search algorithm in AI. It combines the path cost tracking of UCS with the heuristic guidance of greedy search.

A* Evaluation Function:

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

g(n) = actual cost of the path from the start node to node n
h(n) = estimated cost from n to the nearest goal (heuristic)
f(n) = estimated total cost of the cheapest solution path that passes through n

Implementation: Priority queue ordered by f(n) (lowest f first).

By summing actual cost (g) and estimated remaining cost (h), A* avoids two failure modes:

It avoids choosing expensive paths (high g), unlike greedy search
It avoids ignoring proximity to the goal (high h), unlike UCS

Running A* step by step:

Initialize the frontier with the root node (g = 0, f = h(initial state))
Remove the node with the lowest f(n) from the priority queue
If that node passes the goal test, return the solution
Add the node’s state to the explored set
For each child node:
1. Compute g(child) = g(parent) + step cost
2. Compute f(child) = g(child) + h(child)
3. If child is not in frontier or explored, add it to the frontier
4. If child is already in frontier with a higher f, update it

A* trace: Arad to Bucharest

The same heuristic as before — straight-line distance to Bucharest.

Step	Node	g(n)	h(n)	f(n) = g+h
1	Arad (start)	0	366	366
2	Sibiu	140	253	393
3	Rimnicu Vilcea	220	193	413
4	Fagaras	239	176	415
5	Pitesti	317	100	417
6	Bucharest (goal)	418	0	418

A* chose Rimnicu before Fagaras (step 3 vs. 4) because f(Rimnicu) = 413 < f(Fagaras) = 415. It found the optimal 418 km path — the same path that greedy missed.

Why A* Is Optimal

A* is guaranteed to find the optimal solution when h(n) is admissible.

Admissible Heuristic: A heuristic h(n) is admissible if it never overestimates the cost to reach the goal: h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost from n to the goal. Admissible heuristics are optimistic — they think the goal is at least as close as it really is.

Why admissibility guarantees optimality: A* expands nodes in order of increasing f(n). When it first expands a goal node, the f value equals g — the actual path cost. If h is admissible (never overestimates), no unexpanded node can lead to a cheaper path. Therefore the first goal expanded is always optimal.

Checking admissibility — 8-Puzzle:

Heuristic h₁: count of misplaced tiles. Each misplaced tile requires at least one move. So h₁ ≤ true cost. Admissible.

Heuristic h₂: sum of Manhattan distances. Each tile must travel at least its Manhattan distance. So h₂ ≤ true cost. Admissible.

Heuristic h₃: 2 × Manhattan distance. This doubles the estimate and can exceed the true cost. Not admissible.

Property	Value	Explanation
Complete	Yes	A* will find a solution if one exists (assuming graph search and finite branching).
Optimal	Yes	Guaranteed when h(n) is admissible.
Time / Space	Exponential	A* stores all generated nodes. Memory is its primary practical limitation.

Property

Value

Explanation

Complete

Yes

A* will find a solution if one exists (assuming graph search and finite branching).

Optimal

Yes

Guaranteed when h(n) is admissible.

Time / Space

Exponential

A* stores all generated nodes. Memory is its primary practical limitation.

A*'s main real-world limitation is memory. Like BFS and UCS, it stores every generated node. For very large problems, variants like IDA* (iterative deepening A*) apply the iterative deepening trick from Section 3.3 to keep memory use at O(d).

Three Algorithms Side by Side

Algorithm	Evaluation Function	Optimal	Best For
UCS (uniform-cost)	f(n) = g(n)	Yes	No heuristic available
Greedy best-first	f(n) = h(n)	No	Quick approximate solutions
A*	f(n) = g(n) + h(n)	Yes (if h admissible)	Optimal solutions with good heuristic

Algorithm

Evaluation Function

Optimal

Best For

UCS (uniform-cost)

f(n) = g(n)

Yes

No heuristic available

Greedy best-first

f(n) = h(n)

Quick approximate solutions

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

Yes (if h admissible)

Optimal solutions with good heuristic

Visualize A* interactively at PathFinding.js (MIT License) — select "A*" and watch how f(n) guides expansion toward the goal more directly than BFS or DFS.

For an excellent conceptual walkthrough, see the Red Blob Games A* tutorial at redblobgames.com.

A* with h(n) = 0 (the "zero heuristic") reduces to uniform-cost search. A* with a perfect heuristic — one that equals the true remaining cost — would expand only nodes on the optimal path.

What does this tell you about the relationship between heuristic quality and search efficiency? How does this motivate the work of designing good heuristics (Section 3.5)?

Check your understanding of greedy search and A*.

Next: 3.5 Designing Good Heuristics →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.