SearchWiki
AIAWiki.RecentChanges
Edit Page
Page Revisions

Description

Iterative Deepening Search has many of the advantages of Depth First Search and many of the advantages of Breadth First Search. It uses the same amount of memory as a Depth First Search on the same search space, and is complete, and optimal (under appropriate conditions).

The search begins by doing a Depth Limited Search with a limit of Λ and if a goal is not found incrementing this limit (the increment may be greater than one) and trying again until a goal is found.

This may sound like a horrible idea for a search, afterall we are repeatedly searching the same space over and over again. States that are investigated early will be investigated multiple times before a goal is found. If we do the math we find that this concern, while valid, does not have a huge impact. As an example let us consider a case where the branching factor is 10. We begin our search with a limit of 1, and an increment of 1, but don't find a goal state until we reach a depth of 5. So lets calculate how many nodes we visit on each iteration.

   Iteration                                               Total
       1        10                                            10 
       2        10 + 100                                     110 
       3        10 + 100 + 1000                            1,110
       4        10 + 100 + 1000 + 10,000                  11,110
       5        10 + 100 + 1000 + 10,000 + 100,000       111,110

On average we will visit half the states in the fifth iteration (a Depth Limited Search with a limit of 5) before we find our goal state. If we knew that our goal state existed at a depth of five from our start state we could find our goal by visting only 55,555 states. In the iterations 1-4 we visit a total of 12,340 states including multiple visits to the same state. So our Iterative Deepening Search only visits 22% more states than our Depth Limited Search. This might be a reasonable tradeoff to gain optimality in the search. We probably don't know how deep the goal is before we begin the search, so we probably couldn't pick an appropriate depth limit beforehand. Depth Limited Search allows us to find our solution efficiently without knowing the depth limit.

Since we may also gain optimality (under appropriate conditions) it might be more appropriate to compare the efficiency of this search to Breadth First Search. If we were going to peform a Breadth First Search we would have to visit:

   10 + 100 + 1000 + 10,000 + 50,000 = 61,110

states, on average. Our Iterative Deepening Search visits a total of

   12,340 + 55,555 = 67,895

states, on average. So we only visit 11% more nodes than we would using Breadth First Search. For this sacrifice we get much better performance in terms of Space Complexity. In fact, many searches that would be impossible with Breadth First Search due to Space Complexity are easily done with Iterative Deepening Search.

As the Branching Factor or increment increase, these percentages decrease. Iterative Deepening Search becomes more and more efficient when compared to Depth Limited Search or Breadth First Search.

We can apply this extension to other searches where we would like to gain Search Optimality, or better Space Complexity performance. A Star Search becomes Iterative Deepening A Star Search?. Uniform Cost Search becomes Iterative Deepening Uniform Cost Search?, more commonly known as Iterative Lengthening Search?.

This work is licensed under a Creative Commons License.

Edit Page - Upload Attachment - Page Revisions - WikiHelp - SearchWiki - RecentChanges - Printable Version
Page last modified on May 12, 2004, at 09:53 AM