Iterative deepening depth-first search

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Iterative deepening depth-first search
Class Search algorithm
Data structure Tree, Graph
Worst-case performance , where is the branching factor and is the maximum depth
Worst-case space complexity [1]

In computer science, iterative deepening search or more specifically iterative deepening depth-first search[2] (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

Algorithm[edit]

The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS).

function IDDFS(root)
    for depth from 0 to ∞
        found ← DLS(root, depth)
        if found ≠ null
            return found

function DLS(node, depth)
    if depth = 0 and node is a goal
        return node
    if depth > 0
        foreach child of node
            found ← DLS(child, depth−1)
            if found ≠ null
                return found
    return null

Properties[edit]

IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node.[citation needed]

Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.[3]

The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha-beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha-beta pruning is most efficient if it searches the best moves first.[3]

A second advantage is the responsiveness of the algorithm. Because early iterations use small values for , they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as increases. When used in an interactive setting, such as in a chess-playing program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This can be phrased as each depth of the search corecursively producing a better approximation of the solution, though the work done at each step is recursive. This is not possible with a traditional depth-first search, which does not produce intermediate results.

Asymptotic analysis[edit]

Time complexity[edit]

The time complexity of IDDFS in a (well-balanced) tree works out to be the same as depth-first search, i.e. ,[4] where is the branching factor and is the depth of the goal.

Proof[edit]

In an iterative deepening search, the nodes at depth are expanded once, those at depth are expanded twice, and so on up to the root of the search tree, which is expanded times.[5] So the total number of expansions in an iterative deepening search is

where is the number of times the nodes at depth are visited, is the number of times the nodes at depth are visited, and so on. Factoring out gives

Now let . Then we have

This is less than the infinite series

which converges to[citation needed]

, for

That is, we have

, for

Since or is a constant independent of (the depth), if (i.e., if the branching factor is greater than 1), the running time of the depth-first iterative deepening search is .

Example[edit]

For and the number is

The higher the branching factor, the lower the overhead of repeatedly expanded states,[6] but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadth-first search. This means that the time complexity of iterative deepening is still .

Space complexity[edit]

The space complexity of IDDFS is ,[7] where is the depth of the goal.

Proof[edit]

Since IDDFS, at any point, is engaged in a depth-first search, it need only store a stack of nodes which represents the branch of the tree it is expanding. Since it finds a solution of optimal length, the maximum depth of this stack is , and hence the maximum amount of space is .

In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.[3]

Example[edit]

For the following graph:

Graph.traversal.example.svg

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.

Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.

Iterative deepening prevents this loop and will reach the following nodes on the following depths, assuming it proceeds left-to-right as above:

  • 0: A
  • 1: A, B, C, E

(Note that iterative deepening has now seen C, when a conventional depth-first search did not.)

  • 2: A, B, D, F, C, G, E, F

(Note that it still sees C, but that it came later. Also note that it sees E via a different path, and loops back to F twice.)

  • 3: A, B, D, F, E, C, G, E, F, B

For this graph, as more depth is added, the two cycles "ABFE" and "AEFB" will simply get longer before the algorithm gives up and tries another branch.

Related algorithms[edit]

Similar to iterative deepening is a search strategy called iterative lengthening search that works with increasing path-cost limits instead of depth-limits. It expands nodes in the order of increasing path cost; therefore the first goal it encounters is the one with the cheapest path cost. But iterative lengthening incurs substantial overhead that makes it less useful than iterative deepening.[3]

Iterative deepening A* is a best-first search that performs iterative deepening based on "f"-values similar to the ones computed in the A* algorithm.

Notes[edit]

  1. ^ KORF, Richard E. (1985). "Depth-first iterative deepening" (PDF): 5. 
  2. ^ Korf, Richard (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search". Artificial Intelligence. 27: 97–109. doi:10.1016/0004-3702(85)90084-0. 
  3. ^ a b c d Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2 
  4. ^ KORF, Richard E. (1985). "Depth-first iterative deepening" (PDF): 5. 
  5. ^ KORF, Richard E. (1985). "Depth-first iterative deepening" (PDF): 5. 
  6. ^ KORF, Richard E. (1985). "Depth-first iterative deepening" (PDF): 6. 
  7. ^ KORF, Richard E. (1985). "Depth-first iterative deepening" (PDF): 5.