Gieriger Algorithmus - Greedy algorithm

Gierige Algorithmen bestimmen die Mindestanzahl von Münzen, die beim Wechselgeld ausgegeben werden müssen. Dies sind die Schritte, die die meisten Leute unternehmen würden, um einen gierigen Algorithmus zu emulieren, um 36 Cent darzustellen, indem nur Münzen mit den Werten {1, 5, 10, 20} verwendet werden. Die Münze mit dem höchsten Wert, weniger als das verbleibende geschuldete Wechselgeld, ist das lokale Optimum. (Im Allgemeinen erfordert das Problem des Wandels eine dynamische Programmierung , um eine optimale Lösung zu finden; die meisten Währungssysteme, einschließlich Euro und US-Dollar, sind jedoch Sonderfälle, in denen die gierige Strategie eine optimale Lösung findet.)

Ein Greedy-Algorithmus ist jeder Algorithmus , der der Problemlösungsheuristik folgt, um in jeder Stufe die lokal optimale Wahl zu treffen. Bei vielen Problemen erzeugt eine Greedy-Strategie keine optimale Lösung, aber eine Greedy-Heuristik kann lokal optimale Lösungen liefern, die sich in angemessener Zeit einer global optimalen Lösung annähern.

Eine gierige Strategie für das Problem des Handlungsreisenden (das eine hohe Rechenkomplexität hat) ist beispielsweise 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 vernünftigen Anzahl von Schritten; Das Finden einer optimalen Lösung für ein so komplexes Problem erfordert normalerweise unangemessen viele Schritte. Bei der mathematischen Optimierung lösen Greedy-Algorithmen kombinatorische Probleme mit den Eigenschaften von Matroiden optimal und geben Optimierungsproblemen mit der submodularen Struktur konstante Näherungen.

Besonderheiten

Im Allgemeinen haben gierige Algorithmen fünf Komponenten:

  1. Eine Kandidatenmenge, aus der eine Lösung erstellt wird
  2. Eine Auswahlfunktion, die den besten Kandidaten für die Lösung auswählt
  3. Eine Machbarkeitsfunktion, die verwendet wird, um zu bestimmen, ob ein Kandidat verwendet werden kann, um zu einer Lösung beizutragen
  4. Eine Zielfunktion, die einer Lösung oder einer Teillösung einen Wert zuweist, und
  5. Eine Lösungsfunktion, die anzeigt, wenn wir eine vollständige Lösung gefunden haben

Gierige Algorithmen liefern gute Lösungen für einige mathematische Probleme , aber nicht für andere. Die meisten Probleme, für die sie funktionieren, haben zwei Eigenschaften:

Gierige Wahl Eigentum
Wir können die Wahl treffen, die im Moment am besten erscheint, und dann die Teilprobleme lösen, die später auftreten. Die von einem gierigen Algorithmus getroffene Wahl kann von den bisher getroffenen Entscheidungen abhängen, aber nicht von zukünftigen Entscheidungen oder allen Lösungen des Teilproblems. Es trifft iterativ eine gierige Wahl nach der anderen und reduziert jedes gegebene Problem in ein kleineres. Mit anderen Worten, ein gieriger Algorithmus überdenkt seine Entscheidungen nie. Dies ist der Hauptunterschied zur dynamischen Programmierung , die erschöpfend ist und garantiert die Lösung findet. Nach jeder Phase trifft die dynamische Programmierung Entscheidungen basierend auf allen Entscheidungen, die in der vorherigen Phase getroffen wurden, und kann den algorithmischen Weg der vorherigen Phase zur Lösung überdenken.
Optimale Unterkonstruktion
"Ein Problem weist eine optimale Unterstruktur auf, wenn eine optimale Lösung des Problems optimale Lösungen der Teilprobleme enthält."

Fehlerfälle

Beispiele dafür, wie ein Greedy-Algorithmus die optimale Lösung nicht erreichen kann.
Ausgehend von A findet ein Greedy-Algorithmus, der versucht, das Maximum zu finden, indem er der größten Steigung folgt, das lokale Maximum bei "m", ohne das globale Maximum bei "M" zu beachten.
Um die größte Summe zu erreichen, wählt der Greedy-Algorithmus bei jedem Schritt die scheinbar optimale sofortige Wahl, also wählt er im zweiten Schritt 12 statt 3 und erreicht nicht die beste Lösung, die 99 enthält.

Greedy-Algorithmen liefern für viele andere Probleme nicht die optimale Lösung und können sogar die einzige schlechtestmögliche Lösung liefern . Ein Beispiel ist das oben erwähnte Travelling-Salesman-Problem : Für jede Anzahl von Städten gibt es eine Zuordnung von Entfernungen zwischen den Städten, für die die Nearest-Neighbour-Heuristik die eindeutig schlechtestmögliche Tour ergibt. Weitere mögliche Beispiele finden Sie unter Horizonteffekt .

Typen

Gierige Algorithmen können als „kurzsichtig“ und auch als „nicht wiederherstellbar“ bezeichnet werden. Sie eignen sich nur für Probleme, die einen „optimalen Unterbau“ haben. Trotzdem sind für viele einfache Probleme die am besten geeigneten Algorithmen gierig. Es ist jedoch wichtig zu beachten, dass der Greedy-Algorithmus als Auswahlalgorithmus verwendet werden kann, um Optionen innerhalb einer Suche oder eines Branch-and-Bound-Algorithmus zu priorisieren. Es gibt einige Variationen des Greedy-Algorithmus:

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

Theorie

