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)$
Algorithm Property for Clear, Unambiguous Steps: Definiteness
The course clarifies that definiteness is the algorithm property requiring every step to be precise and have exactly one interpretation, distinguishing it from finiteness, effectiveness, and generality.
- Definiteness: each instruction is specified so precisely that only one meaning is possible.
- Finiteness concerns termination, effectiveness concerns executability, and generality concerns applicability to all valid inputs.
- Example: “repeat 3 times” is definite, while “repeat several times” is not.
- Exam tip: associate words like “clear,” “precise,” or “unambiguous” with definiteness.
- Algorithm quality can be expressed as .