Algorithmen und Datenstrukturen · Senior · Frage 3 von 75
Wie unterscheidet sich A* von Dijkstras Algorithmus?
- 1Er ergänzt eine Schätzung der verbleibenden Distanz
- 2Er sucht vom Ziel zurück zum Start
- 3Er ignoriert Kantengewichte und nutzt die BFS-Reihenfolge
Antwort zeigen
Richtige Antwort: Er ergänzt eine Schätzung der verbleibenden Distanz
Erklärung
A* ordnet Knoten nach g + h: den bekannten Kosten plus einer Schätzung bis zum Ziel, etwa die Luftlinie auf einer Karte. Überschätzt h nie (zulässig), bleibt der Weg optimal, und es werden viel weniger Knoten erkundet.