Kurs:Algorithmen und Datenstrukturen/Vorlesung/Greedyalgorithmen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Greedyalgorithmus

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

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

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