Informed and Heuristic Search Questions and Answers

Answer: A

Both use linear memory and therefore forget almost everything, so a node may be regenerated many times over. Algorithms that use whatever memory is available, such as the bounded memory variants, sit between the extremes. Both are optimal with an admissible heuristic, both use far less memory than A star, and cycles are handled by ordinary means. The tension between remembering to avoid rework and forgetting to save memory is the organising theme of the whole family.

Answer: B

Simplified memory bounded A star discards the frontier node with the worst f but records that value in its parent, so the subtree can be regenerated if it later becomes the best option. It uses all available memory and degrades gracefully as it becomes scarce. Restarting, failing and switching strategy are cruder responses. An algorithm that adapts to whatever memory exists, rather than assuming a fixed profile, is what a general purpose implementation needs.

Answer: C

Beam search bounds the frontier to a fixed width, discarding everything else, which makes memory constant and the search fast but sacrifices both completeness and optimality. It is widely used in speech recognition and machine translation where an approximate answer quickly is worth more than a guaranteed one slowly. The other options describe no standard algorithm. Trading guarantees for a fixed resource budget is often the right decision when the budget is hard and the guarantee is soft.

Answer: D

Pruning to a fixed width may discard the only node leading to the goal, and once discarded it is never reconsidered, so the search can fail on a problem that has a solution. Widening the beam trades memory for reliability, and stochastic variants keep some diversity. Memory falls rather than rises, admissibility is a property of the heuristic, and termination is unaffected. An approximation whose failure mode is silent deserves particular care in deployment.

Answer: A

Local search moves from one complete state to a neighbour, keeping no path and no frontier, which suits problems where the goal state itself is the answer and the route to it is irrelevant. Timetabling and layout problems are typical. Memory is constant regardless of the space's size. Heuristics, graphs and direction are shared with other methods. Discarding the path when the path is not wanted is what buys the enormous memory saving.

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.