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)

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Blinde Suche — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Uninformierte Suche — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Informierter Suchalgorithmus — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Suchalgorithmen — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Suchalgorithmus — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Suchstrategie — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Suchterm — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Uninformierter Suchalgorithmus — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • Suchverfahren — Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache… …   Deutsch Wikipedia

  • IP-TV — Mit IPTV (Internet Protocol Television; deutsch: Internet Protokoll Fernsehen) wird die digitale Übertragung von breitbandigen Anwendungen, wie Fernsehprogrammen und Filmen, über ein digitales Datennetz bezeichnet. Hierzu wird das auch dem… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”