= Solution
\b[The first assertion is false.] Give the root a first child that is a <goal state> of cost ten and another child leading to many cheaper non-goal <search nodes>. <Depth-first search> can take the first child and stop immediately. <A-star search> with the <admissible heuristic> $h=0$ behaves as <uniform-cost search> and expands the cheaper non-goal <search nodes> before selecting that goal. Thus an <admissible heuristic> does not make <A-star search> expand fewer nodes than every possible <depth-first search> ordering. The latter need not return an optimal solution.
\b[The second assertion is true under the usual finite-<branching factor> assumption.] <Breadth-first search> orders by <search depth>, not <path cost>. Every finite depth contains finitely many <search nodes>, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite <branching factor> would invalidate the argument irrespective of <step costs>.
\b[The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed.] If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost <cycle in a graph> that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.
Back to article page
