Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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

  1. 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.
  1. 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).
  1. 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

  1. Define an admissible heuristic in one line.
  2. What is the space complexity of IDDFS in terms of solution depth d?
  3. 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?