Uninformed Search Strategies Questions and Answers

Answer: A

The first two are correct. Depth first search returns the first goal it encounters, which may be at any depth, so it is not optimal even with unit costs. It is the trade for its linear memory. The three statements between them cover completeness, space and optimality, which is three of the four standard criteria, and the third is the one depth first fails.

Answer: B

The entire family differs only in how the frontier is ordered, and every property follows from that one choice. An implementation can switch between them by changing the container, which makes the comparison concrete rather than abstract. Iterative deepening is the exception in being a wrapper around repeated depth limited searches rather than a single discipline, which is why it appears as a strategy rather than a data structure.

Answer: C

The first three are correct. Iterative deepening uses linear space, since each iteration is a depth first search, which is precisely the property that makes it attractive. Confusing its space complexity with breadth first's, on the grounds that it shares breadth first's guarantees, is the natural error, and it inverts the whole reason the algorithm exists.

Answer: D

Breadth first, uniform cost and iterative deepening all find a solution if one exists at finite depth. Depth first tree search may descend an infinite branch forever and never return, so it is incomplete in an infinite space. Adding a depth limit or cycle detection restores completeness in the finite case. The odd one out is the algorithm whose only advantage, memory, is bought by surrendering a guarantee.

Answer: A

Both are true and the second is the reason. Because memory rather than time is usually the binding constraint, an algorithm that matches breadth first's guarantees while needing only the current path is preferable whenever the space is large. The cost is regenerating the upper levels, which the exponential structure of the tree makes cheap. Trading a small time penalty for a large memory saving is almost always the right bargain when the memory is what runs out first.

Answer: B

The transition model, sometimes written as a successor function, says what each action does in each state, and together with the initial state it defines the whole state space implicitly. Path cost, goal test and the explored set are separate components. Defining the space implicitly rather than enumerating it is what allows problems with astronomically many states to be posed at all, and it is why search algorithms generate rather than look up. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Answer: C

A puzzle with ten to the twenty states cannot be listed, but the rule generating successors from any given state is a few lines long, so the space is described by a procedure and explored as needed. That is why search algorithms speak of generating successors. Convenience is a side benefit, the goal is irrelevant to enumeration, and the model is fixed. Describing an enormous object by the rule that produces it is the only way such problems can be approached.

Answer: D

Path cost sums the step costs along a route and is the quantity uniform cost search minimises and optimality is defined against. An estimate of the remaining cost is a heuristic and belongs to informed search, node count is a complexity measure, and goal testing is assumed cheap. Keeping the cost incurred so far distinct from the cost yet to come is what makes A star's combination of the two comprehensible.

Answer: A

The answer wanted is the sequence of actions, since knowing the goal state without knowing how to reach it is usually useless, and that sequence is recovered by following parent pointers back from the goal node. The visited set is a by-product and the minimum cost is a property of an optimal solution rather than the solution. Being clear about what the algorithm is asked to return determines what bookkeeping the nodes must carry.

Answer: B

Each node stores the node it was generated from and the action that produced it, so the path is read off by walking up the chain and reversing it. That is the whole reason nodes carry parents rather than being bare states. Replaying, backward search and the explored set order would all be more expensive or incorrect. A small amount of bookkeeping per node, chosen so that the required output can be reconstructed, is a general design pattern. Checking the units of each quantity catches a wrong formula before the arithmetic begins.