Switching from bidirectional to unidirectional search
Hermann Kaindl, Gerhard Kainz, Roland Steiner, Andreas Auer, Klaus Radda · 1999
Recently, we showed that for traditional bidirec-tional search with "front-to-end " evaluations, it is not the meeting of search fronts but the cost of proving the optimality of a solution that is prob-lematic. Using our improved understanding of the problem, we developed a new approach to improv-ing this kind of search: switching to unidirectional search after the search frontiers meet for the first time (with the first solution found). This new ap-proach shows improvements over previous bidirec-tional search approaches and (partly) also over the corresponding unidirectional search approaches in different domains. Together with a special-purpose improvement for the TSP, this approach showed better results than the standard search algorithms using the same knowledge. 1