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

Was ist ein Greedy-Algorithmus?

A Gieriger Algorithmus Teilt eine Menge von Ressourcen rekursiv auf der Grundlage der maximalen unmittelbaren Verfügbarkeit dieser Ressource in jeder Phase der Ausführung auf.

Die Lösung eines Problems mit dem Greedy-Ansatz umfasst zwei Phasen:

1. Scannen der Artikelliste
2. Optimierung

Beide Phasen laufen parallel ab, während das Eingabe-Array schrittweise unterteilt wird.

Um dem Greedy-Ansatz zu folgen, sind Grundkenntnisse in Rekursion und Kontextwechsel hilfreich. tracBetrachten wir den Code. Das Greedy-Paradigma lässt sich mit einem Paar notwendiger und hinreichender Aussagen beschreiben.

Zwei Bedingungen definieren das Greedy-Paradigma.

• Jeder einzelne Entscheidungsschritt muss das Problem in Richtung der bestmöglichen Lösung lenken.
• Die Problemstruktur muss nach einer endlichen Anzahl von gierigen Schritten zum Stillstand kommen.

Nachdem wir die Theorie geklärt haben, wollen wir uns nun die Geschichte des Greedy-Search-Ansatzes ansehen.

Geschichte von Greedy Algorithms

Hier sind die wichtigsten Meilensteine ​​in der Geschichte der Greedy-Algorithmen:

• Greedy-Algorithmen wurden erstmals in den 1950er Jahren für Graph-Walk-Algorithmen konzipiert.
• Edsger Dijkstra entwickelte seinen Algorithmus zur Berechnung des kürzesten Weges, um Routen durch die niederländische Hauptstadt Amsterdam zu verkürzen.
• Im selben Jahrzehnt entwickelten Prim und Kruskal Optimierungsstrategien, die die Pfadkosten entlang gewichteter Routen minimieren, um minimale Spannbäume zu konstruieren.
• In den 70er Jahren beschrieben die amerikanischen Forscher Cormen, Leiserson, Rivest und Stein in ihrem klassischen Werk die rekursive Substrukturierung von Greedy-Lösungen. Introduction to Algorithms Lehrbuch.
• Das gierige Suchparadigma wurde 2005 in den NIST-Aufzeichnungen als eigenständige Optimierungsstrategie katalogisiert.
• Bis heute verwenden Webprotokolle wie Open Shortest Path First (OSPF) und viele Paketvermittlungsprotokolle die Greedy-Strategie, um die Transitzeit in einem Netzwerk zu minimieren.

Gierige Strategien und Entscheidungen

Die Logik reduziert sich in jeder Phase auf eine binäre Entscheidung – „gierig“ oder „nicht gierig“ – basierend auf der Richtung, die der Algorithmus zum Fortschreiten einschlägt.

Der Dijkstra-Algorithmus identifiziert beispielsweise Hosts im Internet, indem er in jedem Schritt eine Kostenfunktion auswertet. Der von der Kostenfunktion zurückgegebene Wert entscheidet darüber, ob der nächste Pfad „gierig“ oder „nicht-gierig“ ist.

Kurz gesagt, ein Algorithmus hört auf, gierig zu sein, sobald er einen Schritt unternimmt, der nicht lokal optimal ist, und gierige Probleme enden, wenn kein weiterer gieriger Schritt mehr möglich ist.

Eigenschaften des Greedy-Algorithmus

Die wichtigen Merkmale eines Greedy-Algorithmus sind:

• Eine geordnete Liste von Ressourcen enthält Kosten- oder Wertzuweisungen, die die Beschränkungen des Systems quantifizieren.
• Der Algorithmus nutzt die maximale Menge an Ressourcen innerhalb der vorgegebenen Zeit.
• Bei einem Aktivitätsplanungsproblem werden beispielsweise die Ressourcenkosten in Stunden gemessen und die Aktivitäten müssen der Reihe nach ausgeführt werden.

Warum den gierigen Ansatz wählen?

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

• Der gierige Ansatz birgt Kompromisse, die ihn für die Optimierung gut geeignet machen.
• Der offensichtlichste Grund ist, umgehend eine realisierbare Lösung zu finden. Im unten beschriebenen Problem der Aktivitätsauswahl können, falls weitere Aktivitäten vor Abschluss der aktuellen Aktivität möglich sind, diese im selben Zeitfenster eingeplant werden.
• Ein weiterer Grund ist, dass es ein Problem rekursiv anhand einer Bedingung aufteilt, ohne dass Teillösungen zusammengeführt werden müssen.
• Bei dem Problem der Aktivitätsauswahl wird der rekursive Teilungsschritt dadurch erreicht, dass die Liste einmal durchsucht und nur die in Frage kommenden Aktivitäten berücksichtigt werden.

Wie man das Problem der Aktivitätsauswahl löst

Im Beispiel der Aktivitätsplanung hat jede Aktivität eine Start- und Endzeit und ist zur besseren Übersicht mit einer Nummer gekennzeichnet. Es gibt zwei Aktivitätskategorien:

1. Berücksichtigung der Aktivität: Die Referenzaktivität, anhand derer die Fähigkeit gemessen wird, weitere verbleibende Aktivitäten einzufügen.
2. Verbleibende Aktivitäten: Aktivitäten an einem oder mehreren Indizes vor der betrachteten Aktivität.

Die Kosten für die Durchführung einer Aktivität entsprechen ihrer Dauer, berechnet als (Ende – Anfang).

Der gierige Umfang ist einfach die Anzahl der verbleibenden Aktivitäten, die innerhalb der Zeit einer betrachteten Aktivität durchgeführt werden können.

ArchiStruktur des Greedy Approach

