Course contentsShow
← Computer Science
Lesson 2762 of 2,87261. AI and Search AlgorithmsFree lesson

Bidirectional Heuristic Search

Explore searching simultaneously from start and goal to reduce the search space exponentially.

Bidirectional Heuristic Search

You'll learn: How to combine bidirectional search with heuristics to exponentially reduce search effort in both directions.

The Core Idea

You already know Bidirectional Search (exploring from both start and goal until the searches meet) and A* (using heuristics to guide search efficiently). Bidirectional Heuristic Search marries these approaches: run informed searches simultaneously from the start state toward the goal and from the goal state backward toward the start.

The key challenge? You need heuristics that work in both directions. The forward search uses a heuristic estimating cost-to-goal h(n), while the backward search needs a heuristic estimating cost-from-start h_reverse(n). When these estimates are admissible and consistent, you maintain optimality while slashing the search space dramatically.

Why It's Powerful

Think of two rescue teams searching for each other in a forest. Without maps (uninformed), they wander broadly. With maps showing approximate distances (heuristics), each team heads intelligently toward where the other likely is. They meet much faster than either could traverse the entire forest alone.

Mathematically, if each direction explores O(b^(d/2)) nodes (where b is branching factor, d is solution depth), you've squared your efficiency compared to unidirectional search's O(b^d).

Practical Considerations

The searches must coordinate carefully—checking whether any node appears in both frontiers. The optimal solution path connects through the meeting point. Designing good reverse heuristics can be tricky: for route-finding, reversing edges works; for puzzle problems, you might need goal-to-start pattern databases.

Key Takeaway: Bidirectional Heuristic Search combines the exponential space savings of bidirectional search with the goal-directed efficiency of heuristics, requiring admissible forward and reverse heuristic functions to maintain optimality.