Uninformed Search
AIMA 3.3-3.4; Appendix A.1
CMPSC 442
Week 3, Meeting 7, Four Segments
Outline: Uninformed Search
1. Evaluating Search Algorithms
2. Tree Search versus Graph Search
3. Four Algorithms (BFS, UCS aka BF, DFS, Iterative Deepening)
4. Comparison of Search Algorithms
Outline, Wk 3, Mtg 7 2
Uninformed Search
AIMA 3.3-3.4; Appendix A.1
CMPSC 442
Week 3, Meeting 7, Segment 1 of 4: Evaluating Algorithms
Evaluating Algorithms
● Completeness: Will a solution be found?
● Time complexity
● Space complexity
● Cost Optimality: Will the optimal (lowest cost) solution be found?
4Evaluating Search Algorithms
Two Ways to Compare Algorithm Efficiency
● Benchmarking:
○ Empirical measurement on benchmark tasks
○ Very specific:
■ A specific language and implementation
■ A specific computer and operating system
■ A specific suite of datasets
● Mathematical Analysis with big O notation
○ Asymptotic analysis: how computation time changes with length of input
○ Abstracts over
■ The exact number of operations
■ The content of the input
5Evaluating Search Algorithms
Complexity Analysis and O() Notation
● Consider an alernative notation using number of operations
○ Would have to be relative to specific inputs
○ Requires use of average, worst-case or best-case formulations
● O() notation summarizes the large-scale performance
○ Easier to use than assessing actual number of operations
○ Less precise than the alternative
● O(n) time and space complexity versus O(n2)
○ As input approaches infinity, O(n) is necessarily better than O(n2)
○ For smaller input sizes, depending on the algorithm, O(n2) could be faster
6Evaluating Search Algorithms
Components of O() Notation
● b (branching factor): number of successors of a search node
● d (depth): number of actions in optimal solution
● m (maximum depth): maximum actions on any path
7Evaluating Search Algorithms
Space or Time Complexity
● Big O notation ignores constant multiplicative factors
● Consider Big O notation
○ Rate of growth of runtime grow relative to input
○ Time complexity: O(α) constant time; O(n) linear time; . . .
● Space complexity is analogous to time complexity
○ Size of memory instead of size of input
○ Units of space are arbitrary
○ Plausible Space units:
■ One memory word
■ Size of any fixed size data structure
8Evaluating Search Algorithms
Breadth First Search Completeness (Mtg 6, last topic)
Given a finite branching factor b and finite state space S
● BFS is complete
○ At each depth, it branches at most b times
○ It continues to each next depth until
■ The frontier is empty: NO SOLUTION
■ The goal state is reached: SUCCESS
9Evaluating Search Algorithms
BFS Space & Time Complexity
O(bd)
● Optimal solution is at depth d
● Nodes remain in memory, so time complexity = space complexity
○ 1 + b + b2 . . . bd = O(bd)
Memory requirements quickly become a problem
● Consider b=10, speed = 1M nodes/sec, memory = 1K/node, d=10
○ Search time: 3 hours
○ Search space: 10 Terabytes
In practice, BFS cannot solve problems with large state space
10Evaluating Search Algorithms
BFS Cost Optimality
● Necessarily finds shortest solution first
○ Only goes to depth d+1 if there is no solution at d or less
○ Therefore is optimal, if all actions have same cost
○ Many problems have actions with different costs, e.g., Romanian Road
Map problem
11Evaluating Search Algorithms