= Cost-bounded depth-first search
{title2=$g(v)\leq L$}
A <cost-bounded depth-first search> follows the usual <depth-first search> order but immediately rejects a generated <search node> whose accumulated <path cost> exceeds a threshold $L$. It can also return the least rejected <path cost>, providing the next threshold for <iterative lengthening search>. Positive <step costs> ensure that a rejected prefix cannot become a cheaper extension. With finite <branching factor> and every <step cost>ing at least $\epsilon>0$, every admitted <search node> has <search depth> at most $\lfloor L/\epsilon\rfloor$, so the pass terminates. Merely requiring every individual <step cost> to be positive does not exclude an infinite branch of finite total <path cost>.
Back to article page
