[Solved]: Iterative lengthening search: iterative version of Uniform Cost Search or DFS?

Problem Detail: 

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.

Asked By : today

Answered By : Varma

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40190