Uninformed Search Flashcards
Why is iterative deepening used?
It combines the benefits of breadth first search and depth first search
What does iterative deepening do?
It tries all depth limits one by one.
What solution does iterative deepening get?
It gets the shallowest solution (benefit of breadth first search)
Which data structure does iterative deepening use?
A stack (benefit of depth first)
Why may iterative deepening seem wasteful?
As it resets after reaching each depth limit, but overhead small in comparison to exponential growth
What is the time complexity of iterative deepening?
O(b^d)
Where b = branch factor, d = depth of solution
What is the space complexity of iterative deepening
O(bd)
What is bidirectional search?
A search that simultaneously goes down the tree from the root and up the tree from goal
When does a bidirectional search work?
When there is one goal state
What is the time complexity of bidirectional search?
O(b ^ (d/2) )
What is the space complexity of bidirectional search?
O(b ^ (d/2) )
