Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
A search algorithm explores the state space by generating successors of states already explored, building a search tree from the initial state.
Terms
| Term | Meaning |
|---|---|
| Frontier | candidate nodes waiting to be expanded |
| Explored (closed) set | nodes already expanded |
| Parent / child node | direct predecessor / direct successor |
| Root node | top node, no parent (the initial state) |
| Leaf node | node with no children |
| Branching factor | maximum (or average) number of successors of a node |
| depth of the least cost solution | |
| maximum depth of the state space |
A strategy is defined by the order of node expansion, i.e. which frontier node is picked next.
Four Criteria
| Criterion | Question |
|---|---|
| Completeness | does it always find a solution if one exists? |
| Time complexity | how long does it take, measured as number of nodes generated |
| Space complexity | maximum number of nodes kept in memory |
| Optimality | does it always find the best (least cost) solution? |
Uninformed vs Informed
Two families:
- uninformed (blind) search uses only the problem definition: BFS, UCS, DFS, depth limited, iterative deepening, and it is usually exponential in time and space
- informed (heuristic) search uses problem specific knowledge to decide the expansion order: greedy search and A*, usually far more efficient
Uninformed Summary
| Criterion | BFS | UCS | DFS | Depth limited | Iterative deepening | Bidirectional |
|---|---|---|---|---|---|---|
| Time | ||||||
| Space | ||||||
| Optimal | Yes* | Yes | No | No | Yes* | Yes |
| Complete | Yes | Yes | No | Yes if | Yes | Yes |
* when all step costs are equal.
Question to think: is an optimal strategy also complete? Yes, if it always returns the best solution then it must return some solution whenever one exists.
The details of each uninformed method start with Breadth-First and Uniform-Cost Search.