Iterative deepening vs depth-first search

Question

I keep reading about iterative deepening, but I don't understand how it differs from depth-first search.

I understood that depth-first search keeps going deeper and deeper.

In iterative deepening you establish a value of a level, if there is no solution at that level, you increment that value, and start again from scratch (the root).

Wouldn't this be the same thing as depth-first search?

I mean you would keep incrementing and incrementing, going deeper until you find a solution. I see this as the same thing! I would be going down the same branch, because if I start again from scratch I would go down the same branch as before.

Solution 1

In a depth-first search, you begin at some node in the graph and continuously explore deeper and deeper into the graph while you can find new nodes that you haven't yet reached (or until you find the solution). Any time the DFS runs out of moves, it backtracks to the latest point where it could make a different choice, then explores out from there. This can be a serious problem if your graph is extremely large and there's only one solution, since you might end up exploring the entire graph along one DFS path only to find the solution after looking at each node. Worse, if the graph is infinite (perhaps your graph consists of all the numbers, for example), the search might not terminate. Moreover, once you find the node you're looking for, you might not have the optimal path to it (you could have looped all over the graph looking for the solution even though it was right next to the start node!)

One potential fix to this problem would be to limit the depth of any one path taken by the DFS. For example, we might do a DFS search, but stop the search if we ever take a path of length greater than 5. This ensures that we never explore any node that's of distance greater than five from the start node, meaning that we never explore out infinitely or (unless the graph is extremely dense) we don't search the entire graph. However, this does mean that we might not find the node we're looking for, since we don't necessarily explore the entire graph.

The idea behind iterative deepening is to use this second approach but to keep increasing the depth at each level. In other words, we might try exploring using all paths of length one, then all paths of length two, then length three, etc. until we end up finding the node in question. This means that we never end up exploring along infinite dead-end paths, since the length of each path is capped by some length at each step. It also means that we find the shortest possible path to the destination node, since if we didn't find the node at depth d but did find it at depth d + 1, there can't be a path of length d (or we would have taken it), so the path of length d + 1 is indeed optimal.

The reason that this is different from a DFS is that it never runs into the case where it takes an extremely long and circuitous path around the graph without ever terminating. The lengths of the paths are always capped, so we never end up exploring unnecessary branches.

The reason that this is different from BFS is that in a BFS, you have to hold all of the fringe nodes in memory at once. This takes memory O(b^d), where b is the branching factor. Compare this to the O(d) memory usage from iterative deepening (to hold the state for each of the d nodes in the current path). Of course, BFS never explores the same path multiple times, while iterative deepening may explore any path several times as it increases the depth limit. However, asymptotically the two have the same runtime. BFS terminates in O(b^d) steps after considering all O(b^d) nodes at distance d. Iterative deepening uses O(b^d) time per level, which sums up to O(b^d) overall, but with a higher constant factor.

In short:

• DFS is not guaranteed to find an optimal path; iterative deepening is.
• DFS may explore the entire graph before finding the target node; iterative deepening only does this if the distance between the start and end node is the maximum in the graph.
• BFS and iterative deepening both run in time O(b^d), but iterative deepening likely has a higher constant factor.
• BFS uses O(b^d) memory, while iterative deepening uses only O(d).

Hope this helps!

Solution 2

There is a decent page on wikipedia about this.

The basic idea I think you missed is that iterative deepening is primarily a heuristic. When a solution is likely to be found close to the root iterative deepening is will find it relatively fast while straightfoward depth-first-search could make a "wrong" decision and spend a lot of time on a fruitless deep branch.

(This is particularly important when the search tree can be infinite. In this case they are even less equivalent since DFS can get stuck forever while BFS or iterative deepening are sure to find the answer one day if it exists)

Solution 3

Just adding to what's already here, but here are some videos from University of Denver's Moving AI Lab that show the differences.

http://movingai.com/dfid.html

You can see in their examples iterative deepening wins when the goal is shallow (solution depth 3, tree depth) and the solution is on the right, but DFS wins no matter what if the solution is in the last row.

I got into this reading about chess programming, next up for me was thinking about quiescence search check that out if you want to know more about search strategies for AI programming.

Comments

[HelloGoodbye]

In depth-first search, you explore each branch you enter completely before backtracking from it and going to the next one. In iterative deepening, you don't go below the current depth, and hence don't explore each branch you visit completely before backtracking.

[bb2]

Thank you! I was missing the concept that iterative deepening would consider ALL the paths of length x.

[Rob Neuhaus]

One small point is that even though IDDFS does more node expansions, it might even be faster than BFS because using less memory means better locality and cache coherency.

[Nico]

Thanks for this detailed answer. But wouldn't iterative deepening only be optimal if the cost associated with each path is the same. And hence not optimal when the costs differ? In that case, is there an algorithm related to iterative deepening that is always optimal? Like for example, for BFS, we have uniformed cost search.

[templatetypedef]

@NicolásCarlo- That's correct; iterative deepening does assume uniform costs. When there are weights on the edges, you can use IDA* (iterative-deepening A*).

[LemonPi]

BFS takes O(b^{d+1}) time and space since it has to expand the frontier nodes, so if the target node is the last one explored with depth d, then you would've expanded all of the other depth d nodes. IDS only takes O(b^d) time because the nodes past limit are not expanded (d+1)b^0 + (d)b^1 + (d-1)b^2 + ... + (1)b^d = O(b^d) where the first coefficient is the number of times you visit that node.

[user2023370]

The following link states that iterative deepening uses O(d) memory: cs.stackexchange.com/a/328/17901

[templatetypedef]

@user2023370 Good catch! Fixed.