Gierige Algorithmen haben eine lange Geschichte in der kombinatorischen Optimierung und der theoretischen Informatik . Gierige Heuristiken sind dafür bekannt, bei vielen Problemen suboptimale Ergebnisse zu erzielen, und daher sind natürliche Fragen:

  • Für welche Probleme funktionieren gierige Algorithmen optimal?
  • Für welche Probleme garantieren gierige Algorithmen eine annähernd optimale Lösung?
  • Für welche Probleme liefert der Greedy-Algorithmus garantiert keine optimale Lösung?

Es existiert eine große Menge an Literatur, die diese Fragen sowohl für allgemeine Problemklassen wie Matroide als auch für spezifische Probleme wie Set Cover beantwortet .

Matroiden

Ein Matroid ist eine mathematische Struktur, die den Begriff der linearen Unabhängigkeit von Vektorräumen auf beliebige Mengen verallgemeinert . Hat ein Optimierungsproblem die Struktur eines Matroids, wird es der entsprechende Greedy-Algorithmus optimal lösen.

Submodulare Funktionen

Eine Funktion, die auf Teilmengen einer Menge definiert ist, heißt submodular, wenn wir das für alle haben .

Angenommen, man möchte eine Menge finden, die maximiert . Der Greedy-Algorithmus, der eine Menge aufbaut, indem inkrementell das Element hinzugefügt wird, das bei jedem Schritt am stärksten zunimmt , erzeugt als Ausgabe eine Menge von mindestens . Das heißt, gierig arbeitet innerhalb eines konstanten Faktors von so gut wie die optimale Lösung.

Ähnliche Garantien sind nachweisbar, wenn der Ausgabe zusätzliche Beschränkungen, wie Kardinalitätsbeschränkungen, auferlegt werden, obwohl häufig geringfügige Variationen des Greedy-Algorithmus erforderlich sind. Siehe für eine Übersicht.

Andere Probleme mit Garantien

Andere Probleme, für die der Greedy-Algorithmus eine starke Garantie, aber keine optimale Lösung bietet, umfassen

Viele dieser Probleme haben übereinstimmende untere Schranken; dh der Greedy-Algorithmus schneidet im schlimmsten Fall nicht besser ab als die Garantie.

Anwendungen

Gierige Algorithmen finden typischerweise (aber nicht immer) die global optimale Lösung nicht, weil sie normalerweise nicht alle Daten erschöpfend verarbeiten. Sie können sich zu früh auf bestimmte Entscheidungen festlegen, was sie daran hindert, später die beste Gesamtlösung zu finden. Zum Beispiel finden alle bekannten Greedy-Coloring- Algorithmen für das Graph-Coloring-Problem und alle anderen NP-vollständigen Probleme nicht konsistent optimale Lösungen. Dennoch sind sie nützlich, weil sie schnell zu denken sind und oft gute Annäherungen an das Optimum liefern.

Wenn nachgewiesen werden kann, dass ein Greedy-Algorithmus das globale Optimum für eine gegebene Problemklasse liefert, wird er in der Regel zur Methode der Wahl, da er schneller ist als andere Optimierungsmethoden wie die dynamische Programmierung . Beispiele für solche gierigen Algorithmen sind Kruskals Algorithmus und Prim-Algorithmus für die Suche nach MST-Heuristik und der Algorithmus für die Suche nach optimalen Huffman Bäume .

Auch im Netzwerk- Routing tauchen gierige Algorithmen auf . Beim Greedy-Routing wird eine Nachricht an den Nachbarknoten weitergeleitet, der dem Ziel "am nächsten" liegt. Der Begriff des Standorts eines Knotens (und damit der "Nähe") kann durch seinen physischen Standort bestimmt werden, wie bei der geografischen Leitweglenkung, die von Ad-hoc-Netzwerken verwendet wird . Der Standort kann auch ein völlig künstliches Konstrukt sein, wie beim Small-World-Routing und der verteilten 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 kollidieren.
  • In dem Macintosh - Computer - Spiel Kristall Quest - das Ziel ist , zu sammeln Kristalle, in ähnlicher Weise wie das Reiseproblem . Das Spiel hat einen Demo-Modus, in dem das Spiel einen gierigen Algorithmus verwendet, um zu jedem Kristall zu gelangen. Die künstliche Intelligenz berücksichtigt keine Hindernisse, sodass der Demo-Modus oft schnell endet.
  • Die Anpassungsverfolgung ist ein Beispiel für einen Greedy-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 gegebenen Dreiecks zu finden, die die Gesamtfläche der Kreise maximieren; Es wird vermutet, dass derselbe Greedy-Algorithmus für eine beliebige Anzahl von Kreisen optimal ist.
  • Ein Greedy-Algorithmus wird verwendet, um während der Huffman-Codierung einen Huffman-Baum zu konstruieren, wo er eine optimale Lösung findet.
  • Beim Lernen von Entscheidungsbäumen werden häufig gierige Algorithmen verwendet, die jedoch nicht garantiert die optimale Lösung finden.
    • Ein beliebter solcher Algorithmus ist der ID3-Algorithmus zur Konstruktion von Entscheidungsbäumen.
  • Der Dijkstra-Algorithmus und der zugehörige A*-Suchalgorithmus sind nachweislich optimale Greedy-Algorithmen für die Graphensuche und die Suche nach dem kürzesten Weg .
    • Die A*-Suche ist bedingt optimal und erfordert eine " zulässige Heuristik ", die die Pfadkosten nicht überschätzt.
  • Kruskals Algorithmus und Prim-Algorithmus sind gierige Algorithmen für die Konstruktion von MST-Heuristik eines bestimmten zusammenhängenden Graphen . Sie finden immer eine optimale Lösung, die im Allgemeinen nicht eindeutig ist.

Siehe auch

Verweise

Quellen

Externe Links