Interaktive Demo
Gierige Bestensuche
Die gierige Bestensuche (Greedy Best-First Search) macht immer bei der Zelle weiter, die dem Ziel am nächsten scheint. Wie weit sie schon gekommen ist, ignoriert sie, deshalb ist sie im freien Gelände schnell und vor Wänden kurzsichtig.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Zeichne eine Wand wie einen Becher zwischen Start und Ziel, offen zum Start: Die Suche läuft in den Becher hinein und findet erst dann den Weg drumherum.
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 (Open List)
- Besucht (Closed List)
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Nein
Sie schaut nur nach vorn, nie auf die bisherigen Kosten, deshalb können ihre Wege viel länger sein als nötig.
Gewichtete Zellen
Nein
Die Kosten ändern die Reihenfolge nicht, deshalb läuft sie mitten durch den Schlamm.
Heuristik
Ja
Nur die geschätzte Entfernung zum Ziel entscheidet.
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 | Ja | Ja | Nein | Nein |
| Gierige Bestensuche diese Seite | 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. Nur die Schätzung zählt
Die Priorität einer Zelle ist h, ihre geschätzte Entfernung zum Ziel. Solange nichts im Weg ist, läuft die Suche direkt zum Ziel und erweitert kaum mehr Zellen, als der Weg lang ist.
2. Von Hindernissen getäuscht
Hinter einer Wand sehen Zellen nah am Ziel am besten aus, auch wenn sie in eine Sackgasse führen. Die Suche füllt die Tasche, bevor sie den Weg drumherum probiert, und der gemeldete Weg behält den Umweg.
3. Die Schätzungen
Manhattan zählt gerade Schritte, Oktil erlaubt diagonale Schritte, Euklidisch ist die Luftlinie und Tschebyschow zählt einen diagonalen Schritt als 1. Bei der gierigen Suche ändert die Wahl die Form des Wegs, aber nicht, ob er optimal ist: Das ist er nie.