Bidirectional Search

The algorithm maintains two separate search frontiers: one expanding from the initial state and one from the goal state. The core challenge is efficiently detecting when these frontiers intersect or 'meet' in the state space. This requires a mechanism to check if a node generated by one search already exists in the closed set or frontier of the opposite search. Common strategies include using a shared hash table or alternating between search steps.

In a graph where a unidirectional search like BFS explores O(b^d) nodes (where b is branching factor, d is solution depth), a bidirectional search ideally explores O(b^{d/2}) nodes from each direction. This represents an exponential reduction in the number of nodes expanded, making it highly efficient for problems with a known goal state and reversible actions. The total effort is roughly 2 * O(b^{d/2}), which is vastly superior to O(b^d) for large d.

For the backward search to be feasible, the successor function (actions) must be invertible. The algorithm must be able to generate the predecessors of a state—the states that can lead to it. If operators are not naturally reversible, a separate inverse model must be defined. This characteristic limits applicability; for example, it works perfectly for road navigation but may be complex for state spaces where actions have irreversible effects.

When using Breadth-First Search (BFS) or Uniform-Cost Search (UCS) for each direction, bidirectional search is complete (will find a solution if one exists) and optimal (will find the shortest path), provided the graph is finite and the backward search is well-defined. The meeting point of the two searches is guaranteed to be on an optimal path when using these systematic, unidirectional base algorithms.

The algorithm's efficiency depends heavily on the strategy for detecting intersection between the two frontiers.

• Alternating Step: Execute one step from the forward frontier, then one from the backward frontier.
• Bidirectional A*: Use heuristic functions h_f(n) (to goal) and h_b(n) (to start) to guide both frontiers.
• Frontier Size Management: Dynamically prioritize expanding the search from the smaller frontier to balance effort. The search terminates when a node is selected for expansion that is already present in the other search's closed set.

While it dramatically reduces the number of nodes expanded, bidirectional search typically doubles the memory overhead compared to a unidirectional search, as it must maintain two open lists, two closed sets, and the associated search trees. The trade-off is favorable when the exponential reduction in node expansion outweighs the linear increase in per-node storage, which is common in large state spaces. It is less beneficial in memory-constrained environments.