Gieriger Algorithmus

Gierige Algorithmen bestimmen die minimale Anzahl von Münzen, die bei Änderungen vorgenommen werden sollen. Dies sind die Schritte, die die meisten Menschen unternehmen würden, um einen gierigen Algorithmus zu emulieren, um 36 Cent nur mit Münzen mit Werten {1, 5, 10, 20} darzustellen. Die Münze des höchsten Werts, weniger als die verbleibende schuldete Veränderung, ist das lokale Optimum. (Im Allgemeinen die Wechselproblem erfordert Dynamische Programmierung eine optimale Lösung zu finden; Die meisten Währungssysteme sind jedoch spezielle Fälle, in denen die gierige Strategie eine optimale Lösung findet.)

A Gieriger Algorithmus ist jeder Algorithmus Das folgt der Problemlösung Heuristik die lokal optimale Wahl in jeder Phase zu treffen.^[1] Bei vielen Problemen führt eine gierige Strategie nicht zu einer optimalen Lösung, aber eine gierige Heuristik kann lokal optimale Lösungen liefern, die eine global optimale Lösung in angemessener Zeit annähern.

Zum Beispiel eine gierige Strategie für die Problem mit reisenden Verkäufern (Das ist von hoher Rechenkomplexität) ist die folgende Heuristik: "Besuchen Sie bei jedem Schritt der Reise die nächste nicht besuchte Stadt." Diese Heuristik beabsichtigt nicht, die beste Lösung zu finden, aber sie endet in einer angemessenen Anzahl von Schritten. Die Suche nach einer optimalen Lösung für ein solches komplexes Problem erfordert typischerweise unangemessen viele Schritte. In der mathematischen Optimierung lösen gierige Algorithmen kombinatorische Probleme mit den Eigenschaften von optimal Matroiden und geben Optimierungsproblemen mit der submodularen Struktur Konstant-Faktor-Näherungen.

Einzelheiten

Gierige Algorithmen produzieren gute Lösungen für einige Mathematische Probleme, aber nicht an anderen. Die meisten Probleme, für die sie arbeiten, werden zwei Eigenschaften haben:

Greedy Choice -Eigenschaft

Wir können die Wahl im Moment treffen und dann die Unterprobleme lösen, die später entstehen. Die Wahl eines gierigen Algorithmus kann von bisher getroffenen Entscheidungen abhängen, jedoch nicht von zukünftigen Entscheidungen oder allen Lösungen für das Unterproblem. Es trifft iterativ eine gierige Wahl nach dem anderen und reduziert jedes gegebene Problem in eine kleinere. Mit anderen Worten, ein gieriger Algorithmus überprüft nie seine Entscheidungen. Dies ist der Hauptunterschied zu Dynamische Programmierung, was erschöpfend ist und die Lösung garantiert findet. Nach jeder Phase trifft die dynamische Programmierung Entscheidungen auf der Grundlage aller in der vorherigen Phase getroffenen Entscheidungen und kann den algorithmischen Pfad der vorherigen Stufe zur Lösung überdenken.

Optimale Unterstruktur

"Ein Problemausstellungen optimale Unterstruktur Wenn eine optimale Lösung für das Problem optimale Lösungen für die Unterprobleme enthält. "^[2]

Fälle von Scheitern

Beispiele dafür, wie ein gieriger Algorithmus möglicherweise die optimale Lösung nicht erreicht.

Ausgehend von A findet ein gieriger Algorithmus, der versucht, das Maximum durch die Befolgung der größten Steigung zu finden, das lokale Maximum bei "M", das sich auf das globale Maximum bei "M" nicht bewusst ist.

Um die größte Summe zu erreichen, wählt der gierige Algorithmus bei jedem Schritt die optimale sofortige Wahl, sodass er im zweiten Schritt 12 anstelle von 3 auswählt und nicht die beste Lösung erreicht, die 99 enthält.

