Jetzt neu: Steuerrecht online lernen auf steuerkurse.de!
ZU DEN KURSEN!

Operations Research 1 - Greedy-Algorithmus

Kursangebot | Operations Research 1 | Greedy-Algorithmus

Operations Research 1

Greedy-Algorithmus

Inhaltsverzeichnis

Wir wollen im weiteren die sehr einfachen Greedy-Algorithmen (auch: gierige Algorithmen) betrachten. Bei Greedy-Algorithmen wird sukzessiv derjenige Folgezustand gewählt, der zum Zeitpunkt der Auswahl das beste Ergebnis verspricht. Der Greedy-Algorithmus betrachtet also die aktuelle Situation und wählt aus dieser die beste Lösung aus. Dabei werden voherige und spätere Entscheidungen nicht berücksichtigt. 

Der Vorteil beim Greedy-Algorithmus ist, dass er schnell durchzuführen und leicht zu implementieren ist. Der Nachteil allerdings, dass er nicht immer die optimale Lösung liefert. 

Merke

Hier klicken zum Ausklappen

Beim Greedy-Algorithmus gilt also: In jedem Verfahrensschritt wird diejenige Entscheidung getroffen, die im Moment am besten ist!

Zu den Greedy-Algorithmen gehören:

-der Dijkstra-Algorithmus

-der Kruskal-Algorithmus

-und der Prim-Algorithmus.

Beispiel: Greedy-Algorithmus

Beispiel

Hier klicken zum Ausklappen

Beim dem Kauf eines neuen Laptops für dein Studium willst du den Betrag von 749 € bar zahlen. Du willst hierbei so wenig Banknoten und Münzen wie möglich einsetzen. Du verfügst über die folgenden Banknoten und Münzen:

500  200  100  50  20  10  5  2  1


Dein Ziel ist es also die Bezahlung des Betrages von 799 € mit möglichst wenig Münzen und Banknoten durchzuführen. Hier kann der Greedy-Algorithmus wie folgt angewandt werden:

Methode

Hier klicken zum Ausklappen

Greedy-Algorithmus: Wähle jeweils immer die größte Banknote oder Münze unter dem Zielwert und ziehe sie von diesem ab. Verfahre solange bis der Zielwert gleich null ist.

Wir beginnen also mit dem Zielwert von 749 € und setzen die größe Banknote/Münze unter dem Zielwert an und ziehe diese ab:

$749 € - 500 € = 249 €$

$249 € - 200 € = 49 €$

$49 € - 20 € = 29 €$

$29 € - 20 € = 9 €$

$9 € - 5 € = 4 €$

$4 € - 2 € = 2 €$

$2 € - 2€ = 0$