iterative_deepening

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