Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Breadth-First Search (BFS)
BFS expands the shallowest unexpanded node first, using a FIFO queue for the frontier. All nodes at depth 1 are expanded, then depth 2, and so on.
| Criterion | BFS |
|---|---|
| Complete | Yes (if is finite) |
| Time | |
| Space | , keeps every node in memory |
| Optimal | Yes, when all step costs are equal |
Memory is the real problem. With , depth 12 needs about nodes, around 35 years and 111 TB in the lecture's table.
Uniform-Cost Search (UCS)
UCS handles different edge costs by expanding the frontier node with the lowest path cost from the start. The FIFO queue is replaced by a priority queue ordered by .
Rules:
- the goal test is done when a node is taken out for expansion, not when it is added to the frontier
- nodes already expanded are not expanded again
- BFS is the special case of UCS with , so with equal step costs the two behave the same
| Criterion | UCS |
|---|---|
| Complete | Yes (step costs positive) |
| Time | number of nodes with cost of optimal solution, about |
| Space | same as time |
| Optimal | Yes |
Worked Example
Edges: S to A cost 1, S to B cost 5, S to C cost 15, A to G cost 10, B to G cost 5, C to G cost 5.
| Step | Expand | Frontier after (node: ) |
|---|---|---|
| 1 | S (0) | A: 1, B: 5, C: 15 |
| 2 | A (1) | B: 5, G: 11, C: 15 |
| 3 | B (5) | G: 10 (cheaper path replaces 11), C: 15 |
| 4 | G (10) | goal test passes, stop |
UCS returns S, B, G with cost 10. If G had been goal tested when first generated, the worse path S, A, G (cost 11) would have been returned, which is why the test waits until expansion.
To save memory, the deep-first alternatives are in Depth-First and Iterative Deepening Search.