7

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?

Improve this question

2 Answers 2

Reset to default
5

You're right. Wikipedia is wrong! Does anyone have the book referenced on Wikipedia to find out what they mean (maybe they're talking about an optimization of some sort)?

Check out http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288 and http://intelligence.worldofcomputing.net/ai-search/depth-first-iterative-deepening.html

Improve this answer
2
  • It feels rather self-serving to accept an answer that says I am right and wikipedia is wrong, but oh well. ;) Thanks for the response to my santiy-check.
    – Dan Burton
    Sep 16, 2011 at 0:08
  • 1
    Am I wrong or is iterative deepening (in chess at least) used with a transposition table (cache of positions) so branches times depth is the cache size (space used)?
    – Kevin
    Aug 7, 2012 at 3:32
0

I'm studying this as we speak, so let me try to answer this question (super late, I know) in hopes of understanding IDDFS more myself.

The O(bd) cost is derived from an implementation that uses a queue to store unexplored nodes, rather than recursion. If you think about it that way, then you can imagine that we expand the root node, and add b children to the queue (to be expanded later), then we pick one child (b-1 nodes left in the queue), expand it, and add its b children (b+(b-1) nodes in the queue), and repeat this process until we reach the goal node at depth d. At this point, we have expanded d nodes, yes? And each node leading up to the goal node has contributed b-1 nodes to the queue. Hence, we have O( (d-1)(b-1)) = O(bd).

Returning to your implementation, yes, I think you're right about the O(b) term being contained in the expand function, since expand will return b children and expand will be called d-1 times. If expand uses a generator that takes constant space, sure, I think that would reduce the cost to O(d), but I don't see how expand could do anything but scale with the size of b.

Improve this answer
3
  • I don't think it has to scale with b. Consider a graph problem where we are given a string, and at each point we can swap the positions of the first character in the string and any other character in the string. Then expand(node) can return an iterator with an internal state of an integer n. Every time we get the next value of expand(node), we increment n and return the string that comes about from swapping the 1st and nth character, and once n reaches the length of the string we stop. Here the internal storage of expand(node) only takes space proportional to the the log of the length of the
    – raptortech97
    Oct 7, 2014 at 22:08
  • string, or ln(b).
    – raptortech97
    Oct 7, 2014 at 22:08
  • What you described is a specific application which uses the nature of the problem to simplify the description of a node. You're right in that the space cost scales with log(b) (still scales with b, just not linearly). I (and I believe the question) was referring to a general instance of IDDFS that makes no assumptions about the problem statement, and only works on a generic tree with branching factor b and goal depth d.
    – user1340033
    Oct 8, 2014 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.