Gieriger Algorithmus mit Beispielen: Gierige Methode & Ansatz

Inhaltsverzeichnis:

Anonim

Was ist ein gieriger Algorithmus?

Im Greedy-Algorithmus wird eine Reihe von Ressourcen rekursiv aufgeteilt, basierend auf der maximalen, sofortigen Verfügbarkeit dieser Ressource in einem bestimmten Ausführungsstadium.

Um ein Problem zu lösen, das auf dem gierigen Ansatz basiert, gibt es zwei Stufen

  1. Scannen der Liste der Elemente
  2. Optimierung

Diese Phasen werden in diesem Tutorial zum Greedy-Algorithmus im Verlauf der Aufteilung des Arrays parallel behandelt.

Um den gierigen Ansatz zu verstehen, müssen Sie über Kenntnisse in Rekursion und Kontextwechsel verfügen. Dies hilft Ihnen zu verstehen, wie Sie den Code verfolgen. Sie können das gierige Paradigma anhand Ihrer eigenen notwendigen und ausreichenden Aussagen definieren.

Zwei Bedingungen definieren das gierige Paradigma.

  • Jede schrittweise Lösung muss ein Problem in Richtung seiner am besten akzeptierten Lösung strukturieren.
  • Es reicht aus, wenn die Strukturierung des Problems in einer endlichen Anzahl von gierigen Schritten zum Stillstand kommen kann.

Lassen Sie uns unter Fortsetzung der Theoretisierung die Geschichte beschreiben, die mit dem Greedy-Suchansatz verbunden ist.

In diesem Tutorial zum Greedy-Algorithmus lernen Sie:

  • Geschichte gieriger Algorithmen
  • Gierige Strategien und Entscheidungen
  • Merkmale des gierigen Ansatzes
  • Warum den gierigen Ansatz verwenden?
  • So lösen Sie das Problem mit der Aktivitätsauswahl
  • Architektur des gierigen Ansatzes
  • Nachteile von gierigen Algorithmen

Geschichte gieriger Algorithmen

Hier ist ein wichtiger Meilenstein gieriger Algorithmen:

  • Gierige Algorithmen wurden in den 1950er Jahren für viele Graph-Walk-Algorithmen konzipiert.
  • Esdger Djikstra konzipierte den Algorithmus, um minimale Spannbäume zu generieren. Er wollte die Spannweite der Strecken in der niederländischen Hauptstadt Amsterdam verkürzen.
  • Im selben Jahrzehnt erreichten Prim und Kruskal Optimierungsstrategien, die auf der Minimierung der Pfadkosten auf gewogenen Strecken basierten.
  • In den 70er Jahren schlugen die amerikanischen Forscher Cormen, Rivest und Stein in ihrer klassischen Einführung in das Algorithmusbuch eine rekursive Substrukturierung gieriger Lösungen vor.
  • Das Greedy-Suchparadigma wurde 2005 in den NIST-Datensätzen als eine andere Art von Optimierungsstrategie registriert.
  • Bis heute verwenden Protokolle, die das Web ausführen, wie das Open-Shortest-Path-First (OSPF) und viele andere Protokolle zur Netzwerkpaketvermittlung, die gierige Strategie, um den Zeitaufwand in einem Netzwerk zu minimieren.

Gierige Strategien und Entscheidungen

Logik in ihrer einfachsten Form wurde auf "gierig" oder "nicht gierig" reduziert. Diese Aussagen wurden durch den Ansatz definiert, der gewählt wurde, um in jeder Algorithmusstufe voranzukommen.

Zum Beispiel verwendete der Algorithmus von Djikstra eine schrittweise gierige Strategie, um Hosts im Internet durch Berechnung einer Kostenfunktion zu identifizieren. Der von der Kostenfunktion zurückgegebene Wert bestimmt, ob der nächste Pfad "gierig" oder "nicht gierig" ist.

Kurz gesagt, ein Algorithmus hört auf, gierig zu sein, wenn er zu irgendeinem Zeitpunkt einen Schritt unternimmt, der lokal nicht gierig ist. Die gierigen Probleme hören ohne weiteren Umfang der Gier auf.

Merkmale des gierigen Ansatzes

Die wichtigen Merkmale eines Greedy-Methodenalgorithmus sind:

  • Es gibt eine geordnete Liste von Ressourcen mit Kosten- oder Wertzuordnungen. Diese quantifizieren Einschränkungen für ein System.
  • Sie nehmen die maximale Menge an Ressourcen in der Zeit, in der eine Einschränkung angewendet wird.
  • Beispielsweise sind bei einem Aktivitätsplanungsproblem die Ressourcenkosten in Stunden angegeben, und die Aktivitäten müssen in serieller Reihenfolge ausgeführt werden.

