Ein Greedy Algorithmus ist eine Methode der Problemlösung, welche darauf ausgelegt ist, möglichst schnell eine Lösung zu finden. Diese muss nicht immer die optimale Lösung sein, da ein Greedy Algorithmus in jeder Entscheidungsstufe nur die aktuell beste Lösung berücksichtigt, ohne Beachtung vorheriger oder nachfolgender Entscheidungsstufen.
Du wirst in diesem Kapitel lernen, wie ein Greedy Algorithmus funktioniert und warum er wichtig ist. Anschließend stellen wir dir einige Übungsaufgaben zur Verfügung, mit denen du dein erworbenes Wissen testen kannst
Inhalt dieser Lektion
Warum ist ein Greedy Algorithmus wichtig?
In der betrieblichen Praxis, speziell im Operations Research, müssen eine Vielzahl von Optimierungsproblemen gelöst werden. Ein Greedy Algorithmus ist eine der Methoden, die zur Lösung solcher Probleme geeignet sind. Er wird vor allem dann eingesetzt, wenn es darum geht schnell eine gute Lösung für das vorliegende Problem zu finden. Dabei wird in Kauf genommen, dass diese Lösung nicht die optimale Lösung des Gesamtproblems darstellt.
Was versteht man unter einem Greedy Algorithmus?
Zur Gruppe der Greedy Algorithmen gehören Algorithmen, die “gierig” darauf sind eine Lösung zu finden. Das bedeutet, sie versuchen in möglichst kurzer Zeit eine geeignete Lösung für das betrachtete Problem zu finden. Die Suche nach einer optimalen Lösung für das Problem ist dabei zweitrangig.
Zu den Greedy Algorithmen gehören beispielsweise:
- der Prim Algorithmus
- der Kruskal Algorithmus
- der Dijkstra Algorithmus
Diese Algorithmen funktionieren nach einem ähnlichen Prinzip: Der Algorithmus trifft immer die aktuell beste Entscheidung. Auf vorhergegangene Entscheidungen oder die Auswirkungen dieser Entscheidung wird dabei nicht geachtet.
Der Servicetechniker soll am besten noch heute in die Stadt D kommen, um die nötigen Reparaturen vorzunehmen, damit die Maschine schnellstmöglich wieder einsatzbereit ist.
Die möglichen Fahrtrouten, um vom Firmenstandort der „BauAuf AG“ in Stadt A zum Kunden in Stadt D zu gelangen zeigt der folgende Graph:
Die Kantengewichte beschreiben hierbei die Fahrtstrecke in km zwischen den einzelnen Städten (Knoten). Da der Kundenauftrag sehr dringend ist, entscheidet sich der Servicetechniker, einen Greedy Algorithmus anzuwenden, um sein Problem der Auswahl einer Fahrstrecke schnellstmöglich zu lösen.
Der Greedy Algorithmus geht dabei so vor, dass an jeder Weggabelung die aktuell beste Entscheidung getroffen wird. Das bedeutet:
Am Knoten A stehen drei mögliche Wege zur Auswahl:
- A zu B mit einer Länge von 100 km
- A zu D mit einer Länge von 230 km
- A zu C mit einer Länge von 150 km
Die beste Entscheidung in diesem Moment ist also, die Strecke von A zu B zu wählen, da diese aktuell den kürzesten Weg aufweist. Im nächsten Schritt bleibt nur die Möglichkeit, den Weg von B zu D mit einer Länge von 200 km zu wählen. Durch die Anwendung des Greedy Algorithmus fährt der Techniker also eine Strecke von insgesamt 300 km, um von Stadt A nach Stadt D zu gelangen.
Die optimale Lösung wäre allerdings gewesen, er hätte zuerst den direkten Weg von A nach D gewählt, um so nur eine Strecke von 230 km fahren zu müssen. Der Greedy Algorithmus hat also zwar eine schnelle, aber nicht die optimale Lösung hervorgebracht.
Wann wird ein Greedy Algorithmus genutzt?
Der Vorteil eines Greedy Algorithmus liegt in seiner Schnelligkeit. Angenommen, unser Techniker hätte nicht nur 2, sondern 22 Wege zur Auswahl gehabt, die auch noch über verschiedene mehrere Städte führen könnten.
Der Graph zur Entscheidungsfindung würde dann so aussehen:
Um hieraus den optimalen Weg zu ermitteln, müssten alle 22 möglichen Lösungen zuerst durchgetestet werden, was einiges an Zeit kosten würde. Mit einem Greedy Algorithmus kann die benötigte Zeit verkürzt werden, da an jeder möglichen Verzweigung immer nur die aktuell beste Möglichkeit weiterverfolgt wird und die restlichen Möglichkeiten nicht weiter betrachtet werden.
Greedy Algorithmen einzusetzen ist also immer dann sinnvoll, wenn unter Zeitdruck eine Lösung für ein Problem mit vielen verschiedenen Lösungsmöglichkeiten gefunden werden muss.
