Mit Beispielen erläuterte gierige Algorithmen

Was ist ein gieriger Algorithmus?

Möglicherweise haben Sie beim Durchsuchen einiger Artikel hier von vielen algorithmischen Entwurfstechniken gehört. Einige von ihnen sind:

  • Rohe Gewalt
  • Teilen und erobern
  • Gierige Programmierung
  • Dynamische Programmierung, um nur einige zu nennen. In diesem Artikel erfahren Sie, was ein gieriger Algorithmus ist und wie Sie mit dieser Technik viele Programmierprobleme lösen können, die ansonsten nicht trivial erscheinen.

Stellen Sie sich vor, Sie gehen wandern und Ihr Ziel ist es, den höchstmöglichen Gipfel zu erreichen. Sie haben die Karte bereits vor dem Start, aber auf der Karte werden Tausende von möglichen Pfaden angezeigt. Sie sind zu faul und haben einfach nicht die Zeit, jeden von ihnen zu bewerten. Scheiß auf die Karte! Sie haben mit einer einfachen Strategie angefangen zu wandern - seien Sie gierig und kurzsichtig. Nehmen Sie einfach Wege, die am meisten nach oben abfallen. Dies scheint eine gute Strategie zum Wandern zu sein. Aber ist es immer das Beste?

Nachdem die Reise beendet ist und Ihr ganzer Körper wund und müde ist, schauen Sie zum ersten Mal auf die Wanderkarte. Ach du lieber Gott! Es gibt einen schlammigen Fluss, den ich hätte überqueren sollen, anstatt weiter nach oben zu gehen. Dies bedeutet, dass ein gieriger Algorithmus die beste sofortige Wahl trifft und seine Wahl niemals überdenkt. In Bezug auf die Optimierung einer Lösung bedeutet dies einfach, dass die gierige Lösung versucht, lokale optimale Lösungen zu finden - die viele sein können - und möglicherweise eine globale optimale Lösung verpasst.

Formale Definition

Angenommen, Sie haben eine Zielfunktion, die an einem bestimmten Punkt optimiert (entweder maximiert oder minimiert) werden muss. Ein Greedy-Algorithmus trifft bei jedem Schritt gierige Entscheidungen, um sicherzustellen, dass die Zielfunktion optimiert wird. Der Greedy-Algorithmus hat nur einen Schuss, um die optimale Lösung zu berechnen, sodass er niemals zurückgeht und die Entscheidung umkehrt.

Gierige Algorithmen haben einige Vor- und Nachteile:

  • Es ist ziemlich einfach, einen Greedy-Algorithmus (oder sogar mehrere Greedy-Algorithmen) für ein Problem zu finden. Das Analysieren der Laufzeit für gierige Algorithmen ist im Allgemeinen viel einfacher als für andere Techniken (wie Teilen und Erobern). Für die Divide and Conquer-Technik ist nicht klar, ob die Technik schnell oder langsam ist. Dies liegt daran, dass mit jeder Rekursionsstufe die Größe kleiner wird und die Anzahl der Unterprobleme zunimmt.
  • Der schwierige Teil ist, dass man für gierige Algorithmen viel härter arbeiten muss, um Korrektheitsprobleme zu verstehen. Selbst mit dem richtigen Algorithmus ist es schwer zu beweisen, warum er korrekt ist. Zu beweisen, dass ein gieriger Algorithmus korrekt ist, ist eher eine Kunst als eine Wissenschaft. Es erfordert viel Kreativität. Normalerweise scheint es trivial zu sein, einen Algorithmus zu entwickeln, aber zu beweisen, dass er tatsächlich korrekt ist, ist ein ganz anderes Problem.

Intervallplanungsproblem

