Bidirektionale Suche

Grundidee und Einsatz

Die bidirektionale Suche ist ein Suchverfahren der Informatik und gehört zu den uninformierten Suchverfahren. Solche Verfahren untersuchen Teile eines Graphen, um bestimmte Eigenschaften zu finden, zum Beispiel den kürzesten Weg zwischen zwei gegebenen Knoten, also einen kürzesten Pfad.

Bei der bidirektionalen Suche starten zwei Suchvorgänge gleichzeitig: einer am Startknoten und einer am Zielknoten. Die beiden Suchen laufen in entgegengesetzte Richtungen. Das Verfahren endet, wenn sich die beiden erzeugten Teilgraphen treffen oder kreuzen. Dann kann daraus der gesuchte Zusammenhang zwischen den beiden Knoten bestimmt werden.

Ziel der Methode ist es, die Komplexität der Suche zu verringern. Dem stehen aber zusätzliche Schwierigkeiten gegenüber: Es muss ständig geprüft werden, ob sich die beiden Teilgraphen bereits getroffen haben. Außerdem kann es schwierig sein, die zweite Suche rückwärts auszuführen. Damit wirklich Zeit gespart wird, müssen beide Suchvorgänge parallel implementiert werden. Deshalb ist die bidirektionale Suche nur selten und nur unter bestimmten Bedingungen dem A*-Algorithmus vorzuziehen, etwa wenn keine geeignete Heuristik vorhanden ist.