Solving Problems by Search

There are a couple ways to solve problems with search.

I will be talking about

• Backtracking Search
• Depth First Search (DFS)
• Breadth First Search (BFS)
• Iterative Deepening Search

|---------------------------|--------------|-----------------|--------------------| | Algorithm | Action Costs | Space Complexity| Time Complexity | |---------------------------|--------------|-----------------|--------------------| |Backtracking Search | any | $O(D)$ | $O(b^D)$ | |Depth First Search (DFS) | zero | $O(D)$ | $O(b^D)$ | |Breadth First Search (BFS) | $c\geq 0$ | $O(b^d)$ | $O(b^d)$ | |Iterative Deepening Search | $c\geq 0$ | $O(b^d)$ | $O(b^d)$ |