Bidirectional search

from Wikipedia, the free encyclopedia

In computer science, bidirectional search is one of the search processes , more specifically one of the uninformed search processes. Like the A * algorithm and the Dijkstra algorithm, such a method determines the part of a graph that has certain properties, such as the shortest path between two given nodes ( shortest path ).

In this approach, two searches are started simultaneously, one on each of the two given nodes . The search processes are directed in opposite directions, the process is completed when the two subgraphs cross.

The bidirectional search is based on the desire to reduce complexity . On the other hand, there is an increased effort due to the check for the clash of the subgraphs, and running the second search backwards can also make implementation more difficult. And to save time, the two processes must be implemented in parallel . For this reason, the bidirectional method is seldom and is preferable to the A * algorithm under certain conditions, such as the lack of a suitable heuristic .

swell

  • Nicholson, TAJ: Finding the shortest route between two points in a network , The Computer Journal, Vol. 9, No. 3, pp. 275-280, 1966.
  • Dennis de Champeaux, Lenie Sint: An Improved Bi-directional Heuristic Search Algorithm , Journal ACM, Volume 24, No. 2, 1977 May, pp. 177-191.
  • Dennis de Champeaux: Bi-Directional Heuristic Search Again , Journal ACM, Volume, No. 1, January 1983, pp. 22-32.
  • Ira Pohl: Bi-directional Search , in Machine Intelligence , No. 6, eds. Meltzer and Michie, Edinburgh University Press, 1971, pp. 127-140.
  • Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach , 2nd ed., Prentice Hall, 2002 (§3.4)