Weak (uninformed) Search
Overview
- b: avg branching factor
- d: goal depth
- m: max depth
| Name | Space Complexity | Time Complexity | Complete | Optimal |
|---|---|---|---|---|
| Breadth-first search | O(bd+1), very bad | O(bd+1), very bad | Yes | No |
| Depth-firth search | O(b*m), very good | O(bm), very bad | No | No |
| Depth-limited search | O(b*L), great and controllable | O(bL), bad but limited | No | No |
| Iterative Deepening search | O(b*d), very good | O(bd), bad | Yes | No |
| Bidirectional search | O(bd/2), bad but better than O(bd) | O(bd/2), bad but better than O(bd) | Yes | Yes |
| Uniform cost search |  , very bad |
 , very bad |
Yes | Yes |
Iterative deepening
Depth-limited DFS
Bidirectional Search
Used when operators are reversible, and goal states
are known and few.
Uniform Cost Search
