= Solution
\b[With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true.] The third answer needs that positivity convention: it is false in general if zero-cost <edges> and unrestricted ties are admitted. Take the <goal test> on selection from the <search frontier>, and assume a finite reachable problem with a reachable <goal state>; finite <branching factor> and a positive lower bound on step costs give the corresponding <tree search> guarantees on an infinite problem. These assumptions make the usual <A-star search> guarantees precise.<Informed search and exploration by Stuart Russell and Peter Norvig>[§4.1, printed pp. 94–100: best-first priorities, consistency and optimality conditions]{ref}
For the first assertion, use a <directed graph> with transitions $s\to t$ of cost $10$, $s\to x$ of cost $1$ and $x\to t$ of cost $1$, where $t$ is the only <goal state>. The <perfect heuristic> is $h^*(s)=2$, $h^*(x)=1$, $h^*(t)=0$. <Greedy best-first search> selects the direct goal of cost $10$ because its priority is zero. The least <path cost> is $2$. Knowing the exact remaining distance does not account for an expensive transition already taken.
The same <counterexample> settles the second assertion. <Greedy best-first search> selects $s,t$, while <A-star search> selects $s,x,t$: after expanding $s$, the <A-star search> priorities are $2$ for $x$ and $10$ for the direct copy of $t$. Thus even the expanded state <sets> differ.
For the third assertion, let the current nonterminal <search node> have finite remaining distance $h^*(s)$. The first transition of a least-cost continuation has some successor $s'$ with
$$
h^*(s)=c(s,s')+h^*(s')>h^*(s').
$$
Every older entry in the <search frontier> has estimate at least $h^*(s)$, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current <search node>, so the argument repeats. Consequently the selected <search nodes> form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This <greedy perfect-heuristic descent> does not imply least <path cost>, as the first <counterexample> demonstrates.
The zero-cost qualification is substantive. Give $s$ two successors $a,b$ of cost $1$, add $a\to x$ of cost $0$, and add $x\to t$ and $b\to t$ of cost $1$. The <perfect heuristic> has values $2$ at $s$, $1$ at $a,b,x$ and $0$ at $t$. Alphabetical priority ties let <greedy best-first search> select $s,a,b,t$, which is not one <graph path>. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.
For the fourth assertion, a least remaining distance satisfies
$$
h^*(s)\le c(s,s')+h^*(s')
$$
on every <edge>, by taking that <edge> and then a least-cost continuation. Thus $h^*$ is a <consistent heuristic>. The usual <A-star search> <graph search> finalizes each expanded state's least <path cost> and returns a least-cost goal.
For the fifth assertion, write $C^*=h^*(s_0)$. Before a goal is selected, an unexpanded prefix of an optimal <graph path> remains on the <search frontier>, with $f=g+h^*=C^*$. <A-star search> therefore selects only <search nodes> with $f\le C^*$. Since $g\ge0$,
$$
\boxed{h^*(n)\le g(n)+h^*(n)\le C^*=h^*(s_0).}
$$
This compares remaining cost, not <search depth> or accumulated <path cost>. The statement can fail with negative costs; those are outside the convention used here.
Back to article page
