We read on Wikipedia > Iterative deepening depth-first search that
The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal.
Wikipedia also gives some decent pseudocode for IDDFS; I pythonified it:
def IDDFS(root, goal): depth = 0 solution = None while not solution: solution = DLS(root, goal, depth) depth = depth + 1 return solution def DLS(node, goal, depth): print("DLS: node=%d, goal=%d, depth=%d" % (node, goal, depth)) if depth >= 0: if node == goal: return node for child in expand(node): s = DLS(child, goal, depth-1) if s: return s return None
So my question is, how does the space complexity include the branching factor? Does that assume that
expand(node) takes up
O(b) space? What if
expand uses a generator that only takes constant space? In that case, would the space complexity still be a function of the branching factor? Are there situations where it is even possible for
expand to be a constant-space generator?