Uninformed Search Flashcards
How do we measure performance?
completeness, optimality, time complexity, and space complexity
completeness
Assuming there is a goal state, are we guaranteed to find it?
optimality
Are we guaranteed to find the goal state with the smallest path cost?
time complexity
How long does it take to find a goal state, measured by # nodes expanded?
space complexity
How much memory is used to find a goal state, measured by maximum # of nodes in the frontier?
What is the frontier in Breadth First Search (BFS)?
Queue
shallowest nodes are expanded first
What are the performance properties of BFS?
Complete: yes, in principle
Optimal: yes, if step-costs are identical
Time: O(b^d)
Space: O(b^d)
What is the frontier in Depth First Search (DFS)?
stack
deepest nodes are expanded first
What are the performance properties of DFS?
Complete: yes, if no cycles and finite
Optimal: no
Time: O(b^d)
Space: O(bd)
Depth-Limited Search
- requires parameter L
- deepest nodes are expanded first, but nodes deeper than L are discarded
What are the performance properties of DLS (depth-limited Search)?
Complete: depends on depth L
Optimal: yes, if d = L
Time: O(b^L)
Space: O(bL)
Iterative Deepening Search
run DLS, but repeatedly increasing depth limit
What are the performance properties of IDS (iterative deepening search)?
Complete: yes
Optimal: yes, if L increases linearly
Time: O(b^d)
Space: O(bd)