Warum den gierigen Ansatz verwenden?

Hier sind die Gründe für den gierigen Ansatz:

  • Der gierige Ansatz hat einige Kompromisse, die ihn für die Optimierung geeignet machen können.
  • Ein wichtiger Grund ist, sofort die bestmögliche Lösung zu finden. Wenn im Aktivitätsauswahlproblem (unten erläutert) vor Abschluss der aktuellen Aktivität weitere Aktivitäten ausgeführt werden können, können diese Aktivitäten innerhalb derselben Zeit ausgeführt werden.
  • Ein weiterer Grund besteht darin, ein Problem rekursiv basierend auf einer Bedingung zu teilen, ohne dass alle Lösungen kombiniert werden müssen.
  • Bei dem Aktivitätsauswahlproblem wird der Schritt "rekursive Unterteilung" erreicht, indem eine Liste von Elementen nur einmal gescannt und bestimmte Aktivitäten berücksichtigt werden.

So lösen Sie das Problem mit der Aktivitätsauswahl

Im Beispiel für die Aktivitätsplanung gibt es für jede Aktivität eine Start- und eine Endzeit. Jede Aktivität wird durch eine Nummer als Referenz indiziert. Es gibt zwei Aktivitätskategorien.

  1. betrachtete Aktivität : ist die Aktivität, die die Referenz ist, anhand derer die Fähigkeit, mehr als eine verbleibende Aktivität auszuführen, analysiert wird.
  2. verbleibende Aktivitäten: Aktivitäten an einem oder mehreren Indizes vor der betrachteten Aktivität.

Die Gesamtdauer gibt die Kosten für die Durchführung der Aktivität an. Das heißt (Ende - Start) gibt uns die Dauer als die Kosten einer Aktivität.

Sie werden feststellen, dass das gierige Ausmaß die Anzahl der verbleibenden Aktivitäten ist, die Sie in der Zeit einer betrachteten Aktivität ausführen können.

Architektur des gierigen Ansatzes

SCHRITT 1)

Scannen Sie die Liste der Aktivitätskosten, beginnend mit Index 0 als berücksichtigtem Index.

SCHRITT 2)

Wenn bis zu dem Zeitpunkt mehr Aktivitäten abgeschlossen sein können, die betrachtete Aktivität beendet ist, suchen Sie nach einer oder mehreren verbleibenden Aktivitäten.

SCHRITT 3)

Wenn keine verbleibenden Aktivitäten mehr vorhanden sind, wird die aktuell verbleibende Aktivität zur nächsten berücksichtigten Aktivität. Wiederholen Sie Schritt 1 und Schritt 2 mit der neu berücksichtigten Aktivität. Wenn keine verbleibenden Aktivitäten mehr vorhanden sind, fahren Sie mit Schritt 4 fort.

SCHRITT 4 )

Geben Sie die Vereinigung der berücksichtigten Indizes zurück. Dies sind die Aktivitätsindizes, die zur Maximierung des Durchsatzes verwendet werden.

Architektur des gierigen Ansatzes

Code Erklärung

#include#include#include#define MAX_ACTIVITIES 12

Erklärung des Codes:

  1. Enthaltene Header-Dateien / Klassen
  2. Eine maximale Anzahl von Aktivitäten, die vom Benutzer bereitgestellt werden.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Erklärung des Codes:

  1. Der Namespace für Streaming-Vorgänge.
  2. Eine Klassendefinition für TIME
  3. Ein Stunden-Zeitstempel.
  4. Ein TIME-Standardkonstruktor
  5. Die Stunden variabel.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Erklärung des Codes:

  1. Eine Klassendefinition aus Aktivität
  2. Zeitstempel, die eine Dauer definieren
  3. Alle Zeitstempel werden im Standardkonstruktor auf 0 initialisiert
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Erklärung des Codes:

  1. Teil 1 der Scheduler-Klassendefinition.
  2. Der betrachtete Index ist der Ausgangspunkt für das Scannen des Arrays.
  3. Der Initialisierungsindex wird verwendet, um zufällige Zeitstempel zuzuweisen.
  4. Ein Array von Aktivitätsobjekten wird mithilfe des neuen Operators dynamisch zugewiesen.
  5. Der geplante Zeiger definiert den aktuellen Basisort für Gier.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Erklärung des Codes:

  1. Der Scheduler-Konstruktor - Teil 2 der Scheduler-Klassendefinition.
  2. Der betrachtete Index definiert den aktuellen Start des aktuellen Scans.
  3. Das aktuelle gierige Ausmaß ist zu Beginn undefiniert.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… …

