Wegsuche im Labyrinth – BFS, DFS und A*
InformatikAlgorithmen und ProblemlösenAlter 17–18
Wird geladen …
Zum Starten anmeldenEin Gitter mit Wänden, einem Startfeld und einem Zielfeld. Die Lernenden wählen Breitensuche (BFS, mit Warteschlange), Tiefensuche (DFS, mit Stapel) oder A* und verfolgen jeden Schritt: Wartende Felder sind in der Reihenfolge nummeriert, in der sie entnommen werden, untersuchte Felder sind nach Entfernung eingefärbt, am Ende erscheint der gefundene Weg. Wände zeichnen oder löschen, Start und Ziel verschieben, neue Labyrinthe erzeugen und die untersuchten Felder sowie die Weglänge der Algorithmen vergleichen.
Lektion: Algorithmen zur Wegsuche im Gitter: Breitensuche (BFS), Tiefensuche (DFS) und A*
Was sie zeigt
Ein Labyrinth wird als Gitter aus Feldern modelliert; jeder Zug führt zu einem Nachbarfeld oben, unten, links oder rechts, und jeder Zug kostet gleich viel. Die Breitensuche hält wartende Felder in einer Warteschlange: Sie untersucht erst alle Felder im Abstand 1, dann im Abstand 2, und wenn sie das Ziel zum ersten Mal erreicht, hat sie einen kürzesten Weg. Die Tiefensuche nutzt einen Stapel und folgt einer Richtung, bis sie feststeckt, daher ist ihr Weg oft länger. A* ordnet Felder nach f = g + h, wobei h der Manhattan-Abstand zum Ziel ist.
So funktioniert es
Wählen Sie BFS, DFS oder A* und drücken Sie Schritt, um die nummerierten wartenden Felder zu verfolgen, oder Start für eine Animation. Vergleichen Sie nach jedem Lauf die Ergebnistabelle. Mit Wände zeichnen, Wände löschen, Start setzen und Ziel setzen ändern Sie das Gitter; oder wählen Sie einen Gittertyp und drücken Sie Neues Gitter.
Einstellbare Parameter
- Algorithmus BFS – Breitensuche, DFS – Tiefensuche, A* – mit Entfernungsschätzung
- Gittertyp Labyrinth mit Kreisen, Zufällige Hindernisse, Leeres Gitter
- Anzahl der Spalten 11–41 Felder
- Zusätzlich entfernte Wände (Labyrinth) 0–60 %
- Hindernisdichte 0–45 %
- Geschwindigkeit 1–100 Schritte/s
Fragen zum Erkunden
- Warum ist der von BFS gefundene Weg immer ein kürzester, der Weg von DFS aber oft nicht?
- Welcher Algorithmus untersucht im leeren Gitter die wenigsten Felder, und warum?
- Können Sie ein Labyrinth bauen, in dem DFS das Ziel nach weniger untersuchten Feldern erreicht als BFS?
