Posts Tagged ‘Depth-first search’

Iterative Deepening Search

September 4th, 2010 2 comments

Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.

Breadth First Search Vs Depth First Search

September 4th, 2010 1 comment
Breadth First Search Depth First Search
Optimal solutions are always found

Multiple solutions found early

May arrive at solutions without examining much of search space
Will not go down blind alley for solution Needs little memory (only node in current path needs to be stored)
If solution path is long, the whole tree must be searched up to that depth May settle for non-optimal solution
All of the tree generated must be stored in memory May explore single unfruitful path for a long time (forever if loop exists!)

Depth First Search

September 4th, 2010 No comments

Depth First Search

Depth First Search

Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it has not finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.