Informed and Heuristic Search Questions and Answers

Answer: A

If one moderately good individual dominates early, its descendants fill the population and the search explores nothing further, arriving quickly at a mediocre answer. Diversity preservation, larger populations and lower selection pressure are the usual remedies. Timing, fitness behaviour and memory are different concerns. A search that stops exploring before it has found anything good is failing in the same way a hill climber trapped on a local maximum is, and the remedies are analogous.

Answer: B

An online search agent must act to discover what its actions do, since the state space is not known in advance, so it interleaves exploration with movement and cannot plan a route through territory it has never seen. Offline search computes a complete solution first. Network access and changing spaces are different notions, though a dynamic space raises related difficulties. Acting in order to learn what acting does is what makes exploration a search problem in its own right.

Answer: C

Without knowing what its actions do or where they lead, the agent has no model to plan over, and must build one by acting and observing. That is the reinforcement learning setting seen from the search direction. Time, goal knowledge and memory are secondary or absent. The distinction between an unknown environment and a merely large one determines whether exploration is a necessity or an inefficiency, and the two are frequently confused.

Answer: D

Comparing the distance actually travelled with what an omniscient agent would have walked gives a competitive ratio, and bounding it is the standard way of evaluating an online algorithm. In the worst case, with adversarially placed dead ends, the ratio can be unbounded. Running time, coverage and success rates are different measures. Judging an algorithm against what perfect knowledge would have achieved is the natural standard when the difficulty is ignorance rather than computation.

Answer: A

LRTA star acts greedily on its current estimates and raises the estimate of a state it leaves to reflect what it found there, so the heuristic improves with experience and the agent escapes from dead ends. Repeated searching, offline learning and radius limits describe other techniques. Updating an estimate towards the value of the best successor is exactly the update rule of value iteration, which connects online search directly to reinforcement learning.

Answer: B

Admissibility requires only that the estimate not exceed the truth:

\[ h = 4 \le 6 = h^{*} \]

so the heuristic is admissible at that state, though a tighter estimate would prune more. Exactness would make the search follow the optimal path directly and is never available in practice. A one sided condition is easy to satisfy and easy to check, which is why admissibility rather than accuracy is the property demanded.

Answer: C

The maximum of admissible heuristics is admissible and dominates both:

\[ h = \max(5, 8) = 8 \]

so 8 is the right choice. The sum of 13 might exceed the true cost and destroy the guarantee unless the two are additive over disjoint subproblems, and the average discards information. Taking the maximum costs only the extra evaluation and never loses, which makes it the default whenever several estimates are available.

Answer: D

The evaluation function is the sum of the two terms:

\[ f = 7 + 5 = 12 \]

giving 12, an estimate of the total cost of the best solution through that node. Nodes are expanded in increasing order of f, so this one waits behind everything cheaper. Keeping the accumulated and the estimated terms clearly separate is what makes the behaviour of A star predictable, since setting either to zero recovers a simpler algorithm.

Answer: A

With h equal to zero the evaluation function reduces to the path cost alone, which is exactly uniform cost search, and the algorithm remains complete and optimal but loses all guidance. Setting g to zero instead gives greedy search. Breadth first requires equal step costs, and termination is unaffected. Recovering simpler algorithms as special cases by zeroing a term is the clearest way to see what each term contributes.

Answer: B

A perfect heuristic makes f constant along an optimal path and larger everywhere else, so the search walks straight to the goal. It is admissible, since equality satisfies the inequality, and it represents the unattainable ideal against which real heuristics are measured. The other options invert the behaviour. Identifying the two extremes, no information and perfect information, places every real heuristic on a scale between them.