Schritt 1) Scannen Sie die Liste der Aktivitätskosten, beginnend mit dem Index 0 als Ausgangspunkt.

Schritt 2) Wenn bis zum Ende der betrachteten Aktivität weitere Aktivitäten abgeschlossen werden können, suchen Sie nach diesen verbleibenden Aktivitäten.

Schritt 3) Wenn keine weiteren Aktivitäten geplant werden können, wird die aktuell verbleibende Aktivität als nächste berücksichtigte Aktivität herangezogen. Wiederholen Sie Schritt 1 und Schritt 2 mit der neuen Aktivität. Falls keine Aktivitäten mehr verfügbar sind, fahren Sie mit Schritt 4 fort.

Schritt 4) Gib die Vereinigung der betrachteten Indizes zurück – dies sind die Aktivitätsindizes, die den Durchsatz maximieren.

ArchiStruktur des Greedy Approach

Code Erläuterung

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

#define MAX_ACTIVITIES 12

Erklärung des Codes:

1. Enthaltene Header-Dateien/Klassen
2. Die maximale Anzahl der vom Benutzer konfigurierbaren Aktivitäten.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Erklärung des Codes:

1. Deklariert den Standard-Namensraum für Streaming-Operationen.
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 für Activity.
2. Zeitstempel, die zusammen eine Dauer definieren.
3. Im Standardkonstruktor werden alle Zeitstempel 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. considered_index ist der Startpunkt für das Scannen des Arrays.
3. init_index wird verwendet, um während der Einrichtung zufällige Zeitstempel zuzuweisen.
4. Mit dem new-Operator wird dynamisch ein Array von Activity-Objekten erstellt.
5. Der geplante Zeiger enthält das aktuelle Ergebnis der Greedy-Operation.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Erklärung des Codes:

1. Der Scheduler-Konstruktor — Teil 2 der Klassendefinition.
2. considered_index markiert den Beginn des aktuellen Scans.
3. Das Ausmaß der Gier 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);
 }
&#8230;
&#8230;

Erklärung des Codes:

1. Eine For-Schleife initialisiert die Start- und Endzeiten jeder geplanten Aktivität.
2. Legt die Startzeit fest.
3. Legt als Endzeitpunkt fest, dass er mindestens zur Startzeit liegt.
4. Eine Debug-Anweisung gibt die zugewiesenen Zeitdauern aus.

	public:
   		 Activity * activity_select(int);
};

Erklärung des Codes:

1. Teil 4 — der letzte Teil der Scheduler-Klassendefinition.
2. activity_select() nimmt einen Startindex als Basis und teilt die gierige Suche in Teilprobleme auf.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Der Bereichsauflösungsoperator (::) verknüpft die Funktionsdefinition mit der Klasse Scheduler.
2. considered_index wird als Wert übergeben, und greedy_extent wird auf den unmittelbar darauf folgenden 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++;
    	}
&#8230;
...

Erklärung des Codes:

1. Die Kernlogik – die gierige Ausdehnung ist auf MAX_ACTIVITIES begrenzt.
2. Die Startzeit der aktuellen Aktivität wird mit der Endzeit der betrachteten Aktivität verglichen.
3. Solange die Bedingung erfüllt ist, wird optional eine Debug-Meldung ausgegeben.
4. Der gierige Extent geht dann zum nächsten Index im Aktivitätsarray über.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Erklärung des Codes:

1. Die Bedingungsprüfung stellt sicher, dass alle Aktivitäten abgedeckt sind.
2. Andernfalls startet der Algorithmus die gierige Suche vom aktuellen Index aus neu – ein rekursiver Schritt, der das Problem gierig aufteilt.
3. Falls ja, wird die Kontrolle an den Aufrufer zurückgegeben, ohne dass die Möglichkeit besteht, Greed zu erweitern.

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 ruft den Scheduler auf.
2. Ein neues Scheduler-Objekt wird instanziiert.
3. Die Funktion activity_select() gibt nach Beendigung der gierigen Quest einen Activity-Zeiger an den Aufrufer zurück.

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

Der Greedy-Ansatz eignet sich nicht für Probleme, die für jedes Teilproblem eine optimale Lösung erfordern, wie beispielsweise das Sortieren.

In solchen Fällen kann die Greedy-Methode zu Fehlern führen – im schlimmsten Fall liefert sie eine nicht optimale Lösung.

Der größte Nachteil gieriger Algorithmen besteht darin, dass sie Entscheidungen treffen, ohne zu wissen, was nach dem aktuellen gierigen Zustand kommt.

Das folgende Diagramm veranschaulicht diesen Nachteil der Greedy-Methode.

Bei dem hier als Baum dargestellten Greedy-Scan (höherer Wert bedeutet höhere Gier) würde ein Algorithmus mit dem Wert 40 als nächstes 29 auswählen, dann bei 12 enden, was insgesamt 41 ergibt.

Im Gegensatz dazu würde eine Divide-and-Conquer-Strategie 25 mit 40 kombinieren, was insgesamt 65 ergibt und 24 Punkte höher ist als bei der lokal gierigen Wahl.

Beispiele für Gierig Algorithms

Die meisten Netzwerkalgorithmen basieren auf einem Greedy-Ansatz. Gängige Beispiele für Greedy-Algorithmen sind:

• Prims Algorithmus für minimale Spannbäume
• Problem des Handlungsreisenden (ungefähr)
• Graphische Kartenfärbung
• Kruskals Algorithmus für minimale Spannbäume
• Dijkstras Algorithmus für den kürzesten Pfad
• Knotenüberdeckung des Graphen
• Rucksackproblem
• Jobsequenzierung mit Fristen

Häufig gestellte Fragen