[go: up one dir, main page]

0% found this document useful (0 votes)
265 views5 pages

Bidirectional Search

Bidirectional search is a graph search algorithm that simultaneously explores from both the start and goal nodes, terminating when the two searches meet at an intersection node, which enhances efficiency in large search spaces. The algorithm requires graphs to support reverse traversal and is optimal when implemented with breadth-first search in both directions. While it reduces search depth and memory usage, challenges include path construction complexity and the need for synchronized searches.

Uploaded by

swainlopamudra58
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
265 views5 pages

Bidirectional Search

Bidirectional search is a graph search algorithm that simultaneously explores from both the start and goal nodes, terminating when the two searches meet at an intersection node, which enhances efficiency in large search spaces. The algorithm requires graphs to support reverse traversal and is optimal when implemented with breadth-first search in both directions. While it reduces search depth and memory usage, challenges include path construction complexity and the need for synchronized searches.

Uploaded by

swainlopamudra58
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Bidirectional Search

Bidirectional search is a graph search algorithm that simultaneously searches from


the start node (in a forward direction) and the goal node (in a backward direction). The
algorithm terminates when the two searches meet at a common node, often called
the intersection node. By halving the effective search depth, this approach is significantly
more efficient than unidirectional searches such as BFS or DFS, especially in large search
spaces.

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:

 Start Node: Node 1 is the root of the search.


 Goal Node: Node 16 is the target.
 Intersection Node: The forward search from 1 and the backward search
from 16 meet at node 9.

Step-by-Step Explanation of Bidirectional Search

Step 1: Initialization

 Start two simultaneous searches:


o Forward Search from the root node 1.
o Backward Search from the goal node 16.
 Maintain two separate frontiers (queues) for each direction:
o The forward frontier starts with node 1.
o The backward frontier starts with node 16.

Step 2: Forward Search Expansion

 Expand the forward frontier:


o Start with node 1 (root node). Expand its neighbors: 4.
o Add node 4 to the forward frontier.
o From node 4, expand its neighbors: 2, 8. Add these nodes to the forward
frontier.

Step 3: Backward Search Expansion

 Expand the backward frontier:


o Start with node 16 (goal node). Expand its neighbors: 15.
o Add node 15 to the backward frontier.
o From node 15, expand its neighbors: 10, 12. Add these nodes to the
backward frontier.
Step 4: Intersection Detection

 The forward search and backward search meet at node 9, the intersection node.

Step 5: Path Construction

 Combine the paths from the forward and backward searches:


o Forward path: 1 → 4 → 8 → 9.
o Backward path: 16 → 15 → 10 → 9.
 The combined path is: 1 → 4 → 8 → 9 → 10 → 15 → 16.
Advantages of Bidirectional Search

1. Reduced Search Depth:


Bidirectional search effectively reduces the search depth from d to d/2, saving
significant computation time.

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.

Problems in Bidirectional Search

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.

You might also like