Bidirectional Search
Bidirectional Search
For successful implementation, the graph must support reverse traversal (from goal to
start), and the branching factor should not be excessively high to optimize memory and
time efficiency.
Example Overview
In the given example:
Step 1: Initialization
The forward search and backward search meet at node 9, the intersection node.
2. Efficiency:
When the branching factor b is large, the bidirectional approach significantly
reduces the number of nodes explored, improving efficiency.
3. Optimality:
If implemented carefully (e.g., with BFS in both directions), bidirectional search
ensures finding the shortest path (for uniform edge weights).
4. Memory Usage:
Compared to unidirectional BFS, which requires storing all explored nodes up to
depth d, bidirectional search requires storing nodes only up to depth d/2 in both
directions, reducing space requirements.
1. Path Construction:
While finding the intersection node is efficient, combining paths from the forward
and backward searches can be complex.
2. Backward Traversal:
Graphs must support reverse traversal from the goal node, which may not always
be possible in certain scenarios.
3. Synchronized Search:
Efficient synchronization of forward and backward searches can be challenging,
especially when the branching factor or graph structures differ significantly in
each direction.
4. Memory Use:
Although memory requirements are reduced compared to BFS, managing two
simultaneous frontiers still poses a challenge for larger graphs.