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
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
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
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$
Weitere interessante Inhalte zum Thema
-
Produktionsplanung
Vielleicht ist für Sie auch das Thema Produktionsplanung (Produktionssysteme) aus unserem Online-Kurs Produktion interessant.
