Informed and Heuristic Search Questions and Answers

Answer: D

Annealing accepts downhill moves, restarts begin again elsewhere, and stochastic beam search maintains diversity across a population. Strict hill climbing halts at the first state no neighbour improves on, which is the definition of being trapped. Sorting local search methods by how each escapes a local optimum is the most useful way to organise the family, since that failure is the one they all exist to address.

Answer: A

Both are true and the second is the reason. Because any node that could lead to a cheaper solution has an f value below the optimum and is therefore expanded first, no cheaper path can remain unexamined when the goal is selected. The argument depends on the heuristic never overestimating, which is precisely admissibility. A proof that identifies exactly which nodes must be examined also explains why a better heuristic prunes more, so one argument settles two questions.

Answer: B

The first is correct, since with cycle detection in a finite space every state is eventually reached. The second fails because greedy search never compares total path costs, so it may return an expensive route that merely pointed in the right direction. The pair separates two guarantees that are often assumed to travel together, and it shows that completeness is a much weaker property than optimality.

Answer: C

Straight line distance is admissible for distance costs, but if the step costs are travel times rather than distances the estimate may exceed the true remaining cost wherever fast roads exist, destroying both admissibility and consistency. Dividing by the maximum speed restores it. Cycles are handled by the explored set, and testing on generation affects only a constant factor. Checking that the heuristic and the cost function are measured in the same currency is the first thing to verify when optimality fails.

Answer: D

Since f is the sum of g and h, a distance added to a time is meaningless and the comparison between nodes becomes arbitrary, and admissibility cannot even be stated. Converting the heuristic into the cost currency, for instance by dividing a distance by the maximum speed, is the standard fix. Computation speed, computability and dimensionlessness are not the issue. A dimensional check on an expression is the cheapest error detection available and it catches this fault immediately.

Answer: A

Removing a restriction on the actions produces a problem whose solutions include all the original's, so its optimal cost cannot exceed the original's and is therefore an admissible heuristic. That is the systematic route to heuristics rather than an inspired guess. Smaller spaces, altered goals and approximate solutions are different notions. A construction that delivers a provable property, rather than a plausible one, is worth preferring even when a guess would perform similarly.

Answer: B

Because the relaxed problem allows everything the original does and more, its optimal solution is at least as cheap, so its cost is a lower bound on the true cost. That argument is completely general and requires nothing about the particular relaxation. State count and ease of solution are practical consequences rather than the reason, and no ordering of actions is involved. A proof that turns on a containment of solution sets is robust in a way that an argument about particular numbers is not.

Answer: C

Any relaxation gives an admissible heuristic, but one whose own optimal solution is as hard to compute as the original is useless, so the relaxation must be chosen so that its cost has a closed form or a cheap algorithm. Manhattan distance is a sum, which is why it is practical. Constraint counts, state spaces and exactness are not requirements. A construction that guarantees validity still leaves the engineering question of usefulness to be settled separately.

Answer: D

Permitting movement directly between any two points, off the road network entirely, gives a problem whose optimal solution is the Euclidean distance and which can never cost more than the real journey. That is why the heuristic is admissible for distance costs. Equal lengths, one way streets and tree structure describe other simplifications with different consequences. Identifying the relaxation behind a familiar heuristic both justifies it and shows where it would cease to apply.

Answer: A

If fast roads exist, the time to travel the straight line distance at ordinary speed can exceed the true fastest time, so the estimate overshoots and optimality is lost. Dividing by the maximum speed on the network restores admissibility. Road geometry, proximity and graph direction do not affect it. A heuristic's admissibility is a relationship between the estimate and the cost function, so changing the cost function requires the heuristic to be rechecked.