Iterative deepening and heuristic functions
Iterative deepening search (IDDFS) trades extra node generation for linear memory; heuristic functions (admissible, consistent) guide informed search like A* and determine optimality and efficiency.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two short sentences: Iterative deepening search (IDDFS) is used when the solution depth is not known but memory is limited — it gives the time performance of breadth-first search with the memory of depth-first search. Heuristic functions are used in informed search (for example A*) to estimate remaining cost to the goal; their properties (admissible, consistent) decide whether A* finds an optimal path and how many nodes it expands.
Key ideas
Start from first principles and define terms before use.
State space: a set of nodes (states) and edges (actions) connecting them with non-negative step costs. We assume a finite branching factor b (each node has at most b successors) and that action costs are non-negative.
Depth-first search (DFS): an uninformed search that explores as deep as possible along each branch before backtracking. Uses O(b·m) memory where m is maximum search depth.
Breadth-first search (BFS): explores the search tree level by level (in order of increasing depth). For a goal at depth d and branching factor b, BFS expands O(b^{d}) nodes but requires O(b^{d}) memory to store the frontier.
Iterative deepening depth-first search (IDDFS): run depth-limited DFS with limits 0,1,2,... until a goal at depth d is found. Each iteration does a DFS limited to depth L. Assumptions: branching factor b is finite and depth of solution d is finite. Advantages: memory O(b·d), time still O(b^{d}).
Exact count of node generations for IDDFS when goal is at depth d (tree, uniform branching): Let n_i = number of nodes at depth i = b^{i}. Each node at depth i is generated in every iteration with limit >= i, that is (d - i + 1) times. Thus total nodes generated S is S = sum_{i=0}^{d} (d - i + 1) b^{i}.
This sum simplifies (for b != 1) to the closed form S = (b^{d+2} - (d+2) b + d + 1) / (b - 1)^{2}.
Asymptotically S = Theta(b^{d}). So IDDFS has the same exponential order as BFS but with a small constant factor overhead; memory is O(b·d).
Heuristic function: a function h(n) that estimates the cost from node n to the nearest goal. We assume non-negative heuristic values and that the true minimal cost from n to goal is h(n)*.
Admissible heuristic: h is admissible iff for every node n, h(n) ≤ h*(n). That is, it never overestimates the true minimal cost to goal. Assumption: h(goal) = 0 (goal has zero remaining cost).
Consistent (or monotone) heuristic: h is consistent iff for every edge (n, m) with step cost c(n,m) ≥ 0, we have h(n) ≤ c(n,m) + h(m). Another equivalent statement: for every successor m of n, f(n) ≤ f(m) where f(x) = g(x) + h(x) and g(x) is the cost from the start to x. Consistency implies admissibility (provided h(goal) = 0).
Dominance: Given two admissible heuristics h1 and h2, we say h2 dominates h1 if for all n, h2(n) ≥ h1(n). If h2 dominates h1, A* with h2 will never expand more nodes than A* with h1 (it may expand fewer), assuming identical tie-breaking, for tree-search; for graph-search with a closed set, this guarantee holds when both heuristics are consistent.
A optimality: If h is admissible then A tree-search (which expands nodes in order of increasing f(n) = g(n) + h(n)) returns an optimal path to the goal. For graph-search with a closed set, optimality is guaranteed if h is consistent; with an admissible but inconsistent heuristic, optimality can be preserved only if the algorithm allows reopening nodes when a better g-value is discovered. If h is consistent, A* with a closed-set (explored set) is easier to implement because f-values along any path are non-decreasing; nodes need not be reopened with better g-values.
Standard proof sketch (admissible ⇒ optimal): Suppose A* has found a goal node G with path cost C. If there were a better path with cost C* < C, then there must be at least one open node n on that optimal path with f(n) ≤ C*. Since A* always expands the lowest f-value first, it would have expanded that node (and eventually reach that cheaper goal) before returning G with cost C. Contradiction. Therefore C = C*.
Diagrams to draw in an exam when explaining IDDFS: draw a small tree with branching factor b=2 up to depth 3. Label levels 0,1,2,3. Mark how many times nodes at each level are generated across iterations L=0..3 (e.g., nodes at level 0 generated 4 times, level 1 generated 3 times, etc.). For heuristics and A*: draw a small graph with start, intermediate nodes, and two goal paths of different costs. Label g, h and f values on nodes and show why admissible h cannot make A* pick the longer path.
Formulas
Nodes_BFS_up_to_depth_d = (b^{d+1} - 1) / (b - 1) — b is branching factor (no unit), applies when tree is full and b != 1.
IDDFS_total_nodes_for_goal_at_depth_d = (b^{d+2} - (d+2)·b + d + 1) / (b - 1)^{2} — b branching factor, d goal depth, applies for b != 1, tree model.
Asymptotic_IDDFS = Theta(b^{d}) — same exponential order as BFS; memory O(d).
Admissible: h(n) ≤ h*(n) for all n — h*(n) is true minimal cost from n to a goal.
Consistent: h(n) ≤ c(n,m) + h(m) for every edge (n,m) — c(n,m) is step cost (SI unit: cost unit; typically unitless in algorithmic cost).
f(n) = g(n) + h(n) — g(n) is cost from start to n, h(n) heuristic estimate to goal.
Note: for algorithmic syntax remember simple IDDFS skeleton:
- for limit = 0..infty:
- do depth_limited_DFS(start, limit)
- if goal found return path
Worked examples
- Count nodes generated by IDDFS (numerical exam-style).
Given b = 3 (branching factor), goal at depth d = 4. Use the closed form formula.
Formula:
S = (b^{d+2} - (d+2)·b + d + 1) / (b - 1)^{2}Compute step by step:
- b^{d+2} = 3^{6} = 729
- (d+2)·b = 6·3 = 18
- d + 1 = 5
- numerator = 729 - 18 + 5 = 716
- denominator = (3 - 1)^{2} = 2^{2} = 4
- S = 716 / 4 = 179
So IDDFS generates 179 nodes in total. Compare to BFS nodes up to depth 4:
(3^{5} - 1)/(3 - 1) = (243 - 1)/2 = 121. Memory: IDDFS uses O(b·d) space (for b=3 and d=4, at most about 12 nodes on the recursion stack), whereas BFS uses Theta(b^{d}) space (frontier size around b^{d} = 81 at the deepest level). Final answer: 179 nodes generated by IDDFS.
- Heuristic example (theory/model answer): 8-puzzle small state and heuristic values. Goal state (3x3): 1 2 3 4 5 6 7 8 _
Initial state S: 1 2 3 4 5 6 7 _ 8
Compute heuristics at S:
- Misplaced tiles: only tile 8 is not in its goal place → h_misplaced(S) = 1.
- Manhattan distance: tile 8 is one move away (one left) → h_manhattan(S) = 1. Check admissibility: both heuristics ≤ true minimal moves (true minimal moves = 1), so admissible. Check consistency on the one applicable action: move blank right swapping blank and 8 gives goal state G with h(G)=0 and c(S,G)=1. Consistency requires h(S) ≤ c(S,G) + h(G) → 1 ≤ 1 + 0 holds. Therefore both heuristics are consistent here. Model answer explains general proofs: Manhattan is admissible because each tile must move at least its Manhattan distance; Manhattan is consistent because moving one tile changes its Manhattan contribution by at most 1, so h(n) ≤ 1 + h(m).
- Model proof question: Show IDDFS is optimal in memory and discuss time compared to BFS. Model answer should derive the sum S (as above), conclude Theta(b^{d}) time, and O(d) memory; show BFS is Theta(b^{d}) time but O(b^{d}) memory. Diagrams and the closed-form sum answer earn full marks.
Common mistakes
- Believing a heuristic must be exact to be useful — even admissible underestimators can greatly reduce search.
- Forgetting to state assumptions (finite branching factor, positive costs) when asserting complexities.
- Using the tree-node-count formula for graphs with repeated states without explaining duplicate detection (graph search vs tree search differences).
For your exam
Typical question formats and what full-marks answers include:
- Definition questions: define IDDFS, admissible, consistent — give formal inequalities and explain assumptions (h(goal)=0, costs non-negative).
- Short note: compare BFS, DFS, IDDFS — include time and space complexities and a small illustrative diagram.
- Derivation: derive the closed-form node-count formula for IDDFS. Show the summation steps: S = sum_{i=0}^{d} (d - i + 1) b^{i} and transform to closed form (algebra or geometric series identity). State b != 1 case explicitly.
- Proof: prove that consistency implies admissibility and explain why A* with an admissible heuristic is optimal (contradiction proof with f-values). Include the role of h(goal)=0.
- Numerical: compute S for given b and d — carry units (nodes) and show each arithmetic step.
- Diagram: draw a small tree and label repeated generations across IDDFS iterations.
To get full marks always: state assumptions, show algebraic steps (do not skip the geometric-series identity), and justify why graph-search vs tree-search differences (duplicate states) matter.
Quick check
- Define an admissible heuristic in one line.
- What is the space complexity of IDDFS in terms of solution depth d?
- For a full b-ary tree, give the asymptotic time complexity of IDDFS for a goal at depth d. Answers: 1. h(n) ≤ h*(n) for all n (never overestimates true cost). 2. O(b·d). 3. Theta(b^{d}).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?