Uninformed Search Strategies Questions and Answers

Answer: A

Multiplying the node count by the size gives:

\[ 10^{9} \times 100 = 10^{11} \]

bytes, that is about 100 gigabytes, beyond most machines. The same search would take about seventeen minutes at a million nodes a second, which is why memory rather than time is the binding constraint. Comparing the two resources explicitly, in the units the machine actually has, is the calculation that decides which algorithm is usable.

Answer: B

A processor generates millions of nodes a second but a machine holds only a few tens of millions of hundred byte nodes, so the memory is exhausted in seconds while the computation could have continued for hours. That asymmetry is why linear space algorithms matter so much. Access latency, permanence and expandability are secondary. Comparing the rates at which two resources are consumed identifies which will run out first, which is the only question that matters.

Answer: C

The state space is every configuration reachable from the start, which for the eight puzzle is half of the nine factorial arrangements, since parity divides them into two unreachable halves. Moves define the transitions, the solution path is one route through the space, and there is a single goal. Noticing that only half the arrangements are reachable is a useful example of problem structure that a naive state count would miss.

Answer: D

A single tile move is a transposition combined with a blank move, and the combination preserves an invariant, so configurations of the wrong parity can never be reached however many moves are made. Half of all arrangements are therefore unsolvable from any given start. Blank reachability, move counts and goal definitions are not the reason. An invariant that partitions a state space is worth looking for, since it can halve the search or prove a problem unsolvable without any search at all.

Answer: A

If the start and the goal differ in an invariant that no action can change, no path between them exists and the search can be abandoned immediately, which is worth more than any speedup. Invariants may also suggest heuristics and abstractions. They do not alter the branching factor or the complexity class directly. Reasoning about a problem before searching it is consistently more valuable than searching it faster, and invariants are the cheapest form of such reasoning.

Answer: B

Formulating locations as states, the roads between them as actions and the distance or time as the step cost makes route finding a uniform cost search problem directly. The other formulations either invert the roles or introduce a continuum where a discrete graph suffices. Choosing what counts as a state is the first and most consequential modelling decision in any search problem, and a natural choice usually makes the rest straightforward. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: C

With unequal step costs the shallowest route is not the shortest, so ordering the frontier by accumulated distance is required for optimality. Breadth first would return the route with fewest turnings rather than the shortest. Size, direction and loops are handled by graph search and by the algorithm's structure. Matching the frontier ordering to the quantity actually being minimised is the whole of choosing between these strategies.

Answer: D

With two squares and two dirt conditions the whole space has eight states and can be drawn on a page, so every algorithm's behaviour can be traced exactly. It is deliberately trivial as a problem and valuable as an illustration. Continuous, multi-agent and partially observable variants exist and are used to introduce those complications one at a time. A worked example small enough to verify by hand is worth more when learning than a realistic one that cannot be checked.

Answer: A

If the agent cannot see which square it is in or where the dirt is, it must reason about sets of possible states and find a sequence of actions that works whatever the true state is. Such a conformant plan often exists. The space of belief states is exponentially larger but still discrete and finite. Lifting a search problem from states to belief states is the standard treatment of partial observability and it reuses every algorithm unchanged. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: B

In a sensorless problem the agent must find one sequence that reaches a goal from every state it might be in, and such a plan is called conformant. It is often surprisingly achievable: a vacuum agent can clean both squares blindly. Safety constraints, language conformance and adaptive replanning are different notions. That a fixed sequence can succeed under complete ignorance of the state is a counter-intuitive and useful result.