BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Greedy Algorithmus

Greedy Algorithmus

Enthält: Beispiele · Definition · Grafiken · Übungsfragen

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

Toggle
  • Warum ist ein Greedy Algorithmus wichtig?
  • Was versteht man unter einem Greedy Algorithmus?
    • Wann wird ein Greedy Algorithmus genutzt?
  • Übungsfragen
  • Ergebnisse

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.

Beispiel für einen Greedy Algorithmus
Die “BauAuf AG” vertreibt Baumaschinen an große Bauunternehmen und bietet auch einen Kundenservice zur Wartung und Reparatur der Geräte an. Der Servicetechniker der “BauAuf AG” hat einen Anruf von einem wichtigen Kunden bekommen, dass eine seiner Maschinen kaputt gegangen sei und schnellstmöglich repariert werden muss, da sie für ein wichtiges Bauprojekt benötigt wird.

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:

Greedy Algorithmus
Greedy Algorithmus: Beispiel

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:

Greedy Algorithmus - Beispiel 2
Greedy Algorithmus – Beispiel 2

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.

Übungsfragen

 

#1. Was versteht man unter einem Greedy Algorithmus?

#2. Warum werden Greedy Algorithmen eingesetzt?

#3. “Ein Greedy Algorithmus betrachtet immer nur die aktuell beste Entscheidung, ohne vorherige Entscheidungspunkte oder deren Auswirkung in Betracht zu ziehen.” – diese Aussage ist:

#4. “Ein Greedy Algorithmus eignet sich besonders gut, um die optimale Lösung für ein Problem zu finden.” – Diese Aussage ist:

#5. “Der Greedy Algorithmus wurde nach seinem Erfinder Alexander Greedy benannt.” – diese Aussage ist:

Vorherige
Fertig

Ergebnisse

Share your score!
Tweet your score!
Share to other

Könnte dich auch interessieren:

Dijkstra Algorithmus - Anwendungsbeispiel

Dijkstra Algorithmus

Der Dijkstra Algorithmus gehört zur Gruppe der Greedy Algorithmen. Er dient der Berechnung des kürzesten Pfades in einem Graphen von … weiterlesen >>

Prim Algorithmus - Anwendungsbeispiel: Finaler Graph

Prim Algorithmus

Der Prim Algorithmus wird genutzt, um den minimalen Spannbaum eines Graphen zu finden. Er kann in Graphen genutzt werden, die … weiterlesen >>

Kruskal Algorithmus - Anwendungsbeispiel: Gegebener Graph

Kruskal Algorithmus

Der Kruskal Algorithmus dient der Ermittlung des minimalen Spannbaums eines zusammenhängenden und gewichteten Graphen. Wir zeigen dir in diesem Kapitel, … weiterlesen >>

Bellman Ford Algorithmus - Anwendungsbeispiel: Gegebener Graph

Bellman Ford Algorithmus

Um den kürzesten Weg in einem gewichteten Graphen zu ermitteln, kann der Bellman Ford Algorithmus eingesetzt werden. Auch bei Graphen, … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.