= Solution
<Iterative deepening depth-first search> increases a bound on the number of actions, usually through $0,1,2,\ldots$. <Iterative lengthening search> instead bounds accumulated <path cost>; after an unsuccessful pass, its next bound is the least <path cost> among the rejected <search nodes>. Thus it can distinguish shallow expensive paths from deeper cheap ones.
Both repeatedly perform <depth-first search> and retain its small active-path storage, trading repeated work for avoiding a large <search frontier>. With unit <step costs> their bounds coincide. With unequal positive <step costs>, <iterative deepening depth-first search> finds a solution with the fewest actions, while <iterative lengthening search>, under the termination conditions discussed next, finds one of least total cost. Real-valued <path costs> can make <iterative lengthening search> perform many more passes than the depth-bounded method.
Back to article page
