4 - Uninformed Search Flashcards
Define Uninformed Search
No Knowledge of the cost from current state to goal
Only knows when goal found
Define Heuristic
Informed search
Access to extra info
Typically a cost estimate from a heuristic function
What are the main steps of General search
- If goal state return solution
- Apply all applic. operators to current, gen new set of states - node/state expansion
- Decide next state and repeat. No more states = fail
What is a fringe/frontier?
The collection of nodes waiting to be expanded
What is node expansion?
Generating all successor nodes considering the available actions
Define search strategy
Which node is next
What is BFS?
Expands shallowest on fringe first
Expand all at depth d before d+1
Use a queue structure
What is DFS?
Expand deepest first
Follow branch fully
Use a stack
What is depth limited search?
If a solution is known to be no deeper than a certain level then apply cut off depth
What is IDS?
Iterative deepening search
- Run DLS lim d = 1
- if not found, run with d+1 until solution
same nodes generated multiple times
Criteria for search method evaluation
Time
Space
COmpleteness
Optimality
What is the branching factor?
Max num of successors of any node
What are the complexities of BFS?
Time = O(b^d) where b is num of successors Space = same as time Completeness = Yes Optimality = Yes, if step costs identical
DFS complexities
Time = O((b^m) where m is max depth Space = O(bm)
Completeness = No, may cause looping Optimality = No
DLS complexities
Time Complexity: every state has b successors, and depth limit l. O(bl).
• Space Complexity: Has space complexity O(bl).
• Completeness: Like DFS, DLS is not complete if the chosen depth is less than solution depth.
• Optimality: Like DFS, DLS is not optimal.
IDS complexities
Time = O(b^d) as nodes must be examined more than once (depth d and successors b)
Space = O(bd) Complete = Yes Optimality = Yes
What is UCS?
Uniform Cost Search
An extension of BFS which expands node with lowest path cost
What is path cost?
The cost of getting from start node to this node
g(n)
UCS COmplexities
Time = b times (c/e) where c is the cost of opimal solution and every action costs at least e
Space = same as time Complete = yes if every cost step > 0 Optimality = yes
What is Bidirectional Search?
Two simultaneous searches forward and backward.
Reduced time complexity but needs to compute successors and also predecessors