Greedy-Algorithmus mit Beispiel: Was ist, Methode und Ansatz

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

Zwei Bedingungen definieren das Greedy-Paradigma.

• Jede schrittweise Lösung muss ein Problem in Richtung der am besten akzeptierten Lösung strukturieren.
• Es reicht aus, wenn die Strukturierung des Problems in einer endlichen Anzahl gieriger Schritte anhalten kann.

Lassen Sie uns im weiteren Verlauf der Theorie die Geschichte beschreiben, die mit dem Greedy-Suchansatz verbunden ist.

Geschichte von Greedy Algorithms

Hier ist ein wichtiger Meilenstein der Greedy-Algorithmen:

• Greedy-Algorithmen wurden in den 1950er Jahren für viele Graph-Walk-Algorithmen konzipiert.
• Esdger Djikstra hat den Algorithmus so konzipiert, dass er minimale Spannbäume generiert. Sein Ziel war es, die Streckenlänge innerhalb der niederländischen Hauptstadt Amsterdam zu verkürzen.
• Im selben Jahrzehnt entwickelten Prim und Kruskal Optimierungsstrategien, die auf der Minimierung der Pfadkosten entlang gewichteter Routen beruhten.
• In den 70er Jahren schlugen die amerikanischen Forscher Cormen, Rivest und Stein in ihrem klassischen Einführungsbuch in die Algorithmen eine rekursive Substrukturierung von Greedy-Lösungen vor.
• Das Greedy-Suchparadigma wurde 2005 als eine andere Art von Optimierungsstrategie in den NIST-Aufzeichnungen registriert.
• Bis heute verwenden Protokolle, die das Web betreiben, wie etwa das Open-Shortest-Path-First (OSPF) und viele andere Netzwerk-Paketvermittlungsprotokolle, die Greedy-Strategie, um den Zeitaufwand für ein 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, mit dem in jeder Algorithmusstufe vorangekommen wurde.

Beispielsweise nutzte der Algorithmus von Djikstra eine schrittweise gierige Strategie zur Identifizierung von Hosts im Internet durch Berechnung einer Kostenfunktion. Der von der Kostenfunktion zurückgegebene Wert legte fest, ob der nächste Pfad „gierig“ oder „nicht gierig“ ist.

Kurz gesagt: Ein Algorithmus ist nicht mehr gierig, wenn er zu irgendeinem Zeitpunkt einen Schritt unternimmt, der nicht lokal gierig ist. Die Greedy-Probleme hören auf, da die Gier kein weiteres Ausmaß mehr hat.

Eigenschaften des Greedy-Algorithmus

Die wichtigen Merkmale eines Greedy-Algorithmus sind:

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

Warum den Greedy-Ansatz verwenden?

Hier sind die Gründe für die Verwendung des Greedy-Ansatzes:

• Der Greedy-Ansatz weist einige Kompromisse auf, die ihn möglicherweise für die Optimierung geeignet machen.
• Ein wichtiger Grund ist, sofort die realisierbarste Lösung zu finden. Wenn beim Aktivitätsauswahlproblem (unten erläutert) mehr Aktivitäten ausgeführt werden können, bevor die aktuelle Aktivität abgeschlossen ist, können diese Aktivitäten gleichzeitig ausgeführt werden.
• Ein weiterer Grund besteht darin, ein Problem rekursiv basierend auf einer Bedingung zu unterteilen, ohne dass alle Lösungen kombiniert werden müssen.
• Beim Aktivitätsauswahlproblem wird der Schritt der „rekursiven Division“ erreicht, indem eine Liste von Elementen nur einmal gescannt und bestimmte Aktivitäten berücksichtigt werden.

So lösen Sie das Problem der Aktivitätsauswahl

Im Beispiel der Aktivitätsplanung gibt es für jede Aktivität eine „Start“- und „Endzeit“. Jede Aktivität ist als Referenz mit einer Nummer versehen. Es gibt zwei Aktivitätskategorien.

1. betrachtete Aktivität: ist die Aktivität, die die Referenz darstellt, anhand derer die Fähigkeit analysiert wird, mehr als eine verbleibende Aktivität auszuführen.
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 – Anfang) gibt uns die Dauer als Kosten einer Aktivität an.

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

ArchiStruktur des Greedy-Ansatzes

SCHRITT 1) Durchsuchen Sie die Liste der Aktivitätskosten, beginnend mit Index 0 als berücksichtigtem Index.

