Questions: Problem Formulation and Uninformed Search Strategies

Question 1

Actions in a route-finding problem have different costs (road lengths). Which uninformed strategy is guaranteed to return a lowest-cost path, assuming all costs are positive?

• A. Breadth-first search
• B. Depth-first search
• C. Uniform-cost search
• D. Depth-limited search

Answer: (C)

Uniform-cost search always expands the frontier node with the lowest path cost g(n), so the first goal it selects for expansion has the cheapest path. Breadth-first search minimizes the number of actions, which is not the same when costs differ. Depth-first and depth-limited search give no cost guarantee.

Question 2

With branching factor b and shallowest solution depth d, what is the space requirement of iterative deepening search?

• A. O(b^d)
• B. O(bd)
• C. O(d)
• D. O(b^(d/2))

Answer: (B)

Each iteration is a depth-limited depth-first search, which stores only the current path plus the unexpanded siblings along it, about b nodes per level for d levels. Breadth-first search needs O(b^d) memory, and O(b^(d/2)) describes bidirectional search.

Question 3

Iterative deepening search repeats so much work that its time complexity is worse than O(b^d).

• T. True
• F. False

Answer: False

Nodes at depth d are generated once, at depth d - 1 twice, and so on. Because the deepest level holds most nodes, the total is still O(b^d). For b = 10 and d = 5, Russell and Norvig count about 123,450 nodes for iterative deepening against about 111,110 for breadth-first search.

Question 4

Breadth-first search is run on a problem with branching factor 10 and a shallowest solution at depth 8. Why is memory, rather than time, often the first limit hit?

Model answer: Breadth-first search must keep the entire frontier in memory, and at depth 8 that is on the order of 10^8 nodes. Even at a modest number of bytes per node, that can exceed available memory before the time becomes unacceptable.

This is the motivation for iterative deepening, which matches breadth-first search's completeness and its optimality for unit costs while needing only O(bd) memory.