5. Bidirectional Search:

• • Bidirectional search algorithm runs two searches simultaneously, one from initial node to goal node called as forward search and other from the goal node to initial node is called backward search, to find the goal node.
• • Bidirectional search replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and other starts from the goal vertex, the search stops when two graphs intersect each other.
• • Bidirectional search can use the search algorithms like Breadth First Search (BFS), Depth First Search (DFS), Depth limited Search (DLS) etc.

Advantages

• • Bidirectional search is fast
• • Bidirectional search requires less memory

Disadvantages

• • Implementation of the bidirectional search tree is difficult.
• • In bidirectional search, one should know the goal state in advance.

Time complexity

Time Complexity of Bidirectional Search using Breadth Fisrt Search (BFS) is O(b^d)

Space complexity

Space Complexity of Bidirectional Search using Breadth First Search (BFS) is O(b^d)

Completeness

Bidirectional Search is Complete if we use Breadth First Search (BFS) in both the cases.

Optimal

Optimal Bidirectional Search is Optimal

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc