Informed and Heuristic Search Questions and Answers

Answer: C

If the global optimum is reached from only a tiny fraction of starting points, the expected number of restarts becomes impractically large however cheap each one is. Methods that cross between basins, such as annealing or crossover, are then needed. Starting points are random by construction, climbing reaches some optimum every time, and the objective is fixed. Estimating the probability of success per attempt is what turns a hopeful strategy into a calculable one.

Answer: D

Ruggedness means the objective varies sharply with small changes of state, so local optima are numerous and each basin is small, which defeats simple hill climbing and often restarts as well. A flat landscape is the opposite extreme and is equally unhelpful. Evaluation noise and boundary optima are different difficulties. Characterising the landscape before choosing a method, even roughly by sampling, is far more informative than choosing by reputation.

Answer: A

Ruggedness is a property of the objective together with the move set, so connecting more states by each move, or encoding the problem so that related configurations are neighbours, smooths it. Restarts cope with ruggedness rather than reducing it. Evaluation accuracy and space size are separate matters. Recognising that the landscape is created jointly by the problem and by the designer's choices is what makes it something that can be improved rather than merely endured.

Answer: B

The representation and the moves together define the landscape, and a well shaped landscape makes almost any method work while a badly shaped one defeats all of them. Choosing among the algorithms matters far less. Iteration counts and starting points are parameters within a given formulation. Spending effort on the formulation rather than on the choice of algorithm is the consistent advice of practitioners and it follows directly from what determines the landscape.

Answer: C

The progression runs from search with no information, through search guided by a heuristic, to search that abandons paths entirely in exchange for constant memory. Each step trades a guarantee for a resource saving, and knowing which guarantee has been given up is what allows the right method to be chosen. Adversarial search and constraint satisfaction follow as specialisations. A sequence organised by what is surrendered at each stage is easier to hold than one organised by algorithm names.

Answer: D

If a heuristic is available, informed search should be used; if the path is not needed, local search should be considered; if optimality must be proved, the systematic methods are required. Prior experience and hardware inform the choice but do not decide it, and language features are irrelevant. Asking what information exists and what guarantee is needed, before considering any algorithm, is the same discipline the agent framework applies to design as a whole.

Answer: A

Adversarial games, constraint satisfaction, classical planning and much of automated reasoning are formulated as search over a space of states or of partial solutions, so the vocabulary and the analysis transfer directly. Not every system searches, other techniques are equally analysable, and provability is not confined to search. A framework that recurs across several apparently distinct subfields is worth mastering once rather than relearning in each disguise.

Answer: B

In a game the successor states are chosen alternately by two agents with opposed objectives, so the value of a state depends on assuming the opponent plays well, which gives minimax rather than simple minimisation. Uncertainty, constraints and deadlines are the additions that produce other specialisations. Identifying exactly what each specialisation adds to the basic framework makes the whole family comprehensible as variations on one theme.

Answer: C

A constraint problem uses a factored representation, so the algorithm can reason about which assignments are inconsistent and prune enormous regions without enumerating them. That is precisely the advantage a factored representation buys. Opponents, costs and path length belong to other variants. Noticing that the gain comes from the representation rather than from the algorithm connects this specialisation back to the discussion of atomic and factored states.

Answer: D

Because states are described by variables, an algorithm can detect that a partial assignment is already inconsistent and prune every completion of it at once, which an atomic representation cannot express. Heuristics such as most constrained variable are a further benefit of the same structure. The space is the same, and exact solutions are returned. The lesson that representation determines what can be exploited, established early in the subject, pays off concretely here.