Brute Force gegen Dijkstra: Greedy
Brute Force gegen Dijkstra
Jetzt treten beide Verfahren im Gitter gegeneinander an.
Werkzeug: Brute Force und Dijkstra
Starte bei derselben Größe einmal Brute Force und einmal Dijkstra. Beide suchen den kürzesten Weg von links oben nach rechts unten.
Gesucht ist der kürzeste Weg von links oben nach rechts unten. Grün hinterlegt: ein kürzester Weg zum Vergleich; orange: der Weg, den der Rechner gerade untersucht; lila gestrichelt: der beste Weg, den er bisher gefunden hat. Nach spätestens 10 Sekunden bricht die Suche ab.
- Mögliche Wege insgesamt
- –
- Untersuchte Wege
- –
- Anteil untersucht
- –
- Benötigte Zeit
- –
- Bester bisher gefundener Weg
- –
- Länge des kürzesten Wegs
- –
- Zeit für alle Wege bei diesem Tempo
- –
- Dijkstra
- –
Aufgabe 1: Vergleiche die beiden Verfahren.
| Größe | Brute Force: untersuchte Wege | Dijkstra: festgelegte Knoten | Ergebnis gleich? |
|---|---|---|---|
| 4 × 4 | |||
| 6 × 6 | |||
| 10 × 10 | |||
| 12 × 12 | |||
Merke: Greedy-Algorithmus
Ein Greedy-Algorithmus („gierig“) trifft in jedem Schritt die Wahl, die im Moment am besten aussieht, und nimmt sie nie mehr zurück. Er schaut nicht voraus.
Dijkstra ist greedy: Er legt immer den Knoten mit dem kleinsten vorläufigen Abstand fest. Bei kürzesten Wegen (ohne negative Gewichte) führt das trotzdem garantiert zur optimalen Lösung – das ist eher die Ausnahme, wie wir noch sehen werden.
Du kennst schon einen Greedy-Algorithmus aus Klasse 9: Beim Lernen eines Entscheidungsbaums wählt man in jedem Schritt das Attribut, das die Daten im Moment am besten trennt.
Der Aufwand von Dijkstra wächst nur mit der Zahl der Knoten und Kanten – doppelt so viele Kreuzungen bedeuten grob doppelt bis viermal so viel Arbeit, nicht milliardenfach mehr.
Aufgabe 2: Was zeichnet einen Greedy-Algorithmus aus?