Uninformed Search Strategies Questions and Answers

Answer: C

Depth first needs only the current path and the unexpanded siblings along it, which is the branching factor times the maximum depth, an enormous saving over breadth first's exponential frontier. That single property is why it remains useful. Graph search versions lose the advantage by storing an explored set. A strategy whose memory requirement grows linearly where the alternative grows exponentially will always have a place, whatever its other weaknesses.

Answer: D

In an infinite space, or one with loops in a tree search implementation, the algorithm may follow a single branch forever without ever examining the branch containing the goal. Depth limiting and cycle detection restore completeness in the finite case. Memory is its strength, and it does eventually reach every state in a finite acyclic space. An algorithm that fails only in infinite spaces is still unusable when the space is large and the depth unknown.

Answer: A

Imposing a limit turns an infinite branch into a finite one, so the search terminates, but it becomes incomplete if the goal lies deeper than the limit. Choosing the limit requires knowledge of the problem, such as the diameter of the state space. Node count limits and stack limits are implementation concerns. Trading one failure mode for another, non-termination for incompleteness, is what motivates the iterative version that follows. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: B

Running depth limited search with a limit of zero, then one, then two and so on gives the completeness and optimality of breadth first with the linear memory of depth first. The repeated work is much smaller than it appears. It is the standard choice when the space is large and the solution depth unknown. Combining the guarantees of one algorithm with the memory profile of another, at modest cost, is an unusually clean result.

Answer: C

In a tree with branching factor b, the bottom level holds more nodes than all the levels above it combined, so regenerating the upper levels adds only a constant factor of about b over b minus one. For a branching factor of ten that is eleven per cent. Nothing is remembered between iterations, and no pruning occurs. An overhead that appears alarming until the exponential is examined is a good illustration of why complexity arguments must be done rather than estimated.

Answer: D

Summing the repeated generations gives a ratio of b over b minus one:

\[ \tfrac{10}{9} \approx 1.11 \]

so the total work is about 1.11 times that of a single breadth first pass, an overhead of eleven per cent. For a branching factor of two it rises to a factor of two, which is why the argument is weakest for narrow trees. Doing the arithmetic rather than trusting the intuition that repetition must be expensive is the lesson here.

Answer: A

Ordering the frontier by the cost of the path from the start makes the search expand cheap paths first, which guarantees optimality with any non-negative step costs. Shallowest is breadth first, an estimate to the goal would be a heuristic, and most recent is depth first. Uniform cost is Dijkstra's algorithm arrived at from the search direction, and recognising them as the same algorithm connects two literatures.

Answer: B

A goal node may be generated by an expensive path while a cheaper route to it is still on the frontier, so returning it immediately would break optimality. Testing when the node is selected for expansion guarantees no cheaper path remains. Breadth first can safely test on generation because all edges cost the same. A small implementation detail that determines whether a guarantee holds is exactly the kind of thing worth being precise about. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: C

Non-negative costs are needed for correctness and a strictly positive lower bound is needed for completeness, since a sequence of zero cost steps could otherwise be followed forever without the path cost rising. Equal costs are the special case where breadth first suffices, and integrality and boundedness are not required. A condition that rules out an infinite sequence of free actions is easy to overlook and occasionally matters in practice. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: D

Running two searches that meet in the middle replaces one search of depth d with two of depth d over two, reducing the node count from b to the d down to twice b to the d over two. For b of ten and d of six that is a thousand nodes instead of a million. Bidirectional edges, strategy alternation and parallel problems are different notions. Halving an exponent is a far larger saving than any constant factor improvement.