Lassen Sie uns auf ein interessantes Problem eingehen, das in fast jeder Branche oder in jedem Lebensbereich auftreten kann. Einige Fälle des Problems sind wie folgt:

  • Sie erhalten eine Reihe von N Vorlesungsplänen für einen einzelnen Tag an einer Universität. Der Zeitplan für eine bestimmte Vorlesung hat die Form (s Zeit, f Zeit), wobei s Zeit die Startzeit für diese Vorlesung darstellt und in ähnlicher Weise die f Zeit die Endzeit darstellt. Bei einer Liste von N Vorlesungsplänen müssen wir die maximale Anzahl von Vorlesungen auswählen, die während des Tages gehalten werden sollen, sodass sich   keine der Vorlesungen überschneiden, dh wenn die Vorlesungen Li und Lj in unserer Auswahl enthalten sind, dann die Startzeit von j > = Endzeit von i oder umgekehrt .
  • Ihr Freund arbeitet als Campberater und ist verantwortlich für die Organisation von Aktivitäten für eine Reihe von Campern. Einer seiner Pläne ist die folgende Mini-Triathlon-Übung: Jeder Teilnehmer muss 20 Runden eines Pools schwimmen, dann 10 Meilen radeln und dann 3 Meilen laufen.
  • Es ist geplant, die Teilnehmer gestaffelt nach folgender Regel auszusenden: Die Teilnehmer müssen den Pool einzeln nutzen. Mit anderen Worten, zuerst schwimmt ein Teilnehmer die 20 Runden, steigt aus und beginnt mit dem Radfahren.
  • Sobald diese erste Person aus dem Pool ist, beginnt ein zweiter Teilnehmer die 20 Runden zu schwimmen. Sobald er oder sie unterwegs ist und mit dem Radfahren beginnt, beginnt ein dritter Teilnehmer zu schwimmen und so weiter.
  • Jeder Teilnehmer hat eine projizierte Schwimmzeit, eine projizierte Fahrradzeit und eine projizierte Laufzeit. Ihr Freund möchte einen Zeitplan für den Triathlon festlegen: eine Reihenfolge, in der die Starts der Teilnehmer sortiert werden.
  • Angenommen, die Fertigstellungszeit eines Zeitplans ist die früheste Zeit, zu der alle Teilnehmer mit allen drei Etappen des Triathlons fertig sind, vorausgesetzt, die Zeitprojektionen sind korrekt. Was ist die beste Reihenfolge, um Leute auszusenden, wenn man möchte, dass der gesamte Wettbewerb so schnell wie möglich vorbei ist? Geben Sie genauer einen effizienten Algorithmus an, der einen Zeitplan erstellt, dessen Fertigstellungszeit so klein wie möglich ist

Das Problem der Vorlesungsplanung

Schauen wir uns die verschiedenen Ansätze zur Lösung dieses Problems an.

Früheste Startzeit Zuerst,  dh wählen Sie das Intervall mit der frühesten Startzeit aus. Schauen Sie sich das folgende Beispiel an, das diese Lösung bricht. Diese Lösung ist fehlgeschlagen, da es ein Intervall geben kann, das sehr früh beginnt, aber sehr lang ist. Dies bedeutet, dass die nächste Strategie, die wir versuchen könnten, darin besteht, zuerst kleinere Intervalle zu betrachten.

Früheste Startzeit zuerst

Kleinstes Intervall Zuerst  wählen Sie die Vorlesungen in der Reihenfolge ihres Gesamtintervalls aus, das nichts anderes als ihr Intervall ist   finish time - start time. Auch diese Lösung ist nicht korrekt. Schauen Sie sich den folgenden Fall an.

Kürzestes Intervall zuerst

Sie können deutlich sehen, dass die kürzeste Intervallvorlesung die mittlere ist, aber das ist hier nicht die optimale Lösung. Schauen wir uns eine weitere Lösung für dieses Problem an, die sich aus dieser Lösung ergibt.

Am wenigsten widersprüchliches Intervall Zuerst  sollten Sie sich Intervalle ansehen, die die geringste Anzahl von Konflikten verursachen. Wir haben wieder ein Beispiel, bei dem dieser Ansatz keine optimale Lösung findet.

Am wenigsten widersprüchliches Intervall zuerst

Das Diagramm zeigt uns, dass das Intervall mit den geringsten Konflikten das in der Mitte mit nur 2 Konflikten ist. Danach können wir nur die beiden Intervalle ganz am Ende mit jeweils Konflikten 3 auswählen. Die optimale Lösung besteht jedoch darin, die 4 Intervalle auf der obersten Ebene auszuwählen.

Früheste Endzeit zuerst . Dies ist der Ansatz, der uns immer die optimale Lösung für dieses Problem bietet. Wir haben viele Erkenntnisse aus früheren Ansätzen gewonnen und sind schließlich auf diesen Ansatz gestoßen. Wir sortieren die Intervalle nach aufsteigender Reihenfolge ihrer Endzeiten und beginnen dann von Anfang an mit der Auswahl der Intervalle. Schauen Sie sich den folgenden Pseudocode an, um mehr Klarheit zu erhalten.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Wann verwenden wir Greedy-Algorithmen?

Gierige Algorithmen können Ihnen helfen, Lösungen für viele scheinbar schwierige Probleme zu finden. Das einzige Problem mit ihnen ist, dass Sie möglicherweise die richtige Lösung finden, aber möglicherweise nicht überprüfen können, ob es die richtige ist. Alle gierigen Probleme haben die gemeinsame Eigenschaft, dass ein lokales Optima letztendlich zu globalen Minima führen kann, ohne die bereits berücksichtigten Auswahlmöglichkeiten zu überdenken.

Gierige Algorithmen helfen uns, viele verschiedene Arten von Problemen zu lösen, wie zum Beispiel:

Problem mit dem kürzesten Weg:

Minimum Spanning Tree Problem in einem Diagramm

Huffman-Codierungsproblem

K Center Problem