2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the context? What kind of data structures are you searching? $\endgroup$ – Raphael Feb 3 '14 at 9:44
2
$\begingroup$

Perhaps the simplest example would be to consider DFS as a search algorithm on graphs, but to use iterative lengthening as follows: the cost of each edge is 1, and the cost of a path is the sum over the edges. So we essentially use DFS while limiting the search depth.

If you start from the limit 1 and increase, then you essentially get (sort of) BFS. Indeed, while you do not open nodes layer-by-layer, in iteration $d$ of the DFS you will open all the edges up to distance $d$.

Do you consider this an example, or are you looking for a more concrete/more involved example?

EDIT: Here is a lecture of iterative depth DFS, which includes an example.

$\endgroup$
  • $\begingroup$ Many thanks for the reply .... If you could point me to an illustrated example, step by step .... as I am not very clear on this $\endgroup$ – Alvaro Soto Mar 15 '13 at 13:20
  • $\begingroup$ I edited the post with a link to an example. $\endgroup$ – Shaull Mar 15 '13 at 14:12
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that, in interative lengthening, you wouldn't just increase your maximum weight by one at each iteration. You wouldn't use any increment that wasn't enough to get you to at least one more node in the iteration of the search. $\endgroup$ – David Richerby Feb 3 '14 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.