Informed and Heuristic Search Questions and Answers

Answer: B

In scheduling, layout and configuration problems the answer is the final arrangement rather than the sequence of edits that produced it, so nothing is lost by forgetting the path. Small spaces admit anything, provable optimality is exactly what local search sacrifices, and irreversibility is unrelated. Asking whether the path is part of the answer is the first test of whether local search applies, and it is a question about the problem rather than about the algorithm.

Answer: C

Hill climbing examines the neighbours of the current state and moves to the best one, stopping when no neighbour is better. It is simple, uses constant memory and is trapped by local maxima, ridges and plateaux. Abstraction hierarchies, frontier ordering and depth increase describe other algorithms. The greedy local move is the simplest possible search rule, which makes its characteristic failures the clearest illustration of why more elaborate methods exist.

Answer: D

A local maximum traps hill climbing, since every move looks worse and the algorithm stops with a suboptimal answer. Random restarts, sideways moves and simulated annealing are the standard escapes. A flat region of equal neighbours is a plateau, and the best state overall is the global maximum. Naming each failure mode separately matters because each has its own remedy, and applying the wrong one wastes effort.

Answer: A

On a plateau no neighbour is better and none is worse, so a strict hill climber halts while allowing sideways moves may let it cross to higher ground. The risk is an infinite sideways walk, so a limit on consecutive sideways moves is imposed. Steep regions, clustered maxima and basin boundaries are different features. A landscape whose flat regions are as troublesome as its peaks is a reminder that the difficulty lies in the shape of the space rather than in the algorithm.

Answer: B

A ridge ascends diagonally while the available moves are axis aligned, so every single move goes downhill and the climber halts although higher ground lies just off the axis. Larger neighbourhoods or compound moves escape it. Drops, direct paths and plateau sequences describe other features. A failure caused by the mismatch between the shape of the landscape and the set of available moves points at redesigning the moves rather than the algorithm.

Answer: C

If each attempt succeeds with probability p, about one over p restarts are needed, and for many problems that is a very small number, so the crude expedient of trying again from somewhere else is remarkably effective. Occasional random moves are stochastic hill climbing and random neighbour choice is random walk. Turning an algorithm that usually fails into one that usually succeeds by repetition is a general and underrated technique.

Answer: D

Simulated annealing sometimes accepts a downhill move, with a probability falling as a temperature parameter is lowered, so the search explores widely at first and settles into a peak later. With a sufficiently slow cooling schedule it converges to the global optimum with probability approaching one. Step size reduction and combination of searches are different techniques. Borrowing a physical annealing process as an optimisation schedule is one of the field's more successful metaphors.

Answer: A

A strict climber cannot leave a local maximum, whereas one that occasionally goes downhill may cross a valley to a higher peak, and the falling temperature ensures it eventually settles. Evaluation cost, termination and memory are unaffected. Deliberately accepting a worse state, and controlling how often, converts a greedy procedure into a global one, which is a surprisingly general trick.

Answer: B

The probability follows an exponential in the ratio of the value decrease to the temperature, so small decreases are accepted readily and large ones rarely, and both become less likely as the temperature falls. That is exactly the Boltzmann factor from statistical mechanics. Neighbour counts, distance and iteration counts are not part of the rule. A rule borrowed intact from physics, and behaving in the intended way, is the reason the analogy is more than decorative.

Answer: C

Local beam search holds k states, generates all their successors and keeps the best k overall, so information is shared and effort concentrates where progress is being made. That sharing is what distinguishes it from k independent restarts. The risk is that all k states converge into one region, which stochastic beam search mitigates. Sharing information between parallel attempts, rather than running them independently, is the idea that also underlies population based methods.