Kurs:Algorithmen und Datenstrukturen/Vorlesung/Greedyalgorithmen

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Greedyalgorithmus[Bearbeiten]

Auf dieser Seite wird der Greedyalgorithmus behandelt.

Greedy bedeutet "gierig". Der Algorithmus erfolgt nach dem Prinzip, dass versucht wird mit jedem Teilschritt so viel wie möglich zu erreichen. Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie immer denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.

Lokales Optimum[Bearbeiten]

Der Greedy Algorithmus berechnet in jedem Schritt das lokale Optimum, dabei kann jedoch das globale Optimum verfehlt werden.

Jedoch entspricht in vielen Fällen das lokale Optimum auch dem globalem Optimum, bzw. es reicht ein lokales Optimum aus.

Problemklasse[Bearbeiten]

  1. Gegebene Menge von Eingabewerten
  2. Menge von Lösungen, die aus Eingabewerten aufgebaut sind
  3. Lösungen lassen sich schrittweise aus partiellen Lösungen, beginnend bei der leeren Lösung, durch Hinzunahme von Eingabewerten aufbauen. Alternativ: bei einer ganzen Menge beginnend schrittweise jeweils ein Element wegnehmen
  4. Bewertungsfunktion für partielle und vollständige Lösungen
  5. Gesucht wird die/eine optimale Lösung


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg