Bidirectional Search
What You'll Learn
You'll learn how running search from both start and goal states simultaneously can dramatically reduce the search space complexity.
The Core Idea
Until now, every search algorithm you've studied moves forward from the initial state toward the goal. Bidirectional search runs two searches at once: one forward from the start state and one backward from the goal state. When these two searches meet in the middle, you've found a solution path.
Think of it like two people searching for each other in a maze—one starting at the entrance, one at the exit. They'll meet much faster than if only one person walked the entire path.
Why This Matters: The Complexity Win
The magic is in the math. Traditional uninformed searches like BFS explore states up to depth d with branching factor b, touching roughly O(b^d) nodes.
Bidirectional search runs two searches, each going to depth d/2. Each search touches about O(b^(d/2)) nodes. Since we run two searches, the total is roughly 2 × O(b^(d/2)), which is still O(b^(d/2))—exponentially better!
Example: If b=10 and d=6, regular search touches ~1,000,000 nodes, but bidirectional only touches ~2,000.
Practical Considerations
You need a way to run the backward search, meaning you must be able to compute predecessors (what states lead to a given state). Both frontiers grow until they intersect—when a state appears in both explored sets, you've found your meeting point.
Key Takeaway: Bidirectional search meets in the middle, slashing complexity from O(b^d) to O(b^(d/2)) by searching simultaneously from start and goal states.