Bidirectional Search Algorithm in Artificial Intelligence

Bidirectional Search Algorithm in Artificial Intelligence

 What is Bidirectional Search Algorithm? A bidirectional search is a searching technique. It is a combination of forwarding and backward se... July 27, 2022

 What is Bidirectional Search Algorithm?

• A bidirectional search is a searching technique.
• It is a combination of forwarding and backward search.
• It works on a directed graph.
• It runs two simultaneous searches, one form initial state called as forward-search and other from goal node called as backward-search, to find the goal node.
• the algorithm stops when the two searches meet at a node.
• It is a faster approach, reduces the time required for traversing the graph.
• Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.

Why do we need Bidirectional Search Algorithm?

• Because in many cases it is faster, it dramatically reduce the amount of required exploration.
• Suppose if branching factor of tree is b and distance of goal vertex from source is d, then the normal BFS/DFS searching complexity would be O(b^d).  
• On the other hand, if we execute two search operation then the complexity would be O(b^d/2) for each search and total complexity would be O(b^d/2 +b^d/2) which is far less than O(b^d).
  
• it is a faster technique, and improves the amount of time required for traversing the graph.
• This approach is efficient in for the case when the starting node and goal node are unique and defined. branching factor is same for both directions.

Bidirectional Search – Example

• Step 1: Say, 1 is the initial node and 16 is the goal node, and 9 is the intersection node.
• Step 2: We will start searching simultaneously from start to goal node and backward from goal to start node.
• Step 3: Whenever the forward search and backward search intersect at one node, then the searching stops.

Real life Applications Of Bidirectional SearchAlgorithm

•  
  

Advantages of Bidirectional Search:

• Bidirectional search is fast.
• Bidirectional search requires less memor.
• It drastically reduces the time taken by the search by having simultaneous searches.
• It also saves resources for users as it requires less memory capacity to store all the searches.

Disadvantages of Bidirectional Searchare:

• The fundamental issue with bidirectional search is that the user should be aware of the goal state to use bidirectional search and thereby to decrease its use cases drastically.
• The implementation is another challenge as additional code and instructions are needed to implement this algorithm, and also care has to be taken as each node and step to implement such searches.
• The algorithm must be robust enough to understand the intersection when the search should come to an end or else there’s a possibility of an infinite loop.
• It is also not possible to search backwards through all states.
• Implementation of the bidirectional search tree is difficult.
• In bidirectional search, one should know the goal state in advance.
  

Performance Measurement:

• Completeness: Bidirectional Search is complete if we use BFS in both searches.
• Time Complexity: Time complexity of bidirectional search using BFS is O(b^d).
• Space Complexity: Space complexity of bidirectional search is O(b^d).
• Optimal: Bidirectional search is Optimal.