= Solution
A lower bound on individual <step costs> does \b[not] bound the difference between consecutive <path cost> thresholds. Two different paths can have costs differing by an arbitrarily small amount, even though every edge costs at least $\epsilon$.
Let $C^*$ be the optimal solution cost. Every unsuccessful threshold is the <path cost> of some <search node> below $C^*$. Such a node has depth strictly less than $C^*/\epsilon$. For a uniform <branching factor> $b>1$, the number of passes is therefore bounded by
$$
1+\sum_{j=0}^{\lceil C^*/\epsilon\rceil-1}b^j=O\!\left(b^{\lceil C^*/\epsilon\rceil}\right).
$$
If a solution of depth $d$ exists, each of its edges costs at most one, so $C^*\leq d$ and an associated bound is \b[$O(b^{\lceil d/\epsilon\rceil})$ passes]. If $d$ denotes the optimal solution's depth, the same inequality applies. With no solution-cost or solution-depth bound, $b$ and $\epsilon$ alone give no finite uniform iteration bound.
The exponential behavior is possible. Put a depth-$d$ goal on a branch with unit costs and let a large competing subtree use costs just above $\epsilon$. Choose tiny distinct perturbations so that its many <search nodes> below cost $d$ have distinct <path costs>. The threshold can advance through those costs one at a time. Thus \b[a bound such as $\lceil d/\epsilon\rceil$ on the number of passes is unjustified]: it bounds admitted depth, not the number of distinct costs. For $b=1$ there is only one path, so the corresponding count is linear in the admitted depth rather than exponential.
Back to article page
