Switching from Bidirectional to Unidirectional Search

Hermann Kaindl, Gerhard Kainz, Roland Steiner, Andreas Auer, Klaus RaddaIJCAI 1999

Bidirectional search, which explores a state space from both the start and goal states simultaneously, is a powerful technique for finding initial solutions quickly. By "meeting in the middle," it often avoids the exponential growth of search frontiers encountered in unidirectional search. However, a significant hurdle remains: proving that the found solution is optimal. This paper, originally presented at IJCAI-97, addresses the high computational cost of the termination condition in bidirectional search by proposing a novel "switching" strategy.

The Termination Bottleneck

In traditional "front-to-end" bidirectional search, finding a path does not signal the end of the algorithm. To guarantee optimality, the search must continue until it can be proven that no shorter path exists. This often requires expanding a vast number of additional nodes, sometimes negating the initial speed advantages of the bidirectional approach. The authors argue that the primary challenge is not the act of meeting in the middle, but the excessive effort required to satisfy the termination condition.

A 4-city TSP graph with edge weights used to demonstrate search algorithms.

The Switching Strategy

To mitigate this, the authors introduce a family of algorithms that pivot from bidirectional to unidirectional search at a critical juncture.

  1. Switch-A*: This algorithm proceeds with a standard bidirectional search until the frontiers first meet. At this point, it evaluates both search frontiers and identifies the one with the higher minimum $f$-value—the "stronger" frontier that has progressed further into high-cost regions. The algorithm then abandons the bidirectional search and completes the task using a unidirectional search from this stronger frontier.
  2. Max-Switch-A*: This variant incorporates the "Max method" to dynamically update heuristic values, enhancing pruning efficiency.
  3. Switch-DFBB-Trans: For memory-intensive problems, this version switches to a Depth-First Branch-and-Bound (DFBB) search with a transposition table after the initial meeting. The first solution found provides a tight upper bound, allowing DFBB to prune the remaining search space effectively.
Search tree for the TSP problem showing the meeting of search fronts and associated f-values.

TSP-Specific Optimizations

For the Traveling Salesman Problem (TSP), the researchers developed "complementary nodes." In symmetric TSP, forward and backward searches often duplicate work. By representing a partial tour and its complement in a single node, the algorithm can recognize meetings much earlier, effectively doubling the utility of stored data.

Experimental Evaluation

The proposed methods were tested on classic benchmarks, including the 15-Puzzle and Euclidean TSP, using hardware typical for the late 90s.

  • 15-Puzzle: Max-Switch-A* outperformed standard A and bidirectional BS, expanding only 62.1% of the nodes required by BS. It successfully solved 79 out of 100 instances within memory limits, a significant improvement over the 34 solved by standard A.
  • TSP: Switch-DFBB-Trans proved to be the fastest method. Although it generated more nodes than A*, its lower overhead per node—due to avoiding complex priority queue maintenance—resulted in superior overall running times.

Conclusion

The "switching" approach provides a robust solution to the termination problem in bidirectional search. By simplifying the search logic once an initial solution is found, these algorithms significantly reduce the overhead required to prove optimality. While memory constraints remain a limiting factor, the strategy demonstrates a clear path forward for improving heuristic search efficiency across diverse problem domains.

Summary updated

BibTeX
@inproceedings{kaindl1999switching,
  author = {Hermann Kaindl and Gerhard Kainz and Roland Steiner and Andreas Auer and Klaus Radda},
  title = {{Switching from Bidirectional to Unidirectional Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure