Uninformed Search
AIMA 3.3-3.4; Appendix A.1
CMPSC 442
Week 2, Meeting 7, Segment 4 of 4: Comparison of Search
Algorithms
UCS Evaluation
● Complete, like BFS
● Optimal for any step cost function
● Time complexity contingent on step costs
○ Let ε = min
a∈A
cost(a) and consider the case ε > 0 (lower bound on cost of an
action)
○ Let C∗ be the optimal solution cost
○ Let b be the branching factor and consider the case b ≥ 2
○ Then the time complexity is at most O(b1+⌊C∗/ε⌋) (⌊C∗/ε⌋ meaning floor of C*/ε)
● Space complexity = time complexity
33Comparison of Search Algorithms
Becky
Becky
DFS Evaluation
● Not complete
● Therefore not optimal
● Time complexity = O(bm)
○ Terrible if m >> d
○ Potentially more efficient than BFS if solutions are dense
● Space complexity = O(bm)
○ Linear space complexity!
34Comparison of Search Algorithms
Becky
Iterative Deepening Evaluation
● Complete
● Optimal if step cost = 1 (like BFS)
● Time complexity
○ Same as BFS, O(bd)
○ Expensive!
● Space complexity
○ Stores only the path it is currently expanding
○ O(d)
35Comparison of Search Algorithms
Comparison of Uninformed Search Algorithms
36Comparison of Search Algorithms
Criterion BFS UCS DFS Depth Limit. Iterative Dp
Completeness Yes, if . . . Yes No No Yes
Optimality Yes, if . . . Yes No No Yes
Time Complexity bd b⌊c∗/ε⌋+1 bm bl bd
Space Complexity bd b⌊c∗/ε⌋+1 bm bl bd
Becky
Summary
● Uninformed search algorithm evaluation uses
○ Completeness
○ Optimality
○ Time Complexity
○ Space complexity
● Graph search uses more memory than tree-like search but avoids
repeated states
● The best uninformed search, iterative deepening, combines the best of
BFS and DFS
37Summary, Wk 3, Mtg 7