Greedy Algorithmus
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.