Path cost ($g(n)={\sum }_{e\in \mathrm{path}(n)}c(e)$)

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.

A step cost is the cost of one action or transition in a search problem. The accumulated path cost is the sum of the step costs along its action history. A uniform positive lower bound on step costs makes every bounded-cost action history have bounded search depth; positivity of each individual term alone does not establish such a bound.