Operations Research

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.

Greedy Algorithmen: schnelle, aber nicht immer optimale Lösungen
direkt ins Video springen
Greedy Algorithmen finden oft schnell eine Lösungen

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:

Beispiel für einen Greedy Algorithmus
direkt ins Video springen
Beispiel für einen Greedy Algorithmus: Günstigster Weg von A nach F

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.

Wahl der günstigsten Teillösung
direkt ins Video springen
Greedy Algorithmen liefern nicht immer die optimale Lösung

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.

Große Anzahl an Möglichkeiten beim Greedy Algorithmus
direkt ins Video springen
Greedy Algorithmus: Unendlich viele 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.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.