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.

Answer 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!

Answer 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)