Uninformed Search Strategies Questions and Answers

Answer: A

Evaluating both expressions:

\[ 2 \times 10^{3} = 2000 \text{ against } 10^{6} \]

so two thousand against one million, a saving of five hundred fold. The gain grows with depth, which is why the technique is worth its considerable implementation difficulty on deep problems. Halving an exponent transforms a problem's feasibility in a way that no constant factor ever can.

Answer: B

Working backwards needs the predecessors of a state, which is easy in a symmetric puzzle and awkward or impossible when actions are not invertible or when the goal is described by a property rather than a specific state. Interleaving on one processor is routine, meeting is detected by intersecting the frontiers, and memory is dominated by the smaller exponents. A technique whose applicability depends on a structural property of the problem must be checked against that property first.

Answer: C

Both build a search tree; the difference is that graph search remembers which states it has already expanded and discards duplicates, which prevents loops and exponential blowup from repeated paths. The price is storing every expanded state. The underlying problem may be a graph in either case. Naming the algorithms by whether they remember, rather than by what they search, avoids the confusion the conventional names invite.

Answer: D

In a grid where each state has several routes to it, a tree search expands the same subtree once for every distinct path, turning a polynomial state space into an exponential search tree. The explored set collapses that to one expansion per state. Goal testing and cost remain correct, and termination fails only with genuine loops. The distinction between the size of a state space and the size of the tree over it is one of the most consequential in the subject.

Answer: A

The explored set grows with the number of distinct states visited, which destroys depth first search's linear memory advantage and makes graph search comparable to breadth first in space. Techniques such as storing only a bounded cache trade completeness for memory. Paths are recovered by parent pointers, the space is never enumerated in advance, and successors are computed on demand. Every guarantee in search costs memory, and the accounting is worth doing explicitly.

Answer: B

A loopy path is a special case of a redundant path in which the same state appears twice, and it can always be shortened by removing the loop, so it is never part of an optimal solution. Detecting loops along the current path is cheaper than a full explored set and is enough to make depth first search complete in a finite space. Return to the start and negative costs describe different situations. Cheap partial cycle detection is often the right compromise when memory is scarce.

Answer: C

The branching factor appears as the base of the exponential in every complexity bound, so reducing it matters far more than any constant factor improvement. It is an average over the states actually encountered rather than a maximum. Goal count and solution depth are separate parameters, and the action count bounds it above but may exceed it when actions are inapplicable. Knowing which parameter sits in the exponent tells you where effort will pay. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Answer: D

Summing the levels from the root to the solution depth gives:

\[ 1 + 3 + 9 + 27 + 81 + 243 = 364 \]

so about 364 nodes. The bottom level alone accounts for 243 of them, which is the observation that makes iterative deepening cheap. Noticing that the last level dominates the sum is the single most useful fact about exponential trees and it explains several results at once.

Answer: A

For a branching factor above two the bottom level exceeds the sum of all the others, so any analysis of an exponential tree is dominated by its last level. That is why iterative deepening's repeated work is cheap and why any pruning near the bottom is worth far more than pruning near the top. Memory per node, goal testing and generation cost are uniform. A structural fact about exponentials that determines several algorithmic conclusions is worth internalising rather than rederiving.

Answer: B

The standard four ask whether a solution will be found if one exists, whether it will be the best one, how long it takes and how much memory it needs. Every textbook comparison table has these as its columns. The other lists mix software engineering and logical properties. Having a fixed set of questions to ask of any new algorithm is what makes the family comparable rather than merely enumerable.