Interaktive Demo
Bidirektionale Suche
Warum nur von einem Ende aus suchen? Die bidirektionale Suche führt den Dijkstra-Algorithmus gleichzeitig vom Start und vom Ziel aus. Im freien Gelände bedecken zwei kleine Kreise weniger Fläche als ein großer.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Türkis ist die Suche vom Start, Violett die Suche vom Ziel. Nach der ersten Berührung sucht sie noch kurz weiter: Die erste Berührung ist nicht immer die günstigste Verbindung.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front vom Start
- Besucht vom Start
- Front vom Ziel
- Besucht vom Ziel
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Ja
Hält erst an, wenn keine günstigere Verbindung zwischen den beiden Suchen mehr möglich ist.
Gewichtete Zellen
Ja
Beide Suchen verwenden die echten Kosten, einschließlich Schlamm.
Heuristik
Nein
Braucht keine, die zweite Suche gleicht einen Teil der fehlenden Richtung aus.
Beliebiger Winkel
Nein
Bewegt sich von Zelle zu Zelle, gerade oder diagonal.
Alle Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche | Nein | Nein | Nein | Nein |
| Dijkstra-Algorithmus | Ja | Ja | Nein | Nein |
| Bidirektionale Suche diese Seite | Ja | Ja | Nein | Nein |
| Gierige Bestensuche | Nein | Nein | Ja | Nein |
| A*-Suche | Mit Gewicht 1 und zulässiger Heuristik | Ja | Ja | Nein |
| Jump Point Search | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. Zwei Fronten
Jede Suche hat ihre eigenen Kosten und Vorgänger. In jedem Schritt erweitert die Seite, deren nächste Zelle günstiger ist, deshalb wachsen beide Fronten etwa gleich schnell.
2. Wann sie aufhören darf
Erreichen beide Suchen dieselbe Zelle, ergeben ihre Kosten zusammen einen vollständigen Weg, der beste wird gemerkt. Die Suche darf aufhören, sobald die nächsten Zellen beider Seiten zusammen mindestens so viel kosten wie dieser Weg. Erst dann ist keine günstigere Verbindung mehr möglich.
3. Die Ersparnis
Für einen Weg der Länge d bedeckt eine Suche eine Scheibe mit Radius d, zwei Suchen bedecken zwei Scheiben mit Radius d/2: auf einem Gitter die halbe Fläche, in schnell verzweigenden Graphen viel weniger. Routenplaner für Straßennetze bauen auf dieser Idee auf.