Depth First Search
The most important AI search algorithm?
MERGE = push
- treat list as a stack
- new search states to explore at front of list, get treated first
What about when many new states created?
- We use a heuristic to decide what order to push new states
- all new states in front of all old states in the list
What about when no new states created?
- We must be at a leaf node in the search tree
- we have to backtrack to higher nodes