Search Strategy Completeness in Infinite-Depth State Spaces
To answer which strategy is not complete in infinite-depth spaces, we need the notion of Completeness. In many classic AI search texts, completeness depends on whether the problem space has (at least) finite branching and on how the algorithm allocates its exploration budget across depths.
For the four options:
- (i) Breadth-First Search (BFS)
- (ii) Depth-First Search (DFS)
- (iii) DFID (Iterative Deepening Depth-First Search, IDDFS)
- (iv) [ Search]{def="Best-first search using f(n)=g(n)+h(n) to expand lowest estimated total cost."}
A standard result is:
- BFS is complete in infinite-depth spaces if branching is finite.
- DFS is not complete in infinite-depth spaces in general, because it can get trapped exploring an infinite path.
- DFID (IDDFS) is complete under the same usual conditions (finite branching), because it systematically increases the depth limit and eventually reaches any finite-depth solution.
- is complete if it uses an admissible (and typically consistent) heuristic and the branching factor is finite; it will expand enough nodes to find a solution when one exists.
This means the expected answer is:
The strategy that is not complete in infinite-depth spaces is (ii) Depth-First Search (DFS).
Visual intuition (why DFS fails)
Explore Related Topics
FIFO Branch-and-Bound Uses a Queue
FIFO Branch-and-Bound expands live nodes in the exact order they are generated, so it is implemented with a queue.
- A queue enforces first‑in‑first‑out, giving the algorithm a BFS‑like, level‑order traversal.
- LIFO Branch‑and‑Bound uses a stack and least‑cost Branch‑and‑Bound uses a priority queue.
- Bounding prunes unpromising nodes independently of the FIFO selection rule.
- Pseudocode: initialize , enqueue root, while dequeue front, generate children, enqueue survivors.
- The abstract answer is “queue,” not an array or other structure, even if an array may implement a queue.
Binary Search Complexity: Why the Correct Choice is $O(\log n)$
Optimal Approach for the 0/1 Knapsack Problem