= Solution
\b[All three variants are <complete search algorithms> under the usual finite-<branching factor>, nonnegative-<heuristic function> assumptions.] Here $0\le h\le h^*$, with zero at goals; the supplied positive lower bound on step costs is also essential. The root is processed once before a parent-dependent priority is needed.<Informed search and exploration by Stuart Russell and Peter Norvig>[section 4.1, printed p. 100, footnote 4, finiteness and positive step costs]{ref} Completeness means finding a solution if one exists, not necessarily terminating when none exists.
Fix a finite solution path. Every <search node> on that path has a finite priority, so let $K$ bound all of its relevant priorities. For ordinary <A-star search> and the second variant, the priority is at least $g(n)$. Thus any <search node> with priority at most $K$ has depth at most $\lfloor K/\epsilon\rfloor$. In the third variant the priority is at least $g(n')$, so its depth is at most $\lfloor K/\epsilon\rfloor+1$. A finitely branching <search tree> has finitely many <search nodes> at these depths. Therefore finitely many earlier <search nodes> can delay each successive <search node> on the chosen solution path; eventually its goal is generated or selected, as appropriate.
Moving the <goal test> to generation cannot destroy that existence guarantee, although it can destroy optimality. Likewise the altered parent-dependent priorities remain bounded below by the accumulated cost to the <search node> or its parent, which is enough for this completeness argument. If “admissible” were interpreted to allow arbitrarily negative estimates, the lower-bound argument would need an additional hypothesis; the conventional nonnegative interpretation is being used explicitly. For the literal upper-bound-only interpretation, all three can fail completeness: attach an infinite unit-cost dead-end chain with $g(n_d)=d$ and $h(n_d)=-2d$ beside a finite goal branch beginning with a cost-$3$ edge and estimate zero. Its successive low priorities can starve the finite branch. Every negative chain estimate is still at most its infinite true remaining cost.
Back to article page
