Wegfindungs-Algorithmen
Der Dijkstra-Algorithmus und A* finden beide kürzeste Wege, erkunden dabei aber sehr unterschiedlich. Dieser Visualisierer zeichnet die Suche, während sie abläuft, sodass Sie sehen, wie A* geradewegs auf das Ziel zusteuert, während Dijkstra sich in alle Richtungen ausbreitet.
So benutzt du diese Simulation
- Wählen Sie zwischen A*, Dijkstra und Breitensuche
- Zeichnen Sie Wände und legen Sie Start und Ziel fest
- Stellen Sie die Animationsgeschwindigkeit ein
Worauf du achten solltest
- Dijkstra breitet sich in einem gleichmäßigen Kreis aus, A* streckt sich zum Ziel
- Beide finden einen Weg gleicher Länge, doch A* prüft weit weniger Felder
- Wände, die einen Umweg erzwingen, lassen beide Algorithmen einander deutlich ähnlicher werden
Die Physik dahinter
Der Dijkstra-Algorithmus expandiert die Knoten nach ihrem Abstand vom Start, was den kürzesten Weg garantiert, aber sehr viel belangloses Gebiet absucht. A* fügt eine heuristische Schätzung der Restentfernung hinzu, die die Suche zum Ziel lenkt. Solange diese Heuristik nie überschätzt, garantiert A* weiterhin den kürzesten Weg und besucht dabei weit weniger Knoten.