Iterative Deepening
Jacky Baltes
National Taiwan Normal University
Taipei, Taiwan
jacky.baltes@ntnu.edu.tw
Search Methods and Iterative Deepening
- Depth First Search
- Advantage: Amount of memory grows linearly with the depth of the search
- Disadvantage: May fall into a deep subtree
- Disadvantage: Usually does not find the shallowest/optimal solution
- Breadth First Search
- Advantage: Finds shallowest/optimal solution
- Disadvantage: Requires an exponential amount of memory
- Hill Climbing Search Search
- Advantage: Local search proceeds quickly
- Disadvantage: May get stuck in local minimum/maximum. Random restart to avoid
- Disadvantage: Not guaranteed to find shallowest/optimal solution
Iterative Deepening
- Combines depth first and breadth first search
- Advantage: Finds optimal/shallowest solution
- Advantage: Amount of memory grows linearly with the depth of the search
- Advantage: Does not fall into a deep subtree
- Disadvantage: Increase in runtime. Iterative deepening is slower
Iterative Deepening
- Impose a depth limit for depth first search
- Obvious problem is that we cut out parts of the search space
- If the solution is in the part that we cut out, then the algorithm will fail to find it
- If we do not find a solution, then we increase the depth limit
- Trading off runtime for memory efficiency
Runtime Overhead of Iterative Deepening
- How much slower will our search be?
- Simplest case is a binary tree
- Branching factor \(b=2\), depth of the search \( d \)
- Number of leave nodes \( n_l \) at level \( l \), that is \[ n_l = 2^{l} \]
- Number of nodes searched in breadth first search \( n_e \) is solution is at level \( l \) is \[ \sum_{i=0}^{l} 2^{i} = 2^{l+1}-1 \]
- Number of nodes expanded in Iterative Deepening \[ \mbox{Limit 1}: (2^1 - 1) \\ \mbox{Limit 2}: (2^2 - 1) \\ \mbox{Limit 3}: (2^3 - 1) \\ ... \]
- Each level will be expanded l - i times \[ n_e = \sum_{i=0}^{l} (l-i)*2^{i} \approx 2^{l+1} \]
- Compare that to the cost of breadth first search \[ 2^{l+1} - 1 \]
- Even with a small branching factor of 2, 50% of the nodes are leaf nodes.
- So even if we expand the nodes in the upper layers of the tree often (worst case it would be l times for the root node), it will only add a small portion to the runtime.
Runtime Overhead of Iterative Deepening
- How much slower will our search be?
- Simplest case is a binary tree
- Branching factor \(b=2\), depth of the search \( d \)
- Number of leave nodes \( n_l \) at level \( l \), that is \[ n_l = 2^{l} \]
- Number of nodes searched in breadth first search \( n_e \) if the solution is at level \( l \) is \[ \sum_{i=0}^{l} 2^{i} = 2^{l+1}-1 \]
- Number of nodes expanded in Iterative Deepening \[ \mbox{Limit 1}: (2^1 - 1) \\ \mbox{Limit 2}: (2^2 - 1) \\ \mbox{Limit 3}: (2^3 - 1) \\ ... \]
- Each level will be expanded l - i times \[ n_e = \sum_{i=0}^{l} (l-i)*2^{i} \approx 2^{l+1} \]
- Compare that to the cost of breadth first search \[ 2^{l+1} - 1 \]
- Even with a small branching factor of 2, 50% of the nodes are leaf nodes.
- So even if we expand the nodes in the upper layers of the tree often (worst case it would be l times for the root node), it will only add a small portion to the runtime.
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
print( f'branching factor {b} and depth {d}, DFS {dfs(b,d)} IDDFS {iddfs(b,d)}')
branching factor 2 and depth 4, DFS 15 IDDFS 42
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
print( f'branching factor {b} and depth {d}, DFS {dfs(b,d)} IDDFS {iddfs(b,d)} Overhead: {iddfs(b,d)/dfs(b,d)}')
branching factor 2 and depth 4, DFS 15 IDDFS 42 Overhead: 2.8
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}, DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}'%)
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}, DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}'%) )
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}, DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}%')
branching factor 2 and depth 4, DFS 15 IDDFS 42 Overhead: 300%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print('DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}%')
branching factor 2 and depth 4
DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}%')
branching factor 2 and depth 4 DFS 15 IDDFS 42 Overhead: 300%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,20
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2)*100}%')
branching factor 2 and depth 20 DFS 1048575 IDDFS 4194050 Overhead: 400%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,20
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 20 DFS 1048575 IDDFS 4194050 Overhead: 400%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,5
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 5 DFS 31 IDDFS 99 Overhead: 319%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,50
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 50 DFS 1125899906842623 IDDFS 4503599627369117 Overhead: 400%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,10
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 10 DFS 1023 IDDFS 4017 Overhead: 393%
def iddfs( b, d ):
sum = 0
for i in range( d+1 ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,3
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 3 DFS 7 IDDFS 16 Overhead: 229%
def iddfs( b, d ):
sum = 0
for i in range( d ):
for j in range( i ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,3
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 3 DFS 7 IDDFS 1 Overhead: 14%
def iddfs( b, d ):
sum = 0
for i in range( d ):
for j in range( i+1 ):
sum = sum + dfs(b,j)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,3
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 3 DFS 7 IDDFS 5 Overhead: 71%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,3
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 3 DFS 7 IDDFS 11 Overhead: 157%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,4
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 4 DFS 15 IDDFS 26 Overhead: 173%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,5
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round(n1/n2 * 100)}%')
branching factor 2 and depth 5 DFS 31 IDDFS 57 Overhead: 184%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,5
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 5 DFS 31 IDDFS 57 Overhead: 84%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,3
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 3 DFS 7 IDDFS 11 Overhead: 57%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,5
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 5 DFS 31 IDDFS 57 Overhead: 84%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,6
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 6 DFS 63 IDDFS 120 Overhead: 90%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,6
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 ) * 100)}%')
branching factor 2 and depth 6 DFS 63 IDDFS 120 Overhead: 190%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,6
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 6 DFS 63 IDDFS 120 Overhead: 90%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,6
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n2/n1 ) * 100)}%')
branching factor 2 and depth 6 DFS 63 IDDFS 120 Overhead: 52%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,2
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n2/n1 ) * 100)}%')
branching factor 2 and depth 2 DFS 3 IDDFS 4 Overhead: 75%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,10
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n2/n1 ) * 100)}%')
branching factor 2 and depth 10 DFS 1023 IDDFS 2036 Overhead: 50%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 2,10
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 2 and depth 10 DFS 1023 IDDFS 2036 Overhead: 99%
fig=plt.figure(dpi=200)
ax1 = fig.add_subplot(1,2,1)
bs=np.arange(10,24,3)
xs = np.arange(2,10)
ydfs = np.zeros((len(bs), len(xs)))
yiddfs = np.zeros((len(bs),len(xs)))
for bi in range(len(bs)):
b = bs[bi]
for i in range(len(xs)):
ydfs[bi,i] = dfs(b,i)
yiddfs[bi,i] = iddfs(b,i)
for bi in range(len(bs)):
ax1.plot(xs, ydfs[bi], label=f'dfs b={bs[bi]}' )
ax1.plot(xs, yiddfs[bi], label=f'iddfs b={bs[bi]}' )
ax1.legend()
ax2 = fig.add_subplot(1,2,2)
for bi in range(len(bs)):
ax2.plot(xs, yiddfs[bi]/ydfs[bi], label=f'dfs/iddfs b={bs[bi]}' )
ax2.legend()
dfsf1 = addJBFigure( "dfsf1", 0, 0, fig )
plt.close()
Overhead of Iterative Deepening Methods
- Even though it may sound like a big waste of runtime (a lot of extra work), the overhead for iterative deepening depth first search is dependent on the depth and the branching factor
- Worst case is for small branching factors (e.g., b=2), but for realistic branching factors (b>10) the overhead is less than 30%
- For a branching factor of b=22, overhead is only 8%
def iddfs( b, d ):
sum = 0
for i in range( d ):
sum = sum + dfs(b,i+1)
#print(f'IDDFS b={b}, d={d}, expands {sum} nodes' )
return sum
def dfs( b, d ):
exp = 0
for j in range( d ):
#print( f'Expand all nodes at level {j}, {b**j} nodes')
exp = exp + b ** j
#print( f'Depth first search to level {d} expands {exp} nodes')
return exp
b,d = 22,10
n1 = iddfs(b,d)
n2 = dfs( b,d )
print( f'branching factor {b} and depth {d}' )
print( f'DFS {n2} IDDFS {n1} Overhead: {round( ( n1/n2 - 1 ) * 100)}%')
branching factor 22 and depth 10 DFS 1264758228163 IDDFS 1324984810456 Overhead: 5%
fig=plt.figure(dpi=200)
ax1 = fig.add_subplot(1,2,1)
bs=np.arange(10,24,3)
xs = np.arange(2,10)
ydfs = np.zeros((len(bs), len(xs)))
yiddfs = np.zeros((len(bs),len(xs)))
for bi in range(len(bs)):
b = bs[bi]
for i in range(len(xs)):
ydfs[bi,i] = dfs(b,i)
yiddfs[bi,i] = iddfs(b,i)
for bi in range(len(bs)):
ax1.plot(xs, ydfs[bi], label=f'dfs b={bs[bi]}' )
ax1.plot(xs, yiddfs[bi], label=f'iddfs b={bs[bi]}' )
ax1.legend()
ax2 = fig.add_subplot(1,2,2)
for bi in range(len(bs)):
ax2.plot(xs, yiddfs[bi]/ydfs[bi], label=f'dfs/iddfs b={bs[bi]}' )
ax2.legend()
dfsf1 = addJBFigure( "dfsf1", 0, 0, fig )
plt.close()
Overhead of Iterative Deepening Methods
- Even though it may sound like a big waste of runtime (a lot of extra work), the overhead for iterative deepening depth first search is dependent on the depth and the branching factor
- Worst case is for small branching factors (e.g., b=2), but for realistic branching factors (b>10) the overhead is less than 30%
- For a branching factor of b=22, overhead is only 8%
Overhead of Iterative Deepening Methods
- Even though it may sound like a big waste of runtime (a lot of extra work), the overhead for iterative deepening depth first search is dependent on the depth and the branching factor
- Worst case is for small branching factors (e.g., b=2), but for realistic branching factors (b>10) the overhead is less than 10%