Informed and Heuristic Search Questions and Answers

Answer: A

The heuristic estimates the cost still to come, which is exactly the information an uninformed search lacks. The cost already incurred is the path cost, usually written g, and the two are combined in A star's evaluation function. Node counts and probabilities are different quantities. Being precise about which direction a heuristic looks is essential, since confusing it with the path cost inverts the behaviour of every algorithm that uses it.

Answer: B

Greedy search ignores the cost already incurred and always heads for whatever looks closest to the goal, which is often very fast and often produces a poor path. Path cost ordering is uniform cost and the sum of the two is A star. It is neither complete in general nor optimal, which is the price of ignoring half the information available. An algorithm that discards a term and gains speed is worth understanding precisely because A star is what results from putting the term back.

Answer: C

By minimising only the estimated remaining cost, greedy search will happily follow an expensive route that appears to point at the goal, and no comparison of total costs is ever made. Adding the accumulated cost back gives A star and restores optimality with an admissible heuristic. Heuristic quality, expansion order and goal detection are separate matters. An algorithm optimising the wrong quantity cannot be repaired by improving how well it optimises it.

Answer: D

The evaluation function combines the exact cost from the start with an estimate of the cost to the goal, giving an estimate of the total cost of the best solution through that node. Minimising it directs the search along promising complete paths rather than merely promising directions. Setting h to zero recovers uniform cost and setting g to zero recovers greedy search, which places the whole family on one axis and makes the comparison immediate.

Answer: A

Admissibility means the estimate is optimistic, never exceeding the true remaining cost, and that alone guarantees A star returns an optimal solution in a tree search. Overestimation can cause the algorithm to overlook the best path. Returning zero at the goal is implied but is not the definition, and computational cost is a separate practical concern. A condition stated as a one sided inequality, and buying a strong guarantee, is worth memorising exactly.

Answer: B

Consistency, or monotonicity, requires that the estimate at a node is at most the step cost plus the estimate at the successor, which is a triangle inequality. It implies admissibility and additionally guarantees that f never decreases along a path, so graph search with an explored set remains optimal. Depth uniformity and formula uniformity are unrelated, and correctness at goals is implied. A local condition that yields a global guarantee is the most useful kind.

Answer: C

With an explored set, once a state has been expanded it is never reconsidered, so if a cheaper route to it is found later the optimal solution can be missed unless consistency guarantees the first expansion was already cheapest. Reopening closed nodes is the alternative repair. Computability, storage and expansion order are not the issue. A guarantee that holds for one variant of an algorithm and not another is exactly the kind of detail that determines correctness in practice.

Answer: D

A star must expand all nodes whose estimated total cost is below the optimal, since any of them might lead somewhere better, and may expand some with f equal to it. That is why a better heuristic, which raises f towards the truth for unpromising nodes, prunes so effectively. Depth and reachability are not the criterion, and expanding only the solution path would require a perfect heuristic. Knowing exactly which nodes an algorithm must examine is what allows two heuristics to be compared.

Answer: A

If h2 is never smaller than h1 and both are admissible, h2 dominates and A star using it expands no more nodes, since every node h1 prunes is pruned by h2 as well. Dominance is therefore the natural ordering on heuristic quality. Computation speed matters practically and may outweigh dominance, exact values at particular states are incidental, and both produce optimal paths. An ordering that guarantees no loss of performance is a strong basis for choosing between alternatives.

Answer: B

The maximum of two admissible heuristics is itself admissible, since neither exceeds the true cost, and it dominates both, so combining costs only the extra computation. The sum may overestimate and destroy admissibility unless the heuristics are additive over disjoint subproblems. Averaging and minimising both throw away information. Taking the maximum is a free improvement whenever several admissible estimates are available, which makes it the standard move.