✏️ Übungen zu Kap. 8 · Brute Force gegen Dijkstra: Greedy
Fassung:
Freiwillig – such dir aus, was du üben willst.
Lückentext
Übung 1: Im Land Knobelien gibt es Münzen zu 1, 3 und 4 Cent. Für 6 Cent nimmt die Greedy-Strategie „immer die größte passende Münze“
Münzen. Es geht aber mit
Münzen.
Ausblick: A*
Navis nutzen oft eine Weiterentwicklung von Dijkstra, den Algorithmus A* („A-Stern“). Er legt nicht einfach den Knoten mit dem kleinsten Abstand vom Start fest, sondern den mit dem kleinsten Wert „Abstand vom Start + geschätzte Entfernung zum Ziel“. Als Schätzung nimmt man z. B. die Luftlinie. So sucht A* bevorzugt in Richtung Ziel und spart viel Arbeit. Eine solche Schätzung nennt man Heuristik.
Freitext
Übung 2: Warum ist die Luftlinie eine gute Schätzung für die Entfernung zum Ziel? Wann wäre sie schlecht?
💡 Zum Speichern deiner Antwort bitte einloggen.