iterative_deepening

Posted on | In

Iterative Deepening DFS

The iterative deepening depth-first search is a state space search algorithm, which combines the goodness of BFS and DFS.

  • Time complexity: O(b^d), where b is the branching factor and d is the depth of the goal.
  • Space complexity: O(d), where d is the depth of the goal.

Pseudocode of IDDFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function IDDFS(root)
   for depth from 0 to ∞
       found, remaining ← DLS(root, depth)
       if found ≠ null
           return found
       else if not remaining
           return null

function DLS(node, depth)
   if depth = 0
       if node is a goal
           return (node, true)
       else
           return (null, true)    (Not found, but may have children)

   else if depth > 0
       any_remaining ← false
       foreach child of node
           found, remaining ← DLS(child, depth−1)
           if found ≠ null
               return (found, true)   
           if remaining
               any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
       return (null, any_remaining)

Comparison of DFS, BFS and IDDFS (based on time complexity and space complexity):

The following code block shows the main function of IDDFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# recursive function of IDDFS, with parameter depth
def IDDFS(node, depth, value, deadline, processors):
    # to the leaf of the tree
    if depth < 0:
        return None

    # store the sum of length of all tasks that a processor needs to work on
    current_v = 0
    total_time = dict()
    for t in node.tasks:
        if t.processor != 0:
            try:
                total_time[t.processor] += t.length
            except:
                total_time[t.processor] = t.length
            current_v += t.length

    # check current node
    if current_v >= value:
        found = True
        for p in total_time:
            if total_time[p] / processors[p] > deadline:
                found = False
        if found :
            return node

    # check all the children of current node
    for child in node.children:
        found = IDDFS(child, depth - 1, value, deadline, processors)
        if found != None:
            return found
    return None