SCHRITT 2) Wenn bis zum Abschluss der betreffenden Aktivität noch weitere Aktivitäten abgeschlossen werden können, beginnen Sie mit der Suche nach einer oder mehreren verbleibenden Aktivitäten.

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

SCHRITT 4 ) Gibt die Vereinigung der betrachteten Indizes zurück. Dies sind die Aktivitätsindizes, die zur Maximierung des Durchsatzes verwendet werden.

Code Erklärung

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#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 Stundenvariable.

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 Definition der Scheduler-Klasse.
2. Der berücksichtigte Index ist der Ausgangspunkt für das Scannen Array.
3. Der Initialisierungsindex wird verwendet, um zufällige Zeitstempel zuzuweisen.
4. Ein Array von Aktivitätsobjekten wird dynamisch mithilfe des neuen Operators zugewiesen.
5. Der geplante Zeiger definiert den aktuellen Basisstandort 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. Der aktuelle Greedy-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 Endzeiten aller aktuell geplanten Aktivitäten.
2. Startzeitinitialisierung.
3. Endzeitinitialisierung immer nach oder genau zur Startstunde.
4. Eine Debug-Anweisung zum Ausdrucken zugewiesener Dauern.

	public:
   		 Activity * activity_select(int);
};

Erklärung des Codes:

1. Teil 4 – der letzte Teil der Definition der Scheduler-Klasse.
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. Mithilfe des Bereichsauflösungsoperators (::) wird die Funktionsdefinition bereitgestellt.
2. Der betrachtete Index ist der nach Wert aufgerufene Index. Der greedy_extent wird nur einen Index nach dem betrachteten Index initialisiert.

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 Ausmaß der Gier ist auf die Anzahl der Aktivitäten beschränkt.
2. Die Startstunden der aktuellen Aktivität werden als planbar überprüft, bevor die betreffende Aktivität (angegeben durch den betreffenden Index) enden würde.
3. Solange dies möglich ist, wird eine optionale Debug-Anweisung gedruckt.
4. Gehen Sie zum nächsten Index im Aktivitätsarray

...
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 Ihren Greedy 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 und hat keinen Spielraum für die Ausweitung der Gier.

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 Planers.
2. Ein neuer Scheduler wird instanziiert.
3. Die Aktivitätsauswahlfunktion, die einen Zeiger vom Typ Aktivität zurückgibt, kehrt zum Aufrufer zurück, nachdem die gierige Suche beendet ist.

Ausgang:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

Einschränkungen der Greedy-Technik

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

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

Der Nachteil von Greedy-Algorithmen besteht daher darin, dass man nicht weiß, was vor dem aktuellen Greedy-Zustand liegt.

Nachfolgend finden Sie eine Darstellung der Nachteile der Greedy-Methode:

Im hier als Baum dargestellten gierigen Scan (höherer Wert, höhere Gier) nimmt ein Algorithmus mit dem Wert 40 wahrscheinlich 29 als nächsten Wert an. Außerdem endet seine Quest bei 12. Dies ergibt einen Wert von 41.

Allerdings, wenn der Algorithmus einen suboptimalen Weg eingeschlagen oder eine Eroberungsstrategie übernommen hat. dann würde auf 25 40 folgen, und die Gesamtkostenverbesserung wäre 65, was als suboptimale Entscheidung um 24 Punkte höher bewertet wird.

Beispiele für Gierig Algorithms

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

• Prims Minimal Spanning Tree-Algorithmus
• Problem mit dem reisenden Verkäufer
• Diagramm – Kartenfärbung
• Kruskals Minimal-Spanning-Tree-Algorithmus
• Dijkstras Minimal Spanning Tree-Algorithmus
• Diagramm – Scheitelpunktabdeckung
• Rucksackproblem
• Jobplanungsproblem

Zusammenfassung

Zusammenfassend lässt sich sagen, dass der Artikel das Greedy-Paradigma definiert und gezeigt hat, wie Greedy-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 häufig zur Problemlösung eingesetzt, und zwar als Greedy-Algorithmus Python, C, C#, PHP, Javausw. Die Aktivitätsauswahl des Greedy-Algorithmusbeispiels wurde als strategisches Problem beschrieben, bei dem mit dem Greedy-Ansatz ein maximaler Durchsatz erzielt werden konnte. Abschließend wurden die Nachteile der Verwendung des Greedy-Ansatzes erläutert.