Du weißt nicht was Greedy-Algorithmen sind und was sie beispielsweise mit kürzesten Wegen zu tun haben? Dann bist du hier genau richtig!
Inhaltsübersicht
Greedy Algorithmus Definition
Greedy-Algorithmen finden oft schnell eine Lösung, während andere Algorithmen kein Ergebnis in endlicher Zeit liefern können.
Häufig handelt es sich bei der, durch einen Greedy-Algorithmus, gefundenen Lösung jedoch nicht um die optimale Lösung für das Problem. Das liegt an der Funktionsweise dieser Algorithmen. Es wird nämlich immer die aktuell beste Entscheidung getroffen, ohne auf Vorherige oder auf Auswirkungen dieser Wahl zu achten.
Zu den Greedy, also zu den gierigen Algorithmen, zählen beispielsweise der Algorithmus von Prim , der Algorithmus von Kruskal und der Dijkstra Algorithmus .
Beispiel für ein Greedy Verfahren
Schauen wir uns das genauer an einem kleinen Beispiel an. Dir wird folgender Graph vorgelegt:
Deine Aufgabe ist es den günstigsten Weg von Knoten A zu F zu finden.
Wie gehst du vor? Klar! Du erkennst, dass es 2 Wege gibt und wählst den, der insgesamt die geringsten Kosten hat. So ist es dir möglich, mit Kosten von 75 von A zu F zu gelangen. Doch was würde ein simpler Greedy-Algorithmus tun?
Beginnen wir bei Knoten A. Der Greedy-Algorithmus hat jetzt die Aufgabe, die günstigste Teillösung zu wählen. Er sieht also, dass der Weg von A nach B um einiges besser ist als der von A nach C und legt somit fest, dass dies der bevorzugte Weg ist.
Da es jetzt keine weiteren Auswahlmöglichkeiten mehr gibt, wird also ein Weg mit Gesamtkosten von 351 dem Weg mit Kosten von 75 vorgezogen, nur weil der allererste Schritt günstiger ist. Daran kannst du gut erkennen, warum Greedy-Algorithmen oft nicht die optimale Lösung liefern.
Doch warum solltest du sie dann verwenden? Stelle dir vor, es gäbe nicht nur 2 sondern eine sehr große Anzahl an Möglichkeiten.
Ein Greedy-Algorithmus muss den Graphen nur durchlaufen und stets die günstigste Möglichkeit wählen, während ein normaler Algorithmus jede einzelne Möglichkeit testen müsste. Da dies oft nicht in endlicher Zeit möglich ist, sind Greedy-Algorithmen essenziell wichtig für viele Probleme.
Super, du weißt jetzt was Greedy-Algorithmen sind und wozu diese verwendet werden. Außerdem hast du gelernt, warum sie zwar eine schnelle, aber nicht unbedingt optimale Lösung liefern.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
Greedy Algorithmus — häufigste Fragen
(ausklappen)
Greedy Algorithmus — häufigste Fragen
(ausklappen)-
Was ist bei Greedy-Algorithmen mit „günstigster Teillösung“ gemeint?Mit „günstigster Teillösung“ ist bei Greedy-Algorithmen die im aktuellen Schritt billigste Erweiterung der bisherigen Lösung gemeint, zum Beispiel die Kante mit dem kleinsten Gewicht von einem Knoten aus. Man bewertet dabei nur diese unmittelbare Wahl und nicht die späteren Gesamtkosten des ganzen Wegs.
-
Woran erkennt man, ob ein Greedy-Ansatz für eine Aufgabe sinnvoll ist?Einen Greedy-Ansatz erkennt man als sinnvoll, wenn vor allem schnell irgendeine gute Lösung gebraucht wird und das Durchprobieren aller Möglichkeiten zu aufwendig wäre. Wenn dagegen eine sicher optimale Lösung zwingend nötig ist, ist ein einfacher Greedy-Ansatz oft ungeeignet, weil lokale Entscheidungen die Gesamtlösung deutlich verschlechtern können.
-
Warum führt bei Greedy-Algorithmen die lokal beste Wahl oft nicht zum global besten Ergebnis?Die lokal beste Wahl führt bei Greedy-Algorithmen oft nicht zum global besten Ergebnis, weil eine frühe Entscheidung spätere Optionen einschränkt und man dadurch in einem ungünstigen Teil des Graphen landet. In einem Beispielgraphen kann die erste billigere Kante dazu führen, dass am Ende ein deutlich teurerer Weg entsteht.
-
Wann liefert der Dijkstra-Algorithmus den kürzesten Weg?Der Dijkstra-Algorithmus liefert den kürzesten Weg, wenn alle Kantenkosten im Graphen nicht negativ sind. Dann ist die einmal als „am günstigsten erreicht“ festgelegte Distanz zu einem Knoten tatsächlich endgültig, sodass der Dijkstra-Algorithmus die kürzesten Wege von der Startquelle zu allen erreichbaren Knoten korrekt bestimmt.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Algorithmen verstehen
Der Greedy-Algorithmus gehört zum Themenfeld der Algorithmen und ist ein typisches Beispiel für schrittweise Entscheidungen in der Informatik. Wer sich mit Algorithmen beschäftigt, vergleicht verschiedene Lösungswege und prüft, wie schnell und wie zuverlässig sie ein Problem lösen. So wird klar, warum manche Verfahren sehr effizient arbeiten, aber nicht immer die beste Gesamtlösung liefern. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.
