Depth-First Iterative Deepening vs Depth-First Search
Depth-first iterative deepening is an optimal uninformed search algorithm in both time and space on exponential trees. The videos on this page illustrate the difference between the two approaches. In the first video we can see that the DFID approach can find the goal much faster, because it doesn't spend time searching any deeper than the goal. The remaining videos show the potential overhead of DFID because of its iterations at shallower depths. The larger the branching factor, the smaller the overhead of the iterative deepening.
These videos are intended for use along side other teaching material. The videos are freely available for educational use.
In all the videos below the red line is DFID and the green line is DFS.
DFID vs DFS: shallow goal (solution depth 3, tree depth 4)
DFID vs DFS: Branching factor 2 (goal in lower right corner)
DFID vs DFS: Branching factor 3 (goal in lower right corner)
DFID vs DFS: Branching factor 4 (goal in lower right corner)
DFID vs DFS: Branching factor 5 (goal in lower right corner)
DFID vs DFS: Branching factor 6 (goal in lower right corner)
DFID vs DFS: Branching factor 7 (goal in lower right corner)
DFID vs DFS: Branching factor 8 (goal in lower right corner)
DFID vs DFS: Branching factor 9 (goal in lower right corner)
Download all movies as .zip file (131.6MB)