Breadth-First Search (BFS)
What You'll Learn
You'll learn how BFS systematically explores a state space level-by-level to guarantee finding the shortest path to a goal.
The Core Idea
Breadth-First Search is a complete and optimal uninformed search algorithm that explores all nodes at depth d before moving to any node at depth d+1. Think of it like ripples expanding outward from a stone dropped in water—each "ring" represents one level of depth from your starting point.
BFS uses a queue (First-In-First-Out) to manage the frontier. When you visit a node, you add all its successors to the back of the queue. This ensures you process nodes in the exact order they were discovered, guaranteeing that shallower nodes are always explored before deeper ones.
How It Works
- Start with the initial state in the frontier (queue)
- Remove the front node from the queue
- Check if it's a goal state
- If not, expand it: generate all successors and add them to the back of the queue
- Mark the node as explored (to avoid revisiting in graph search)
- Repeat until you find the goal or the queue is empty
Why It's Optimal
Since BFS explores by depth layer, it's guaranteed to find the shallowest goal first. If all actions have the same cost (unit cost), the shallowest solution is also the least costly, making BFS optimal for such scenarios.
The Trade-off
BFS is memory-intensive. It must store every node at the current depth level in memory simultaneously, which can grow exponentially with depth.
Key Takeaway: BFS guarantees completeness and optimality (for unit costs) by systematically exploring all paths of length d before any path of length d+1, using a queue to enforce level-by-level expansion.