Erklärung des Codes:

  1. Eine for-Schleife zum Initialisieren der Start- und Endstunden jeder der aktuell geplanten Aktivitäten.
  2. Initialisierung der Startzeit.
  3. Endzeitinitialisierung immer nach oder genau zur Startstunde.
  4. Eine Debug-Anweisung zum Ausdrucken der zugewiesenen Dauer.
public:Activity * activity_select(int);};

Erklärung des Codes:

  1. Teil 4 - der letzte Teil der Scheduler-Klassendefinition.
  2. Die Aktivitätsauswahlfunktion verwendet einen Startpunktindex als Basis und unterteilt die gierige Suche in gierige Teilprobleme.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Mit dem Bereichsauflösungsoperator (: :) wird die Funktionsdefinition bereitgestellt.
  2. Der betrachtete Index ist der nach Wert aufgerufene Index. Der greedy_extent ist der initialisierte Index nur nach dem betrachteten Index.
Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… …

Erklärung des Codes:

  1. Die Kernlogik - Das gierige Ausmaß ist auf die Anzahl der Aktivitäten beschränkt.
  2. Die Startstunden der aktuellen Aktivität werden als planbar überprüft, bevor die betrachtete Aktivität (angegeben durch den berücksichtigten Index) beendet wird.
  3. Solange dies möglich ist, wird eine optionale Debug-Anweisung gedruckt.
  4. Fahren Sie mit dem nächsten Index des Aktivitätsarrays fort
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Erklärung des Codes:

  1. Die Bedingung prüft, ob alle Aktivitäten abgedeckt wurden.
  2. Wenn nicht, können Sie Ihre Gier mit dem betrachteten Index als aktuellem Punkt neu starten. Dies ist ein rekursiver Schritt, der die Problemstellung gierig teilt.
  3. Wenn ja, kehrt es zum Anrufer zurück, ohne dass die Gier erweitert werden kann.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Erklärung des Codes:

  1. Die Hauptfunktion zum Aufrufen des Schedulers.
  2. Ein neuer Scheduler wird instanziiert.
  3. Die Aktivitätsauswahlfunktion, die einen Zeiger vom Typ Aktivität zurückgibt, kehrt zum Anrufer zurück, nachdem die gierige Quest beendet ist.

Ausgabe:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Nachteile von gierigen Algorithmen

Es ist nicht für gierige Probleme geeignet, bei denen für jedes Teilproblem wie das Sortieren eine Lösung erforderlich ist.

Bei solchen Übungsproblemen mit dem Greedy-Algorithmus kann die Greedy-Methode falsch sein. im schlimmsten Fall sogar zu einer nicht optimalen Lösung führen.

Daher besteht der Nachteil von gierigen Algorithmen darin, nicht zu wissen, was vor dem aktuellen gierigen Zustand liegt.

Nachfolgend finden Sie eine Darstellung des Nachteils der Greedy-Methode:

In dem hier als Baum gezeigten gierigen Scan (höherer Wert, höhere Gier) wird ein Algorithmusstatus mit dem Wert: 40 wahrscheinlich 29 als nächsten Wert annehmen. Außerdem endet seine Quest um 12. Dies entspricht einem Wert von 41.

Wenn der Algorithmus jedoch einen suboptimalen Weg eingeschlagen oder eine Eroberungsstrategie angenommen hat. dann würde 25 gefolgt von 40, und die Gesamtkostenverbesserung wäre 65, was als suboptimale Entscheidung um 24 Punkte höher bewertet wird.

Beispiele für gierige Algorithmen

Die meisten Netzwerkalgorithmen verwenden den gierigen Ansatz. Hier ist eine Liste einiger Beispiele für Greedy-Algorithmen:

  • Prims minimaler Spanning Tree-Algorithmus
  • Problem mit dem reisenden Verkäufer
  • Grafik - Kartenfärbung
  • Kruskals Minimal Spanning Tree-Algorithmus
  • Dijkstras Minimal Spanning Tree-Algorithmus
  • Grafik - Scheitelpunktabdeckung
  • Rucksackproblem
  • Job Scheduling Problem

Zusammenfassung:

Zusammenfassend definierte der Artikel das gierige Paradigma und zeigte, wie gierige Optimierung und Rekursion Ihnen helfen können, bis zu einem gewissen Punkt die beste Lösung zu finden. Der Greedy-Algorithmus wird in vielen Sprachen wie dem Greedy-Algorithmus Python, C, C #, PHP, Java usw. häufig zur Problemlösung eingesetzt. Die Aktivitätsauswahl des Greedy-Algorithmus-Beispiels wurde als strategisches Problem beschrieben, mit dem mit dem Greedy ein maximaler Durchsatz erzielt werden kann Ansatz. Am Ende wurden die Nachteile der Verwendung des gierigen Ansatzes erklärt.