Greedy-Algorithmen

Greedy-Algorithmen konstruieren eine Lösung inkrementell, indem sie wiederholt die im aktuellen Schritt am besten erscheinende Wahl treffen, und sind genau dann korrekt, wenn solche lokal optimalen Entscheidungen nachweislich zu einer global optimalen Lösung führen.

Definition

Ein Greedy-Algorithmus konstruiert eine Lösung durch eine Abfolge von Entscheidungen, wobei jede Entscheidung zur Optimierung eines lokalen Kriteriums getroffen wird und frühere Entscheidungen niemals revidiert werden; er ist nur dann korrekt, wenn die lokal optimalen Entscheidungen zu einem global optimalen Ergebnis führen.

Scope

Dieses Thema behandelt das Greedy-Paradigma: die Greedy-Choice-Eigenschaft und die optimale Teilstruktur, die es rechtfertigen, die Standard-Beweistechniken (Austauschargumente und der Matroid-Rahmen) sowie kanonische Greedy-Algorithmen, einschließlich Huffman-Codierung, minimale Spannbäume (Kruskal und Prim), Dijkstras kürzeste Wege und Intervallplanung. Es wird auch behandelt, wann Greedy-Strategien nur als Approximationsheuristiken und nicht als exakte Methoden dienen.

Core questions

• Was ist die Greedy-Choice-Eigenschaft und wie wird sie für ein gegebenes Problem bewiesen?
• Wie zeigt ein Austauschargument, dass eine Greedy-Wahl sicher ist?
• Welche Probleme weisen eine Matroidstruktur auf, die die Greedy-Optimalität garantiert?
• Wann ist eine Greedy-Methode nur eine Approximation und kein exakter Algorithmus?
• Wie vergleicht sich Greedy mit der dynamischen Programmierung für dasselbe Problem?

Key concepts

• Greedy-Choice-Eigenschaft
• optimale Teilstruktur
• Austauschargument
• Matroide
• Huffman-Codierung
• minimaler Spannbaum
• Intervallplanung
• fraktionaler Rucksack

Key theories

Greedy-Choice-Eigenschaft und Austauschargumente

Ein Problem lässt eine Greedy-Lösung zu, wenn eine global optimale Lösung immer so modifiziert werden kann, dass sie mit der ersten Greedy-Wahl übereinstimmt, ohne an Optimalität zu verlieren; Austauschargumente (oder 'Greedy bleibt vorne') formalisieren dies.

Matroide und Greedy-Optimalität

Wenn die zulässigen Lösungen die unabhängigen Mengen eines gewichteten Matroids bilden, findet der Greedy-Algorithmus immer eine unabhängige Menge mit maximalem Gewicht; dies vereinheitlicht Ergebnisse wie die Optimalität von Kruskals Algorithmus für minimale Spannbäume.

Clinical relevance

Greedy-Algorithmen treiben weit verbreitete Systeme an: Huffman-Codierung in Datenkompressionsformaten, Algorithmen für minimale Spannbäume im Netzwerkdesign, Dijkstras Algorithmus in Routing und Navigation sowie Greedy-Planungs- und Set-Cover-Heuristiken in Betriebssystemen und der Ressourcenallokation.

History

Greedy-Ansätze finden sich in klassischen Ergebnissen wie Kruskals (1956) und Prims (1957) Algorithmen für minimale Spannbäume, Huffmans (1952) optimalen Präfixcodes und Dijkstras (1959) Algorithmus für kürzeste Wege. Die matroidtheoretische Erklärung, wann Greedy-Methoden erfolgreich sind, wurde von Edmonds und anderen in den 1960er und 1970er Jahren entwickelt.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Warum funktioniert Greedy für den fraktionalen Rucksack, aber nicht für den 0/1-Rucksack?

Beim fraktionalen Rucksack können Gegenstände geteilt werden, sodass die Wahl des Gegenstands mit dem höchsten Wert pro Gewicht immer sicher und nachweislich optimal ist. Beim 0/1-Rucksack sind Gegenstände unteilbar, die Greedy-Wahl kann eine bessere Kombination ausschließen, und für ein exaktes Optimum ist dynamische Programmierung erforderlich.

Wie beweist man die Korrektheit eines Greedy-Algorithmus?

Die beiden Standardtechniken sind das Austauschargument, das jede optimale Lösung in die Greedy-Lösung umwandelt, ohne sie zu verschlechtern, und das 'Greedy bleibt vorne'-Argument, das zeigt, dass die Greedy-Teillösung in jedem Schritt mindestens so gut ist wie jede andere. Die Matroidtheorie liefert eine allgemeine hinreichende Bedingung.