Uninformed Search Flashcards
What is the state space problem?
A state space problem consists of:
- a set of all states reachable from initial state(s) by any action sequence
- a subset of states called the start states
- a set of actions
- an action function: given a state and an action, returns a new state
- a (set of) goal state, specified as boolean function
-path cost
What is a state?
A state contains all of the information necessary to predict the effects of an action and to determine whether a state satisfies the goal.
What is a solution?
A solution is a sequence of actions that will get the agent from it’s current state to a state that satifies the goal.
What is breadth-first search?
Treats the frontier as a queue, always selects the earliest element added to the frontier. All nodes are expanded at a given depth int he tree before any nodes at the next level are expanded.
What are the properties of breadth-first search?
Completeness - guaranteed is b is finite
Admissibility - guaranteed if arcs have the same cost
Space - O(b^d)
Time - O(b^d)
Optimal - yes, but only if all actions have the same cost
What is Uniform Cost Search?
This search method is guaranteed to find a minimum-cost path. Is similar to a breadth-first search, but it selects a path with the lowest cost. The frontier is implemented as a priority queue. Reduces to Breadth-first search when all paths have the same cost.
What are the properties of Uniform-Cost Search?
Completeness - guaranteed if b is finite and cost >= e
Admissibility - guaranteed
Space - O(b^[1 + C / e])
Time - O(b^[1 + C / e])
Optimal - Yes - nodes expand in increasing order of g(n)
What is depth-first search?
Depth-first search expands nodes at the deepest level of the tree. Implements the frontier as a stack
What are the properties of Depth-First Search?
Completeness - not guaranteed
Admissibility - not guaranteed
Space - O(bm)
Time - O(b^m)
Optimal - No, can find suboptimal solutions first
What are the properties of depth-limited search?
Completeness - guaranteed, if b is finite
Admissibility - not guaranteed
Space - O(bk)
Time - O(b^k)
Optimal - No, can find suboptimal solutions first
What is depth-limited search?
Depth-first search with a depth limit. picking a good limit is a difficult problem though
What is iterative deepening search?
Repeatedly applies depth-first search with increasing depth limits.
Properties of iterative deepening search?
Completeness - guaranteed, if b is finite
Admissibility - guaranteed, if arcs have the same cost
Space - O(bd)
Time - O(b^d)
Optimal - yes, if step costs are identical
What is bi-directional search?
Search both forward from the initial state and backward from the goal. It needs to check for intersection as well.
What are the properties of bi-directional search?
Completeness - depends on the search algorithms used
Admissibility - depends on the search algorithms used
Space - O(b^d/2)
Time - O(b^d/2)
Optimal - Depends on the search algorithm used
