Bidirectional Search, as the name implies, searches in two directions at the same time: one forward from the initial state and the other backward from the goal. This is usually done by expanding tree with branching factor b and the distance from start to goal is d. The search stops when searches from both directions meet in the middle.
Bidirectional search is a brute-force search algorithm that requires an explicit goal state instead of simply a test for a goal condition. Once the search is over, the path from the initial state is then concatenated with the inverse of the path from the goal state to form the complete solution path.
Bidirectional search still guarantees optimal solutions. Assuring that the comparisons for identifying a common state between the two frontiers can be done in constant time per node by hashing. The time complexity of Bidirectional Search is O(b^d/2) since each search need only proceed to half the solution path. Since at least one of the searches must be breadth-first in order to find a common state, the space complexity of bidirectional search is also O(b^d/2). As a result, it is space bound in practice.
ADVANTAGES
- The merit of bidirectional search is its speed. Sum of the time taken by two searches (forward and backward) is much less than the O(bd) complexity.
- It requires less memory.
DISADVANTAGES
- Implementation of bidirectional search algorithm is difficult because additional logic must be included to decide which search tree to extend at each step.
- One should have known the goal state in advance.
- The algorithm must be too efficient to find the intersection of the two search trees.
- It is not always possible to search backward through possible states.