Uninformed Search Strategies Questions and Answers

Answer: A

A problem is fully specified by where the agent starts, what it can do, what each action leads to, how to recognise success and what a path costs. Everything else, including the frontier, the search tree and the choice of algorithm, belongs to the solution rather than the problem. Heuristics belong to informed search. Separating the problem from the method is what allows the same problem to be attacked by several algorithms and compared fairly. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: B

A node carries a state together with its parent, the action that reached it, the path cost and the depth, so two different nodes may hold the same state reached by different routes. That distinction is what makes graph search possible and what allows a solution path to be recovered. Storage and goal testing are not the difference. Confusing the bookkeeping structure with the thing it describes causes most of the confusion in first encounters with search.

Answer: C

The frontier, or open list, holds the nodes at the edge of the explored region, and the order in which nodes are taken from it is what distinguishes one strategy from another. The explored set holds what has been expanded, and the current path is a separate notion used by depth first search. Recognising that every uninformed strategy differs only in the frontier's ordering discipline makes the whole family easy to remember.

Answer: D

Breadth first takes the shallowest node, depth first the deepest, uniform cost the cheapest, and that single choice determines completeness, optimality and both complexities. None of them uses a heuristic, which is exactly what uninformed means. Representation and goal testing are shared. Seeing the whole family as one algorithm with different queue disciplines is the cleanest way to hold it in mind.

Answer: A

Taking nodes in the order they were generated expands the shallowest first, which is breadth first search. A stack gives depth first, a priority queue on path cost gives uniform cost, and an arbitrary order gives no useful guarantees. The correspondence between the data structure and the strategy is exact, which is why an implementation can switch strategy by changing one line.

Answer: B

Breadth first examines every node at depth d before any at depth d plus one, so if a solution exists at any finite depth it will be found, provided each node has finitely many successors. It does not loop, since repeated states are detected, and an infinite state space is no obstacle so long as the solution is at finite depth. Completeness under a stated condition is worth more than an unqualified claim, and the condition here is mild. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: C

Breadth first finds the shallowest goal, which is the cheapest only if cost increases with depth, that is when all actions cost the same. With varying costs a deeper path may be cheaper and uniform cost search is needed instead. Branching factor and repeated states affect efficiency rather than optimality. A guarantee that holds only under a condition must always be stated with it, and this condition is the one most often forgotten.

Answer: D

Raising the branching factor to the depth gives:

\[ 10^{6} = 1000000 \]

so about one million nodes. At a million nodes a second that is a second of computation but around a gigabyte of memory, which is why space rather than time is usually the binding constraint. Working the numbers for a realistic branching factor is the quickest way to see why exhaustive search fails on anything but small problems.

Answer: A

The frontier grows as the number of nodes at the current depth, which is the same exponential as the time, but a modern machine generates nodes far faster than it can store them, so memory is exhausted first. A million nodes a second fills a gigabyte in minutes. The state space is never enumerated in advance, and nodes are discarded as they are expanded. Identifying which resource binds first decides which algorithm is actually usable. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: B

Expanding the most recently generated node drives the search down one branch until it can go no further, which is depth first search, and it is often implemented by recursion rather than an explicit stack. A queue gives breadth first, and a priority queue on depth would simply reproduce breadth first. Hash tables are used for the explored set. The choice of container is the whole of the difference between the two fundamental strategies. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.