Informed and Heuristic Search Questions and Answers

Answer: A

Keeping a short list of recently visited configurations and refusing to return to them forces the search out of a local optimum and prevents immediate cycling. The list length controls how far it is driven. Constraint violation, branch pruning and restricted spaces describe other techniques. Using a memory of where the search has been, in a method that otherwise keeps no history, is a modest addition that addresses the characteristic failure directly.

Answer: B

Once hill climbing is forced downhill out of a local optimum, the natural next move is straight back up, and forbidding the recently visited states blocks exactly that. Only a short window need be remembered, which keeps the memory constant. Storing everything would be expensive, worsening moves are precisely what is being permitted, and no region is fixed. A small bounded memory that addresses one specific failure is a better answer than an unbounded one that addresses it incidentally.

Answer: C

Forbidding a move that would reach the best configuration found so far is plainly counterproductive, so the tabu status is overridden in that case. It is a small exception that prevents the memory from doing harm. Target values, move ranking and list clearing are different mechanisms. A rule that suspends a general restriction when the restriction would obviously be wrong is a pattern worth recognising, since blanket prohibitions usually need one.

Answer: D

By keeping one complete state rather than a frontier, local search operates in spaces far too large for any systematic method, and pays for it by abandoning completeness and optimality. It applies only where the path is irrelevant. The objective and the neighbourhood matter more than the choice among the algorithms, which is the opposite of the last option. Knowing what each family can and cannot do, rather than preferring one, is what allows the right one to be selected.

Answer: A

If the sequence of actions is what the user needs, or a provably best answer is required, only a systematic method will do. Large spaces, expensive objectives and rugged landscapes all argue for local search instead. The decision follows from what the problem requires rather than from any property of the algorithms, which is why it should be made when the problem is formulated rather than when the code is written.

Answer: B

Overestimating may cause the algorithm to overlook the cheapest route, so the solution returned can be worse than optimal, but the search usually finishes sooner. Weighted A star exploits that deliberately with a bounded loss. Completeness is retained in a finite space, and the heuristic is certainly still used. Knowing exactly which guarantee a violated condition costs, rather than assuming everything fails, is what allows the violation to be adopted deliberately.

Answer: C

Inflating an admissible estimate focuses the search far more sharply, and a solution found in a second within five per cent of optimal often beats one found in a minute exactly. The weighted variant bounds the loss, which turns a gamble into a decision. Computation cost, availability and completeness are not the reasons. Choosing to give up a guarantee, with the loss quantified, is a legitimate engineering decision in a way that accidentally losing it is not.

Answer: D

Hill climbing, annealing and genetic algorithms are optimisation methods applied to discrete configurations, and gradient methods are their continuous counterparts. The vocabulary of landscapes, local optima and basins is shared throughout. Systematic search is a different tradition concerned with paths rather than points. Recognising that a literature developed elsewhere applies directly to a problem at hand is one of the cheapest sources of technique available.

Answer: A

Where hill climbing examines discrete neighbours, gradient ascent follows the derivative of a differentiable objective, but both move locally uphill and both stop at local optima. The failure modes and the remedies, including restarts and momentum, correspond closely. Breadth first, annealing and beam search have their own continuous analogues. Noticing that two methods in different literatures are the same idea in different settings makes the intuitions from one immediately available in the other.

Answer: B

Every local optimum has a surrounding region from which hill climbing leads to it, and the relative sizes of those basins determine how likely a random restart is to succeed. A global optimum with a tiny basin is very hard to find by restarts. Sign of the objective, proximity and evaluation history are different notions. Thinking about the sizes of the basins, rather than the number of optima, is what predicts whether restarts will work.