Search thru a Problem Space / State Space
- Set of states
- Operators [and costs]
- Start state
- Goal state [test]
Output
- Path: start ⇒ a state satisfying goal test
- [May require shortest path]
- [Sometimes just need state passing test]
Search Methods
Blind search
- Depth first search (DFS)
- Breadth first search (BFS)
- Iterative deepening depth-first search (IDS)
Heuristic search
- Best first search
- Uniform cost search (UCS)
- Greedy search
A*
- Iterative Deepening
A*
(IDA*
)
- Beam search
- Hill climbing
Depth First Search