Iterative Deepening Search (IDS / IDDFS) — Beginner-Friendly Notes

1. What It Is (the fix for DLS)

Run DLS repeatedly with increasing limit $l = 0, 1, 2, ...$ until goal found.

for depth = 0 to infinity:
  result = DLS(initial, goal, depth)
  if result != cutoff: return result

"Try shallow first, if not found go one deeper." Like BFS in effect, but DFS in memory.

2. Why It Works Brilliantly

• Like BFS: finds shallowest goal first → optimal for uniform cost and complete.
• Like DFS: uses $O(b \cdot d)$ space → memory efficient.
• Repeats work (re-expands top levels each iteration) — but cost is dominated by deepest level, so overhead is small: total nodes ≈ $O(b^d)$.

Beginner intuition: Most nodes are at the bottom layer; re-doing upper layers adds only ~ $b/(b-1)$ extra — e.g., $b=10$, overhead ~11%.

3. Properties (exam favourite — memorise)

Property	Value
Complete	Yes (if $b$ finite)
Optimal	Yes for uniform step cost (like BFS)
Time	$O(b^d)$
Space	$O(b \cdot d)$
Best use	When you want BFS optimality but cannot afford BFS memory

4. Example Trace (goal at depth 2)

• limit 0: check root only → cutoff
• limit 1: expand root, check depth1 → cutoff
• limit 2: expand root, depth1, depth2 → finds goal → done

5. IDS vs BFS vs DFS

	BFS	DFS	IDS
Optimal (uniform)	Yes	No	Yes
Space	$O(b^d)$ huge	$O(bm)$ tiny	$O(bd)$ tiny
Time	$O(b^d)$	$O(b^m)$	$O(b^d)$

IDS is the preferred uninformed search when you don't know depth and memory is limited.

6. One-Line Summary

IDS iterates DLS with increasing depth limits, achieving BFS-like completeness and optimality with DFS-like linear space $O(b \cdot d)$ at the cost of repeated shallow expansions.

7. Quick Self-Check

1. Why is IDS optimal even though it uses DFS inside?
2. Why is repeated expansion not wasteful?