Hosted Pages



Pathfinding Benchmarks



Grid-Based Path Planning Competition



AAAI 2017 Job Fair


AAAI 2017 Workshop on what's next for AI in games


Archived Pages


AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

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)


© Nathan Sturtevant, All rights reserved.