2
$\begingroup$

Actually my question has two parts:

1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page 90), it is described as follow:

It would seem worthwhile to develop an iterative analog to uniform-cost search, inheriting the latter algorithm's optimality guarantees while avoiding its memory requirements. The idea is to use increasing path cost limits instead of increasing depth limits. This resulting algorithm is called iterative lengthening search... It turns out, unfortunately, that iterative lengthening incurs substantial overhead compared to uniform-cost search.

It seems that by using "avoiding its memory requirements", they mean that we use it in combination with DFS.

But, here in this link, which is the solution of final exam problems of artificial intelligence course at CMU, on page 4, it is described as follow:

Iterative lengthening search is an iterative version of uniform cost search. The main idea of this algorithm is that we use increasing limits on path cost.

  • We start searching as though we were performing uniform cost search.

and so on...

And also here in this link, question 4, part 1:

Iterative lengthening is uniform-cost search which is run multiple times with an increasing bound on the maximum cost from the start to reach before quitting. Iterative lengthening search doesn't have advantages in the same way iterative deepening depth-first search does.Iterative lengthening will simply search the same nodes each time adding more at the end since the first closest node, second closest node, etc. is invariant. All that iterative lengthening does is require the algorithm to restart repeatedly before finding a solution.

It seems that they mean we use it in combination with Uniform-Cost search.

Actually, I implemented it using uniform cost search, but to me there is no point in running uniform cost search over and over from beginning while increasing path cost limit (I mean using DFS seems more reasonable).

So which one is correct? (Is it the case that I misinterpreted them?)

2) Would you clarify why iterative lengthening search occurs substantial overhead?(Actually in case of using Uniform-cost search it is obvious, but I wanted to know this in case of using DFS.)

Clarification:

In order to resolve any ambiguity, here is pseudocodes for ILS in both cases(using DFS or UCS):

ILS using DFS:

0. Set limit to zero.
1. Perform DFS on initial node while discarding any generated node with path cost greater than limit.
2. If DFS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of DFS.
4. Go to line 1.

ILS using UCS:

0. Set limit to zero.
1. Perform UCS on initial node while discarding any generated node with path cost greater than limit.
2. If UCS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of UCS.
4. Go to line 1.

I was thinking about this for the past week. I think that ILS in combination with UCS has no advantages to UCS itself. While ILS in combination with DFS, at least is much better than UCS in terms of memory usage. And I think overhead occurs because in both of them, in each iteration only one more node(or a few if we have several nodes with same minimum path cost) is added to nodes that we explore in next iteration. However I'm not sure about these.

Improve this question
$\endgroup$
4
  • $\begingroup$ Just to be clear ... It seems to me that when you say "using DFS" you mean that the threshold is updated with the depth of the nodes that exceed the current threshold and that when you say "using Uniform cost search" you mean that their $g$-value is used instead ... am I right? I am willing to provide an answer but I need to be sure about the terminology you are using .... $\endgroup$
    – Carlos Linares López
    Mar 9, 2015 at 15:45
  • $\begingroup$ @CarlosLinaresLópez No. If threshold is updated with the depth of the nodes that exceed the current threshold, then I think it's called iterative deepening search. In both cases (using DFS or using UCS) we use g-value and we stop when there is no unexpanded nodes with path costs (g-value) smaller than threshold, which means cutoff has been occured. Then we increase the threshold and run DFS(or UCS) again from initial node. We repeat this procedure until we reach the goal node or our algorithm fails(in case of finite state space.) $\endgroup$
    – today
    Mar 9, 2015 at 19:22
  • $\begingroup$ thanks for your reply! Let me also dig into the terminology once more. UCS (Uniform Cost Search) is just a best-first search which sorts nodes in open with f(n)=g(n), right? (see Ariel Felner. "Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm", page 48). So your question would ultimately related to the following issue: while incrementing the depth should I use a depth-first search or a best-first search? Did I got the facts right this time? Cheers $\endgroup$
    – Carlos Linares López
    Mar 9, 2015 at 20:18
  • $\begingroup$ @CarlosLinaresLópez I added a clarification at the end of my question. Please take a look at that. Thanks. $\endgroup$
    – today
    Mar 12, 2015 at 10:34

1 Answer 1

Reset to default
1
$\begingroup$

Typically iterative deepening searches are used with DFS to improve the memory usage.

Consider BFS and IDDFS, both are optimal and complete but IDDFS in a tree search will use only $O(bm)$ space, where $b$ is thebranching factor and $m$ is the maximum height of the goal.

Now extending this to Uniform Cost Search using DFS, if we increase the max depth step by step, we are doing too many iterations over already visited nodes, whereas this was not true in case of IDDFS because of one step increase at a time (look for the overhead factor). So though using iterative search with DFS can save huge space ($O(bm)$), it gets worse with time complexity.

Secondly, there is no point in using Iterative Search with UCS as it is never a better upgrade over simple UCS in terms of space and time complexities.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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