iterative lengthening search example

I am looking for an example of the "iterative lengthening search". I have searched and I was only able to find definitions like


iterative lengthening search an iterative analog to uniform cost
search. The idea is to use increasing limits on path cost. If a node
is generated whose path cost exceeds the current limit, it is
immediately discarded. For each new iteration, the limit is set to the
lowest path cost of any node discarded in the previous iteration

I'd be deeply grateful for an example, that enables me to understand.

Iterative deepening is not actually the same as iterative lengthening, but they're very similar concepts.

In an iterative deepening search (using depth-first), you use the depth (a measure of distance between nodes) as a limiting factor. So, if you're performing an iterative deepening depth-first search starting at point a, and you set a depth limit of 2, you're asking the algorithm to perform a depth-first search from point a, but to not continue the depth-first search after you get two points away from your starting point a.

e.g.

a             In our example, the algorithm would never
                      / \            visit point e. It is more than 2 points
                     b   c           away from a (its depth is greater than 2)
                   /
                  d
                 /
                e

The algorithm will therefore explore all paths from a that are equal to a length of 2 (do not go deeper than depth 2).

In an iterative deepening search, you slowly increase (iterate) the depth at which you limit the search. It tries all paths of length 1 and then all paths of length 2 and so on. This means if there's a path of length 1 to a goal that you're trying to find, this algorithm would find it before trying any paths of length 2, 3, 4, et cetera.

Similarly, an iterative lengthening search uses the cost (or "length") of a path to limit the search rather than the depth. This is useful in situations where connections are weighted. The algorithm would explore all possiblities with a cost of 1 or less, then all possibilities of a cost of 2 or less, and so on. For a real-life example, the cheapest (cost) way to get somewhere is not always the same as the simplest (depth) way to get there. You might have to catch seven buses and a helicopter, but it's cheaper than renting out the Concorde for a single flight. You could consider an iterative deepening search to be a specific case of an iterative lengthening search where you define the "length" that you're iterating as the depth.

StackExchange Computer Science Q#10504, answer score: 4