|
Breadth-First Search Breadth-first search goes through the tree level by level, visiting all of the nodes on the top level first, then all the nodes on the second level, and so on. This strategy has the benefit of being complete (if there's a solution, it will be found), and optimal as long as the shallowest solution is the best solution. However, the way breadth-first search achieves this is by keeping all of the leaf nodes in memory, which requires a prohibitive amount of memory when searching anything more than a very small tree. The time complexity of breadth-first search is O(b^d) where b is the branching factor (2 for the binary trees below) and d is the depth of the solution. |
|
|
Depth-First Search Depth-first search goes through the tree branch by branch, going all the way down to the leaf nodes at the bottom of the tree before trying the next branch over. This strategy requires much less memory than breadth-first search, since it only needs to store a single path from the root of the tree down to the leaf node. However, it is potentially incomplete, since it will keep going on down one branch until it finds a dead-end, and it is nonoptimal -- if there's a solution at the fourth level in the first branch tried, and a solution at the second level in the next one over, the solution at the fourth level will be returned. The time complexity of depth-first search is O(b^m) where b is the branching factor (2 for the binary trees below) and m is the maximum depth of the tree. Its space complexity is only b*m. Try searching for "a" and see which of the two solutions is found when using depth-first search. |
|
|
Depth-Limited Search Depth-limited search essentially does a depth-first search with a cutoff at a specified depth limit. When the search hits a node at that depth, it stops going down that branch and moves over to the next one. This avoids the potential problem with depth-first search of going down one branch indefinitely. However, depth-limited search is incomplete -- if there is a solution, but only at a level deeper than the limit, it will not be found. It is also nonoptimal in the same way as depth-first search is. The time complexity of depth-first search is O(b^l) where b is the branching factor (2 for the binary trees below) and l is the depth limit. Its space complexity is only b*l. The depth limit in this instance of the algorithm (set using the PARAM tag within the APPLET tag; view the source of the file to see) is 2. (The depth of the root node is 0.) |
|
|
Iterative Deepening Search Iterative deepening does repeated depth-limited searches, starting with a limit of zero and incrementing once each time. As a result, it has the space-saving benefits of depth-first search, but is also complete and optimal, since it will visit all the nodes on the same level first before continuing on to the next level in the next round when the depth is incremented. The time complexity of iterative deepening search is O(b^d) where b is the branching factor (2 for the binary trees below) and d is the depth of the solution. The space complexity is O(bd). |