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.

CriterionBFS
CompleteYes (if is finite)
Time
Space, keeps every node in memory
OptimalYes, 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
CriterionUCS
CompleteYes (step costs positive)
Timenumber of nodes with cost of optimal solution, about
Spacesame as time
OptimalYes

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.

StepExpandFrontier after (node: )
1S (0)A: 1, B: 5, C: 15
2A (1)B: 5, G: 11, C: 15
3B (5)G: 10 (cheaper path replaces 11), C: 15
4G (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.