Uninformed Search Strategies Questions and Answers

Answer: A

Every uninformed strategy has time complexity exponential in the solution depth, so the family collectively defines the limit of what can be done without problem specific knowledge. Improving within the family changes the memory profile and the guarantees but not the exponent. That conclusion is exactly what motivates informed search, and understanding why no rearrangement of the frontier can escape the exponential is what makes the value of a heuristic clear.

Answer: B

Lacking any information beyond the problem definition, the algorithm has no basis for preferring one branch over another and in the worst case must examine them all. A heuristic supplies exactly that basis, which is why informed search can do better. Data structures and goal testing contribute constant factors, and state spaces are not always exponential. Identifying the missing ingredient, rather than the inefficiency, is what points to the remedy. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: C

Depth first may explore the entire tree down to the maximum depth before finding a goal, so its time bound involves the maximum depth rather than the solution depth, which can be far worse than breadth first even though its memory is far better. In a space with a small maximum depth the two are comparable. Stating a complexity in terms of the right parameter matters as much as getting the functional form right, and here the parameter is what distinguishes the two algorithms.

Answer: D

Because it completes each level before starting the next, breadth first never touches a node below the level containing the goal, so its work is bounded by the solution depth. Depth first has no such guarantee. Cost ordering belongs to uniform cost, memory is a consequence rather than a cause, and goal testing order is a detail. The parameter appearing in a complexity bound follows directly from the order in which the algorithm works, which is why the two bounds differ.

Answer: A

Optimal efficiency is a statement about how few nodes an algorithm can get away with expanding given the information it has, and A star with a consistent heuristic has this property. It is quite distinct from optimality, which concerns the solution returned. Memory and wall clock speed are separate measures. Two properties both called optimal, meaning different things, is an unfortunate collision of vocabulary and one worth guarding against explicitly.

Answer: B

Writing the five components down, estimating the branching factor and depth and hence the size of the space, and only then selecting a strategy is the order that avoids implementing something that could never have worked. A back of the envelope estimate takes minutes and frequently rules out whole families of approach. Implementing first and comparing afterwards wastes the effort the estimate would have saved. Estimating before building is unglamorous and reliably worthwhile.

Answer: C

A dead end is a state from which the goal cannot be reached, either because it has no successors or because everything beyond it is also unproductive. Depth first search must explore it fully before backtracking, which is why detecting dead ends early is valuable. Expanded states, depth limits and cost bounds are different notions, though a cost bound produces a similar effect. Recognising futility before spending effort on it is what pruning techniques are for.

Answer: D

When a branch runs out of unexplored successors without reaching a goal, the search must return to the most recent node with alternatives remaining and try the next one. That is exactly what a stack, or recursion, provides automatically. No states are skipped, the frontier order is fixed, and costs are accumulated incrementally. An algorithm whose control structure is provided free by the language's call stack is unusually simple to implement, which is part of its durability.

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.