Bidirektionale Suche

In der Informatik zählt die Bidirektionale Suche zu den Suchverfahren. Wie der A*-Algorithmus und der Dijkstra-Algorithmus ermittelt ein solches Verfahren den Teil eines Graphen der bestimmte Eigenschaften, wie kürzester Weg zwischen zwei gegebenen Knoten (Kürzester Pfad) aufweist.

Bei diesem Lösungsverfahren werden zwei Suchen simultan gestartet, jeweils eine an den beiden gegebenen Knoten. Die Suchvorgänge sind gegensätzlich gerichtet, das Verfahren ist abgeschlossen, wenn sich die zwei Teilgraphen kreuzen.

Der bidirektionalen Suche liegt der Wunsch nach Verringerung der Komplexität zu Grunde. Dem steht ein erhöhter Aufwand durch die Prüfung auf Aufeinandertreffen der Teilgraphen gegenüber, auch kann das Rückwärts laufen lassen der zweiten Suche die Realisierung erschweren. Und zur Erzielung einer Zeitersparnis müssen die beiden Vorgänge parallel implementiert werden. Daher ist das bidirektionale Verfahren nur selten und unter bestimmten Bedingung wie dem Fehlen einer geeigneten Heuristik dem A*-Algorithmus vorzuziehen.

Quellen

• Nicholson, T.A.J.: Finding the shortest route between two points in a network, The Computer Journal, Vol. 9, Nr. 3,S. 275-280, 1966.

• Dennis de Champeaux & Lenie Sint, An Improved Bi-directional Heuristic Search Algorithm, Journal ACM, Band 24, Nr. 2, 1977 Mai, S. 177-191.

• Dennis de Champeaux, Bi-Directional Heuristic Search Again, Journal ACM, Band, Nr 1, 1983 Januar, S. 22-32.

• Ira Pohl, Bi-directional Search, in Machine Intelligence, Nr. 6, eds. Meltzer und Michie, Edinburgh University Press, 1971, S. 127-140.

• Stuart Russell und Peter Norvig. Artificial Intelligence: A Modern Approach, 2nd ed., Prentice Hall, 2002 (§3.4)