In bidirectional search, two simultaneous searches are run. One search starts from the initial state, called forward search and the other starts from the goal state, called backward search.

The search process terminates when the searches meet at a common node of the search tree.

For e.g. consider a problem which has a solution at depth d=6. If we run breadth first search in each direction, then in the worst case the two searches meet when they have generated all nodes at depth 3. If b=10.

Process:

Performance evaluation:

Completeness: Yes, if the branching factor b is finite and both directions use breadth first search.

Optimality: Yes, if all costs are identical and both directions use breadth first search.

Time complexity: It is O(bd/2).

Space complexity: The space complexity is O(bd/2).