Über dieses Experiment
Routenplaner in Karten, Robotern und Videospielen lösen alle dasselbe Problem: den günstigsten Weg vom Start zum Ziel finden. In diesem Gitter kostet jeder Schritt auf eine Straße 1, ein Schritt in Schlamm 5, und Mauern können nicht überquert werden. Beobachte, wie sich drei klassische Algorithmen von S ausbreiten. Die Breitensuche zählt Schritte und ignoriert den Schlamm, Dijkstra untersucht immer als Nächstes die kostengünstigste Zelle, und A* schätzt zusätzlich die verbleibende Entfernung, damit es direkt auf das Ziel zusteuern kann. Gestalte eigene Karten und vergleiche, wie viel Arbeit jeder Algorithmus leistet.
Lernziele
- Eine Karte als Graph aus Zellen darstellen, die mit ihren Nachbarn verbunden sind, wobei jeder Schritt Kosten verursacht
- Beschreiben, wie die Breitensuche Ringe mit gleicher Schrittzahl durchläuft
- Erkläre, warum Dijkstra den günstigsten Pfad findet, wenn die Schritte unterschiedliche Kosten haben
- Erkläre, wie die A*-Heuristik die Anzahl der untersuchten Zellen verringert, ohne den besten Pfad zu verlieren
- Vergleiche die Algorithmen anhand der Kosten des gefundenen Pfads und des erforderlichen Aufwands
Anleitung
- 1Wähle BFS aus und drücke auf „Suchen“. Führt der gefundene Pfad durch den Schlamm? Lies die Kosten in der Tabelle ab.
- 2Wähle Dijkstra aus und suche erneut. Vergleiche den Pfad und seine Kosten mit BFS.
- 3Wähle A* aus. Sind die Pfadkosten dieselben wie bei Dijkstra? Wie viele Zellen weniger wurden untersucht?
- 4Beobachte während der Suche die blaue Suchfront. Wie unterscheidet sich ihre Form bei Dijkstra und A*?
- 5Male eine Wand, um die Straße um den Schlamm herum zu sperren. Welcher Algorithmus ändert seinen Pfad und warum?
- 6Drücke auf „Karte leeren“ und ziehe S und G auseinander. Wie viele Zellen untersucht jeder Algorithmus, wenn es keine Hindernisse gibt?
Das Modell
Annahmen
- Es sind nur Bewegungen nach oben, unten, links und rechts möglich. Das Betreten eines Feldes kostet auf einer Straße 1 und im Schlamm 5; Wände können nicht betreten werden.
- Bei der Suche behandelt BFS jeden Schritt so, als würde er 1 kosten, und findet daher den Pfad mit den wenigsten Schritten. Die in der Tabelle angegebenen Kosten sind die tatsächlichen Kosten dieses Pfads, einschließlich des Schlamms.
- Wenn zwei Felder dieselbe Priorität haben, wird zuerst das Feld untersucht, das zuerst hinzugefügt wurde. Daher ergibt sich bei jeder Suche mit derselben Karte genau dieselbe Reihenfolge.
- Die Suche endet, sobald das Ziel aus der Frontier genommen wird. Dann stehen seine geringstmöglichen Kosten fest.
Im Unterricht ausprobieren
- Q1Warum kann BFS einen teureren Pfad als Dijkstra finden, obwohl er weniger Schritte umfasst?
- Q2Würden BFS und Dijkstra Pfade mit denselben Kosten finden, wenn jedes Feld eine Straße wäre? Warum?
- Q3Was würde mit A* passieren, wenn die Schätzung h zehnmal so groß wäre wie die Manhattan-Distanz?
- Q4Warum untersucht A* weniger Felder, wenn das Ziel in einem offenen Gebiet liegt, aber ungefähr so viele wie Dijkstra in einem Labyrinth?
- Q5Ein Navigationsgerät findet in weniger als einer Sekunde eine schnelle Route durch ein Land mit Millionen von Straßenkreuzungen. Welche Ideen aus diesem Labor machen das möglich?
Häufig gestellte Fragen
Welcher Algorithmus ist der beste?
Das hängt vom Problem ab. BFS ist einfach und korrekt, wenn jeder Schritt gleich viel kostet. Dijkstra kann mit unterschiedlichen Kosten umgehen. A* liefert dasselbe Ergebnis wie Dijkstra und untersucht dabei weniger Zellen, sofern eine gute Schätzung der Entfernung zum Ziel verfügbar ist.
Was ist die Front (Frontier)?
Die Grenze ist die Menge der Zellen, die erreicht, aber noch nicht untersucht wurden. Jeder Algorithmus nimmt jeweils eine Zelle von der Grenze; sie unterscheiden sich nur darin, nach welcher Regel die nächste Zelle ausgewählt wird.
Können diese Algorithmen mit negativen Kosten umgehen?
Dijkstra und A* setzen voraus, dass kein Schritt negative Kosten hat. Bei negativen Kosten könnte sich später herausstellen, dass eine zuvor festgelegte Zelle doch über eine günstigere Route erreicht werden kann. Dann ist ein anderer Algorithmus wie Bellman-Ford erforderlich.