Editing Iterative deepening depth-first search

{{Short description|Search strategy}}
{{more citations needed|date=January 2017}}
{{Infobox Algorithm
|class=[[Search algorithm]]
|image=
|caption =
|data=[[Tree (data structure)|Tree]], [[Graph (data structure)|Graph]]
|time=<math>O(b^d)</math>, where <math>b</math> is the branching factor and <math>d</math> is the depth of the shallowest solution
|space=<math>O(d)</math><ref name="re1985"/>
|optimal=yes (for unweighted graphs)
|complete=yes
}}

In [[computer science]], '''iterative deepening search''' or more specifically '''iterative deepening depth-first search'''<ref name="re1985">{{cite journal|last=Korf|first=Richard|author-link=Richard E. Korf|title=Depth-first Iterative-Deepening: An Optimal Admissible Tree Search|journal=Artificial Intelligence|year=1985|volume=27|pages=97–109|doi=10.1016/0004-3702(85)90084-0|s2cid=10956233 }}</ref> (IDS or IDDFS) is a [[state space search|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 optimal, meaning that it finds the shallowest goal.<ref name=":0" /> Since it visits all the [[node (computer science)|node]]s in the [[search tree]] down to depth <math>d</math> before visiting any nodes at depth <math>d + 1</math>, the cumulative order in which nodes are first visited is effectively the same as in [[breadth-first search]]. However, IDDFS uses much less memory.<ref name="re1985"/>

== Algorithm for directed graphs==
The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS) for [[directed graph]]s. This implementation of IDDFS does not account for already-visited nodes.

 '''function''' IDDFS(root) '''is'''
     '''for''' depth '''from''' 0 '''to''' ∞ '''do'''
         found, remaining ← DLS(root, depth)
         '''if''' found ≠ '''null''' '''then'''
             '''return''' found
         '''else if''' not remaining '''then'''
             '''return''' '''null'''
 
 '''function''' DLS(node, depth) '''is'''
     '''if''' depth = 0 '''then'''
         '''if''' node is a goal '''then'''
             '''return''' (node, '''true''')
         '''else'''
             '''return''' ('''null''', '''true''')    ''(Not found, but may have children)''
 
     '''else if''' depth > 0 '''then'''
         any_remaining ← '''false'''
         '''foreach''' child '''of''' node '''do'''
             found, remaining ← DLS(child, depth−1)
             '''if''' found ≠ null '''then'''
                 '''return''' (found, '''true''')   
             '''if''' remaining '''then'''
                 any_remaining ← true    ''(At least one node found at depth, let IDDFS deepen)''
         '''return''' ('''null''', any_remaining)

If the goal node is found by '''DLS''', '''IDDFS''' will return it without looking deeper. Otherwise, if at least one node exists at that level of depth, the ''remaining'' flag will let '''IDDFS''' continue.

[[Tuple|2-tuples]] are useful as return value to signal '''IDDFS''' to continue deepening or stop, in case tree depth and goal membership are unknown ''a priori''. Another solution could use [[sentinel value]]s instead to represent ''not found'' or ''remaining level'' results.

== Properties ==
IDDFS achieves breadth-first search's completeness (when the [[branching factor]] is finite) using depth-first search's space-efficiency. If a solution exists, it will find a solution path with the fewest arcs.<ref name=":0">{{cite web |author1=David Poole |author2=Alan Mackworth |title=3.5.3 Iterative Deepening‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition |url=https://artint.info/2e/html/ArtInt2e.Ch3.S5.SS3.html |website=artint.info |access-date=29 November 2018}}</ref>

Iterative deepening visits states multiple times, and it may seem wasteful.  However, if IDDFS explores a search tree to depth <math>d</math>, most of the total effort is in exploring the states at depth <math>d</math>.  Relative to the number of states at depth <math>d</math>, the cost of repeatedly visiting the states above this depth is always small.<ref name="rn3">{{Russell Norvig 2003}}</ref>

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.<ref name="rn3"/>

A second advantage is the responsiveness of the algorithm. Because early iterations use small values for <math>d</math>, they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as <math>d</math> 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 [[corecursive|''co''recursively]] 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 ==

=== Time complexity ===

The [[time complexity]] of IDDFS in a (well-balanced) tree works out to be the same as breadth-first search, i.e. <math>O(b^{d})</math>,<ref name="re1985"/>{{rp|5}} where <math>b</math> is the branching factor and <math>d</math> is the depth of the goal.

==== Proof ====

In an iterative deepening search, the nodes at depth <math>d</math> are expanded once, those at depth <math>d - 1</math> are expanded twice, and so on up to the root of the search tree, which is
expanded <math>d+1</math> times.<ref name="re1985"/>{{rp|5}} So the total number of expansions in an iterative deepening search is

:<math>b^{d} + 2b^{d-1} + 3b^{d-2} + \cdots + (d-1)b^{2} + db +  (d + 1) = \sum_{i=0}^d (d+1-i)b^i</math>

where <math>b^{d}</math> is the number of expansions at depth <math>d</math>, <math>2b^{d - 1}</math> is the number of expansions at depth <math>d - 1</math>, and so on. Factoring out <math>b^{d}</math> gives

:<math>b^{d}(1 + 2b^{-1} + 3b^{-2} + \cdots + (d-1)b^{2 - d} + db^{1 - d} + (d + 1)b^{-d}) </math>

Now let <math>x = \frac{1}{b} = b^{-1}</math>. Then we have

:<math>b^{d}(1 + 2x + 3x^2 + \cdots + (d-1)x^{d - 2} + dx^{d - 1} + (d + 1)x^d)</math>

This is less than the infinite series

:<math>b^{d}(1 + 2x + 3x^2 + 4x^3 + \cdots ) = b^{d} \left( \sum^{\infty}_{n=1}n x^{n-1} \right)</math>

which [[Geometric series#Geometric power series|converges]] to

:<math>b^d (1 - x)^{-2} = b^d  \frac{1}{(1-x)^2}</math>, for <math>abs(x) < 1</math>

That is, we have

<math>b^{d}(1 + 2x + 3x^2 + \cdots + (d-1)x^{d - 2} + dx^{d - 1} + (d + 1)x^d) \leq b^d (1 - x)^{-2}</math>, for <math>abs(x) < 1</math>

Since <math>(1 - x)^{-2}</math> or <math>\left(1 - \frac{1}{b} \right)^{-2}</math> is a constant independent of <math>d</math> (the depth), if <math>b > 1</math> (i.e., if the branching factor is greater than 1), the running time of the depth-first iterative deepening search is <math>O(b^d)</math>.

==== Example ====

For <math>b=10</math> and <math>d=5</math> the number is

: <math>\sum_{i=0}^{5} (5 + 1 - i)10^i = 6 + 50 + 400 + 3000 + 20000 + 100000 = 123456</math>

All together, an iterative deepening search from depth <math>1</math> all the way down to depth <math>d</math> expands only about <math>11 \%</math> more nodes than a single breadth-first or depth-limited search to depth <math>d</math>, when <math>b = 10</math>.<ref>{{cite book|last1=Russell|last2=Norvig|title=Artificial Intelligence: A Modern Approach|date=1994}}</ref>

The higher the branching factor, the lower the overhead of repeatedly expanded states,<ref name="re1985"/>{{rp|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 <math>O(b^d)</math>.

=== Space complexity ===

The [[space complexity]] of IDDFS is <math>O(d)</math>,<ref name="re1985"/>{{rp|5}} where <math>d</math> is the depth of the goal.

==== Proof ====

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 <math>d</math>, and hence the maximum amount of space is <math>O(d)</math>.

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.<ref name="rn3"/>

==Example==
For the following graph:

[[Image:graph.traversal.example.svg|200px]]

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
(Iterative deepening has now seen C, when a conventional depth-first search did not.)
*2: A, B, D, F, C, G, E, F
(It still sees C, but that it came later. Also 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 ==

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.<ref name="rn3">{{Russell Norvig 2003}}</ref>

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

=== Bidirectional IDDFS ===
IDDFS has a bidirectional counterpart,<ref name="re1985"/>{{rp|6}} which alternates two searches: one starting from the source node and moving along the directed arcs, and another one starting from the target node and proceeding along the directed arcs in opposite direction (from the arc's head node to the arc's tail node). The search process first checks that the source node and the target node are same, and if so, returns the trivial path consisting of a single source/target node. Otherwise, the forward search process expands the child nodes of the source node (set <math>A</math>), the backward search process expands the parent nodes of the target node (set <math>B</math>), and it is checked whether <math>A</math> and <math>B</math> intersect. If so, a shortest path is found. Otherwise, the search depth is incremented and the same computation takes place.

One limitation of the algorithm is that the shortest path consisting of an odd number of arcs will not be detected. Suppose we have a shortest path <math>\langle s, u, v, t \rangle.</math> When the depth will reach two hops along the arcs, the forward search will proceed from <math>u</math> to <math>v</math>, and the backward search will proceed from <math>v</math> to <math>u</math>. Pictorially, the search frontiers will go through each other, and instead a suboptimal path consisting of an even number of arcs will be returned. This is illustrated in the below diagrams:

[[File:Bidirectional iterative deepening depth-first search search frontier pass through each other.png|thumb|Bidirectional IDDFS|400px]]

What comes to space complexity, the algorithm colors the deepest nodes in the forward search process in order to detect existence of the middle node where the two search processes meet.

Additional difficulty of applying bidirectional IDDFS is that if the source and the target nodes are in different strongly connected components, say, <math>s \in S, t \in T</math>, if there is no arc leaving <math>S</math> and entering <math>T</math>, the search will never terminate.

==== Time and space complexities ====

The running time of bidirectional IDDFS is given by

{{center|
: <math>2\sum_{k = 0}^{n / 2} b^k</math>
}}

and the space complexity is given by

{{center|
: <math>b^{n/2},</math>
}}

where <math>n</math> is the number of nodes in the shortest <math>s,t</math>-path. Since the running time complexity of iterative deepening depth-first search is <math>\sum_{k=0}^n b^k</math>, the speedup is roughly

{{center|
: <math>\frac{\sum_{k=0}^n b^k}{2\sum_{k=0}^{n/2} b^k} =\frac{\frac{1 - b^{n+1}}{1-b}}{2\frac{1 - b^{n/2 + 1}}{1-b}} = \frac{1-b^{n+1}}{2(1 - b^{n/2 + 1})} = \frac{b^{n+1} - 1}{2(b^{n/2+1} - 1)} \approx \frac{b^{n+1}}{2b^{n/2+1}} = \Theta(b^{n/2}).</math>
}}

==== Pseudocode ====

 '''function''' Build-Path(s, &mu;, B) '''is'''
     &pi; &larr; Find-Shortest-Path(s, &mu;) ''(Recursively compute the path to the relay node)''
     remove the last node from &pi;
     '''return''' &pi; <math>\circ</math> B ''(Append the backward search stack)''

 '''function''' Depth-Limited-Search-Forward(u, &Delta;, F) '''is'''
     '''if''' &Delta; = 0 '''then'''
         F &larr; F <math>\cup</math> {u} ''(Mark the node)''
         '''return'''
     '''foreach''' child '''of''' u '''do'''
         Depth-Limited-Search-Forward(child, &Delta; − 1, F)

 '''function''' Depth-Limited-Search-Backward(u, &Delta;, B, F) '''is'''
     prepend u to B
     '''if''' &Delta; = 0 '''then'''
         '''if''' u '''in''' F  '''then'''
             '''return''' u ''(Reached the marked node, use it as a relay node)''
         remove the head node of B
         '''return null'''
     '''foreach''' parent '''of''' u '''do'''
         &mu; &larr; Depth-Limited-Search-Backward(parent, &Delta; − 1, B, F)
         '''if''' &mu; <math>\neq</math> '''null''' '''then'''
             '''return''' &mu;
     remove the head node of B
     '''return null'''

 '''function''' Find-Shortest-Path(s, t) '''is'''
    '''if''' s = t '''then'''
        '''return''' &lt;s&gt;
    F, B, &Delta; &larr; &empty;, &empty;, 0
    '''forever do'''
        Depth-Limited-Search-Forward(s, &Delta;, F)
        '''foreach''' &delta; = &Delta;, &Delta; + 1 '''do'''
            &mu; &larr; Depth-Limited-Search-Backward(t, &delta;, B, F)
            '''if''' &mu; <math>\neq</math> '''null then'''
                '''return''' Build-Path(s, &mu;, B) ''(Found a relay node)''
        F, &Delta; &larr; &empty;, &Delta; + 1

== References ==
{{Reflist}}

{{Graph traversal algorithms}}

{{DEFAULTSORT:Iterative Deepening Depth-First Search}}
[[Category:Graph algorithms]]
[[Category:Search algorithms]]