Iterative Deepening in Artificial Intelligence

 Iterative Deepening

We have seen that problem with depth first search is that the search can go down an infinite branch and thus never return. This problem can be avoided by imposing a depth limit(d) which terminates the search at that depth. However, the next question is to decide a suitable depth limit (d), To overcome this problem there is another search method called iterative deepening search. Iterative deepening search is a general strategy often used in combination with depth first search that finds the best depth limit. This method enjoys the memory requirements of depth first search while guaranteeing that a goal node of minimal depth will be found (if a goal exists) .This search method simply tries all possible depth limits, first 0, then 1, then 2 etc. until a solution is found. In iterative deepening, successive depth first searches are conducted each with depth bounds increasing by 1 until a goal node is found. Hence, iterative deepening combines the benefits of depth first and breadth first search.

The below figure shows how iterative depending works on a simple tree. We note from the figure that the number of nodes expanded by iterative depending search is not much more than that would be using breadth first search.

 

The Depth first Iterative Deepening Algorithm (DFID) attempts to identify an propriate value of d in DDFS (root, d) by noting from DDFS that a FAILURE to find a solution implies that ‘d’ must be increased in order to encounter a SUCCESS. The appropriate amount of increment, however, remains unknown. DFID finds a suitable d by initially guessing it to be very small (equal to 1, in fact), repeatedly increments d on encountering FAILURE until a SUCCESS is found. The pseudo code is as follows,

Algorithm Depth First Iterative Deepening (DFID)

{
    begin 25
        d:=0;
        repeat
            d:= d+ 1;
            DDFS (root, d);
                until SUCCESS;
    end;
}

Iterative deepening search is analogous to breadth first search in that it explores a complete layer of new nodes at each iteration before going to the next layer. It is worthwhile to develop an iterative analog to uniform cost search, iterating the depth first’s guarantee to find a solution and avoiding its memory requirements. The idea is to use Increasing path cost limits instead of increasing depth limits. The resulting algorithm called iterative lengthening search, incurs substational overhead as compared to uniform cost search.

Note : In general, iterative deepening is preferred uninformed search method when there is a large search space and the depth of the solution is not Known.