Chapter 2 : Search Flashcards
What is uniformed search?
Has no idea what the environment entails
What is informed search?
Uses information about environment to conduct a search efficiently
What are the complete/optimal/complexities of breadth-first search
Complete: yes
Optimal: yes
Time complexity: O(b^d)
Space complexity: O(b^d)
where d is depth of solution
What are the complete/optimal/complexities of uniform cost search?
Complete: yes
Optimal: yes
Time complexity: O(b^(c/epsilon)+1)
Space complexity: O(b^(c/epsilon)+1)
What are the complete/optimal/complexities of depth-first search?
Complete: no
Optimal: no
Time complexity: O(b^M)
Space complexity: O(b^M)
where M is depth of tree
What are the complete/optimal/complexities of depth-limited search?
Complete: if l >= d yes, if l < d no
Optimal: only optimal if l = d, otherwise no
Time complexity: O(b^L)
Space complexity: O(b^L)
where l is level and d is depth of solution
What are the complete/optimal/complexities of iterative deepening tree?
Complete: yes
Optimal: yes
Time complexity: O(b^d)
Space complexity: O(b*d)
d is depth of solution
What are the complete/optimal/complexities of bidirectional tree?
Complete: yes
Optimal: yes
Time complexity: O(b^(d/2))
Space complexity: O(b^(d/2))
d is depth of solution
What are the complete/optimal/complexities of greedy best-first search?
Complete: yes, in finite spaces
Optimal: no, can make a bad decision
Time complexity: O(b^M)
Space complexity: O(b^M)
where M is depth of tree
What are the complexities of A* Pathfinding?
Complete: yes
Optimal: yes
*Only if a good heuristic is used
What is local search?
Only operate on single current node (rather then looking at entire state) and generally only moves to neighbors
What are advantages of local search?
- Less memory
- Can find reasonable solutions in huge state spaces which would not be possible with informed/uninformed searches
Where does hill climbing search get stuck?
plateaus, local maxima, ridges
What are solutions to fixing hill climbing search?
- Random restart
- Problem reformulation
Is hill climbing search guaranteed to find solution?
False, if probability of finding solution is p chance of finding a solution on each restart is 1/p
What does simulated annealing search do?
Algorithm allows “smartly” to make bad decisions in hopes it will lead to an eventual smart decision at end.
f - heuristic function
T - temperate (if larger then accepts worse decisions)
What is local beam search?
- Starts with k randomly generated states
- If goal found stop, otherwise pick best k’ states
What is gradient/descent search?
Used for continuous environments to find minma/maxima
What is adversarial search?
Used in multi-agent competitive environments where agents goals are in conflict
What is Mini-max search?
Adversarial search algorithm that assumes
- 2 Players
- Game is zero-sum (one wins)
- Each player plays optimally
- One player tries to maximize utility function other tries to minimize it
What is alpha beta pruning?
Used in Minimax state trees on terminal nodes that will have no impact on decisions
