 Path cost

The path cost of a search node is the sum of step costs along the action history that reaches it:The same physical state can have different path costs when reached through different histories. Uniform-cost search orders nodes by accumulated path cost; A-star search adds a heuristic function estimating the remaining cost.

If every step cost is at least a fixed $\epsilon >0$, a history of depth $d$ satisfies $g(n)\ge \epsilon d$, so a cost bound gives an upper bound $d\le g(n)/\epsilon$ on search depth. Strict positivity without a uniform lower bound is insufficient: costs $2^{-1},2^{-2},\dots$ give arbitrarily deep prefixes of total path cost below one.