Gierige Algorithmen erzeugen für viele andere Probleme nicht die optimale Lösung und können sogar die produzieren Einzigartig schlechtestes Lösung. Ein Beispiel ist das Problem mit reisenden Verkäufern oben erwähnt: Für jede Anzahl von Städten gibt es eine Zuordnung von Entfernungen zwischen den Städten, für die die Heuristik der nächsten Nachbarn die einzigartige schlimmste Tour erzeugt.^[3] Für andere mögliche Beispiele siehe Horizontffekt.

Typen

Gierige Algorithmen können als "kurzsichtig" und auch als "nicht reconabierbar" charakterisiert werden. Sie sind ideal nur für Probleme, die eine „optimale Unterstruktur“ haben. Trotzdem sind für viele einfache Probleme die am besten geeigneten Algorithmen gierig. Es ist jedoch wichtig zu beachten, dass der gierige Algorithmus als Selektionsalgorithmus verwendet werden kann, um Optionen innerhalb einer Suche oder ein Zweig-und-gebundener Algorithmus zu priorisieren. Es gibt einige Variationen des gierigen Algorithmus:

• Reine gierige Algorithmen
• Orthogonale gierige Algorithmen
• Entspannte gierige Algorithmen

Theorie

Gierige Algorithmen haben eine lange Geschichte des Studiums in Kombinatorische Optimierung und Theoretische Informatik. Es ist bekannt, dass gierige Heuristiken suboptimale Ergebnisse zu vielen Problemen erzielen.^[4] Und so natürliche Fragen sind:

• Für welche Probleme funktionieren gierige Algorithmen optimal?
• Für welche Probleme garantieren gierige Algorithmen eine ungefähr optimale Lösung?
• Für welche Probleme sind der gierige Algorithmus garantiert nicht eine optimale Lösung erzeugen?

Eine große Anzahl von Literatur gibt es, um diese Fragen für allgemeine Klassen von Problemen zu beantworten, wie z. Matroidensowie für spezifische Probleme wie z. Deckung festlegen.

Matroiden

A Matroid ist eine mathematische Struktur, die den Begriff von verallgemeinert hat lineare Unabhängigkeit aus Vektorräume zu willkürlichen Sets. Wenn ein Optimierungsproblem die Struktur einer Matroid hat, löst der entsprechende gierige Algorithmus ihn optimal.^[5]

Submodularfunktionen

Eine Funktion ${\ displayStyle f}$ definiert auf Teilmengen eines Satzes ${\ displayStyle \ Omega}$ wird genannt submodular Wenn für jeden ${\ displayStyle S, t \ subseteq \ Omega}$ wir haben das ${\ displayStyle f (s)+f (t) \ geq f (s \ cup t)+f (s \ cap t)}$.

Angenommen, man möchte einen Satz finden ${\ displayStyle S}$ was maximiert ${\ displayStyle f}$. Der gierige Algorithmus, der einen Satz aufbaut ${\ displayStyle S}$ durch inkrementelles Hinzufügen des Elements, das zunimmt ${\ displayStyle f}$ am meisten bei jedem Schritt produziert als Ausgabe einen Satz, der zumindest ist ${\ displayStyle (1-1/e) \ max _ {x \ subseteq \ omega} f (x)}$.^[6] Das heißt, Giery spielt innerhalb eines konstanten Faktors von ${\ displayStyle (1-1/e) \ ca. 0,63}$ So gut wie die optimale Lösung.

Ähnliche Garantien sind nachweislich, wenn zusätzliche Einschränkungen wie Kardinalitätsbeschränkungen,^[7] werden dem Ausgang auferlegt, obwohl oft geringfügige Abweichungen des gierigen Algorithmus erforderlich sind. Sehen ^[8] Für einen Überblick.

Andere Probleme mit Garantien

Andere Probleme, für die der gierige Algorithmus eine starke Garantie liefert, aber keine optimale Lösung, umfassen

• Deckung festlegen
• Das Steiner Baumproblem
• Lastverteilung^[9]
• Unabhängiger Satz

Viele dieser Probleme haben die unteren Grenzen; d.h. der gierige Algorithmus funktioniert im schlimmsten Fall nicht besser als die Garantie.

Anwendungen

