Uninformed Search Strategies Questions and Answers

Answer: A

Depth limited search treats nodes at the limit as leaves, so a goal deeper than the limit is never reached and the search fails, though a solution exists. Distinguishing failure from proof of insolubility requires reporting whether the limit was reached, which good implementations do. Returning something suboptimal or ignoring the limit would defeat its purpose. An algorithm that can fail for two different reasons should say which, or its output cannot be acted upon.

Answer: B

If no node was truncated at the limit, the space below was fully explored and the absence of a solution is proved; if the limit was reached anywhere, the search is simply inconclusive and a deeper limit may succeed. Iterative deepening relies on that distinction to know when to stop. Memory, formulation errors and timeouts are unrelated. Returning enough information to distinguish two very different outcomes costs one boolean and saves considerable confusion.

Answer: C

The loop ends either with a solution or with an iteration in which no node was truncated, which proves the space is finite and contains no goal. Without the second condition the algorithm would loop forever on an insoluble finite problem. Fixed maxima, memory and node counts are not sound termination conditions. Building the proof of exhaustion into the termination test is what makes the algorithm complete rather than merely usually successful.

Answer: D

The overhead factor is b over b minus one, so a branching factor of two doubles the work while a branching factor of ten adds only eleven per cent. For very narrow trees the argument for iterative deepening weakens considerably. Completeness, memory and optimality are unaffected. A justification that depends on a parameter must be rechecked whenever that parameter is unusual, and a branching factor of two is exactly such a case.

Answer: A

The geometric sum is dominated by its last term, so the total is close to b to the d multiplied by b over b minus one, and for practical purposes the leading term is what matters. Products and inverted exponents describe quite different growth. Being able to write down the leading behaviour of a sum immediately, rather than evaluating it term by term, is what makes complexity comparisons quick enough to be worth doing.

Answer: B

A strategy that needs a thousand times the memory or a million times the work will not be rescued by optimisation, so the decision must be made from the complexity analysis rather than by trying and measuring. Implementations are of course changeable, and formulation and language are independent of the choice. That algorithmic decisions dominate implementation quality, by margins no amount of optimisation can close, is the practical justification for complexity analysis as a discipline.

Answer: C

Uninformed, or blind, search uses only the initial state, the actions, the transition model, the goal test and the path costs, and nothing else. Any additional guidance, however obtained, makes the search informed. Distance estimates are heuristics, prior statistics are learned guidance and precomputed structure is an abstraction. Defining a family by exactly what information it is denied is what makes the comparison with informed search meaningful.

Answer: D

Completeness turns a negative result into information: if a complete algorithm reports failure on a finite space, the problem genuinely has no solution, whereas an incomplete algorithm's failure tells you nothing at all. That distinction matters greatly when the search is part of a larger reasoning process. Termination bounds, optimality and memory are the other three criteria. The value of a guarantee lies in what may be concluded when it holds and nothing is found.

Answer: A

Depth first search in an infinite space may be descending a fruitless branch forever, and a depth limited search may simply have looked too shallow, so neither absence of result licenses any conclusion. That is why iterative deepening reports whether any node was truncated. Reporting, timing and goal testing are not the issue. Knowing what may be inferred from a null result is as important as knowing what may be inferred from a positive one.

Answer: B

Estimating the branching factor and the depth gives the node count, and that one number determines whether any exhaustive strategy is feasible and hence whether a heuristic or a reformulation is essential. It takes a minute and frequently changes the whole approach. Language, deadline and prior art matter but follow from it. Making the decisive estimate first, before any commitment, is the habit that separates a designed solution from a hopeful one.