Eyal Shlomo Shimony

Bidirectional heuristic search potentially decreases search effort in combinatorial search problems amenable to backward search. To date, bidirectional search has been limited to minimization or shortest path problems. This paper extends the notion of bidirectional heuristic search to (constrained) longest-path problems. We present a bidirectional heuristic search algorithm for longest simple path (LSP) in undirected graphs, and prove its correctness. We then suggest several refinements, as well as a generalization to other types of longest path problems, such as Coil-in-a-box (CIB). Empirical evaluation shows that, as with many forms of bidirectional search, sometimes unidirectional search wins, but for a sizable chunk of problem instances, bidirectional search performs better by expanding fewer nodes and achieves a shorter runtime despite the increased overhead per expansion.