Uninformed Search Strategies Questions and Answers

Answer: C

Wherever two routes lead to the same state, a tree search will expand that state's subtree twice, and with many such states the search tree becomes exponentially larger than the state space. The explored set of graph search removes the redundancy. Dead ends, heuristic quality and null actions are different phenomena. The distinction between the size of the space and the size of the tree over it is what makes the explored set worth its memory. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Answer: D

In a grid a state at distance d can be reached by very many routes, so the tree has exponentially many nodes over a merely quadratic state space. Where the space is already a tree the two coincide, and irreversible or single action problems produce no redundancy either. Recognising in advance whether a space contains many alternative routes decides whether graph search is essential or merely tidy.

Answer: A

Storing expanded states means each is expanded once, so the work becomes proportional to the number of states rather than to the number of paths, which is a change of complexity class. Memory rises rather than falls, and the solution found and the completeness are unchanged for breadth first. A structural change that alters the exponent is worth far more than any constant factor, and it is bought here with memory.

Answer: B

Exponential growth means a small increase in depth multiplies the frontier size by the branching factor, so a program that fits comfortably at one size fails abruptly at the next. Switching to iterative deepening usually resolves it. A leak would show on small instances too, branching factor is usually constant, and goal testing is cheap. Abrupt failure at a slightly larger size is the characteristic signature of an exponential, and it points at the algorithm rather than at the code.

Answer: C

Iterative deepening retains completeness and optimality with unit costs while reducing the memory from exponential to linear, at a modest cost in repeated work. More memory buys only one extra level for each multiplication by the branching factor, a depth limit sacrifices completeness, and earlier goal testing saves a constant factor. Attacking the exponent rather than the constant is the only response that changes what is feasible.

Answer: D

Doubling the memory buys a fraction of one extra level of depth when the requirement grows as ten to the depth, so hardware improvement is hopeless against an exponential. Only a better algorithm, a heuristic or a reformulation of the problem changes the outcome. Addressing limits, speed and efficiency are secondary. That hardware growth cannot outrun exponential problem growth is the central practical lesson of complexity analysis.

Answer: A

Abstracting away irrelevant detail, such as ignoring which particular tile is where when only a count matters, can collapse an enormous space into a manageable one. It is often far more effective than any algorithmic improvement. Goal restatement, hardware and decomposition are related techniques, the last being valuable in its own right. Changing the problem is frequently the most powerful move available, and it is the one most often overlooked. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: B

If a representation distinguishes states that behave identically, the space is multiplied by the number of irrelevant variations, and abstracting them away can reduce it by orders of magnitude. Node size, goal test cost and branching factor are affected too but are secondary. Asking what distinctions the problem actually requires, before choosing a representation, is the cheapest way to make a search feasible.

Answer: C

Raising the branching factor to the depth gives:

\[ 4^{8} = 65536 \]

so 65536 nodes at that level, and about 87000 in the whole tree. The bottom level holds three quarters of them, which is the usual pattern. Working an exponential out for concrete numbers, rather than reasoning about it in the abstract, is what makes the growth vivid enough to influence a design decision.

Answer: D

Dividing the node count by the rate gives:

\[ \tfrac{10^{12}}{10^{6}} = 10^{6} \]

seconds, which is about 11.6 days. Two more levels of a tree with branching factor ten would take three years. Converting node counts into wall clock time is what turns an abstract complexity into a decision about whether a program can be run at all, and it should be done before the program is written.