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.)
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.