Gierige Algorithmen finden in der Regel (aber nicht immer) die global optimale Lösung nicht, da sie normalerweise nicht alle Daten ausführlich arbeiten. Sie können zu früh für bestimmte Entscheidungen verpflichtet und verhindern, dass sie später die beste Gesamtlösung finden. Zum Beispiel alle bekannt gierige Färbung Algorithmen für die Graph Färbungsproblem und alle anderen NP-Complete Probleme finden nicht konsequent optimale Lösungen. Trotzdem sind sie nützlich, weil sie sich schnell überlegen und oft das Optimum gute Annäherungen geben.

Wenn nachweislich ein gieriger Algorithmus nachweislich das globale Optimum für eine bestimmte Problemklasse liefert, wird er typischerweise zur Methode der Wahl, da er schneller als andere Optimierungsmethoden wie ist Dynamische Programmierung. Beispiele für solche gierigen Algorithmen sind Kruskals Algorithmus und Prims Algorithmus zur Findung Mindestüberschreitende Bäume und der Algorithmus zur Optimumfindung Huffman -Bäume.

Gierige Algorithmen erscheinen im Netzwerk Routing auch. Mit gierigem Routing wird eine Nachricht an den benachbarten Knoten weitergeleitet, der dem Ziel "am nächsten" ist. Der Begriff des Standorts eines Knotens (und damit der "Nähe") kann durch seinen physischen Standort wie in bestimmt werden Geografisches Routing benutzt von Ad -hoc -Netzwerke. Die Lage kann auch ein völlig künstliches Konstrukt sein wie in kleines Weltrouting und verteilte Hash -Tabelle.

Beispiele

• Das Aktivitätsauswahlproblem ist charakteristisch für diese Klasse von Problemen, bei denen das Ziel darin besteht, die maximale Anzahl von Aktivitäten auszuwählen, die nicht miteinander in Konflikt geraten.
• In dem Macintosh Computer Spiel Kristallquest Ziel ist es, Kristalle auf eine ähnliche Weise wie die zu sammeln Problem mit reisenden Verkäufern. Das Spiel hat einen Demo -Modus, in dem das Spiel einen gierigen Algorithmus verwendet, um zu jedem Kristall zu gehen. Das künstliche Intelligenz berücksichtigt keine Hindernisse, so dass der Demo -Modus häufig schnell endet.
• Das passende Verfolgung ist ein Beispiel für einen gierigen Algorithmus, der auf die Signalannäherung angewendet wird.
• Ein gieriger Algorithmus findet die optimale Lösung für Malfattis Problem drei disjunkte Kreise innerhalb eines bestimmten Dreiecks zu finden, die die Gesamtfläche der Kreise maximieren; Es wird vermutet, dass der gleiche gierige Algorithmus für eine beliebige Anzahl von Kreisen optimal ist.
• Ein gieriger Algorithmus wird verwendet, um einen Huffman -Baum während zu konstruieren Huffman -Codierung wo es eine optimale Lösung findet.
• Im EntscheidungsbaumlernenEs werden häufig gierige Algorithmen verwendet, sie werden jedoch nicht garantiert die optimale Lösung finden.
  • Ein beliebter solcher Algorithmus ist der ID3 -Algorithmus Für Entscheidungsbaumkonstruktion.
• Dijkstra -Algorithmus und die verwandten Ein* Suchalgorithmus sind nachweislich optimale gierige Algorithmen für grafische Suche und kürzester Weg finden.
  • Eine* Suche ist bedingt optimal und erfordert eine "zulässige Heuristik"Das wird die Pfadkosten nicht überschätzen.
• Kruskals Algorithmus und Prims Algorithmus sind gierige Algorithmen zum Konstruktion Mindestüberschreitende Bäume von einem gegebenen verbundenes Diagramm. Sie finden immer eine optimale Lösung, die im Allgemeinen möglicherweise nicht einzigartig ist.

Siehe auch

Verweise

Quellen

Externe Links

• "Gieriger Algorithmus", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Geschenk, Noah. "Python Greedy Coin Beispiel".