Uninformed Search Strategies Questions and Answers

Answer: C

For many problems no useful heuristic is known, and the uninformed strategies then define what is achievable and provide the baseline against which any heuristic is measured. They also form the skeleton on which informed strategies are built, since A star is uniform cost with an added term. Speed, guarantees and code size are secondary. Understanding the case with no information is what allows the value of information to be quantified.

Answer: D

Both order the frontier by a cost, and A star uses the path cost so far plus an estimate of the cost remaining, so uniform cost is the special case where that estimate is always zero. Recognising the relationship shows why A star inherits uniform cost's optimality when the heuristic is admissible. Bidirectionality and inadmissibility are separate variations, and the two are not identical for unit costs. Seeing one algorithm as a special case of another organises the whole family.

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.