Bidirectional Search in Artificial Intelligence

Bidirectional Search

Bidirectional Search is used when a problem has a single goal state that is given explicitly and all the node generation operators have inverses. Searching is done by searching forward from the initial node and backward from the goal node simultaneously. So, the program must save(store) the nodes so generated on both search frontiers until a common node is found. Both DFS and BFS can be modified slightly to perform this search.

Time and Space Complexity of Bidirectional Search

To perform this search to a depth of k, the search is made from one direction and the nodes at depth k are stored. At some time, a search to a depth of k and k+1 is made from the other direction, and all nodes generated are matched against the nodes stored from the other side. The process is repeated for lengths k=0 to d/2 from both directions. So, its time and space complexity is both O(b^d/2) when node matching is done in constant time per node.