Vocab
Transition model - going from an action to resulting state space (getting the next state) State space - set of possible states Action cost Start state Goal
Fundamental Counting Principle
Basically the number of options is the number of possible states.
State Space Graphs
A graph with nodes as states and edges as actions Each state appears at once Typically too large to store in memory
Search Trees
Depicts entire path that one can travel from start state (root note) to the given state State can appear multiple times
How to perform computation on these structures when they’re so large?
Only store needed states (ones that are being worked with, getting next state, actions, costs, as necessary along the way) Typically performed with search trees, replacing curr state with their children until goal state
Iterative Uninformed Search
Selecting a node on the frontier and replacing it with all its children if it is not goal state
What is a frontier?
just the current nodes being looked at
Three basic categories
- DFS
- BFS
- Uniform Cost Search
How do we evaluate search strategies?
Completeness: can it find the goal given enough resources? Optimality: will it find the lowest cost path to the goal? Branching factor: the increase in nodes on the frontier at each step Time complexity
DFS
Stack, evaluating deepest nodes first
Isn’t complete because if graph has cycles, then could be in an infinite loop Isn’t optimal because it just finds the leftmost solution; no cost consideration worst-case - reaches the goal last (if goal is on right)
BFS
shallowest nodes first queue
is complete (because it goes by shallowest, so even if infinite, it will hit goal state first if it exists)
unoptimal - no cost consideration (only optimal if edge costs are all equal) worst-case - goal is bottom right of tree and super far
Uniform Cost Search
priority queue chooses lowest cost node each step, replacing with children in frontier repeats
Greedy
complete because if a solu exists, then it must have some shortest path optimal because guaranteed to find lowest cost path to goal
- only with nonnegative edge costs
See also Informed Search