Today I Learned

Some of the things I've learned every day since Oct 10, 2016

114: Iterative Deepening Search

Iterative deepening depth-first search is a graph traversal algorithm which visits (new) nodes in effectively the same order as breadth-first search, but with lower memory usage and a runtime of O(b^d) (where b is the branching factor of the graph and d is the depth of the goal node.

The algorithm does pretty much what the name describes: it iteratively performs a typical depth-first search up do a set maximum depth, incrementing the depth with each iteration. In this way, nodes are seen for the first time in the order they would be seen by BFS while using lower amounts of memory. In addition, since it runs on DFS the algorithm uses just O(d) space, where d is the depth of the goal.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: