Einführung in den Greedy-Algorithmus
Eine Strategie zur Lösung von Problemen. Der Greedy-Algorithmus wird als einer der Ansätze zur Lösung von Problemen angesehen. Dieser Ketzer zur Problemlösung geht mit einer Entscheidung einher, die in diesem Moment am besten zu sein scheint. Dieser Ansatz eignet sich am besten zur Lösung von Optimierungsproblemen. Optimierungsprobleme können als Probleme definiert werden, die entweder minimale oder maximale Ergebnisse erfordern. Ein Greedy-Algorithmus ist der einfachste und direkteste Ansatz, mit dem eine optimale Lösung erzielt werden kann.
Was ist der Greedy-Algorithmus?
Der Greedy-Algorithmus ist eine algorithmische Strategie, die verwendet wird, um in einem sehr kleinen Stadium die beste optionale Auswahl zu treffen und schließlich eine global optimale Lösung auszugeben. Dieser Algorithmus wählt die derzeit beste Lösung aus, ohne Rücksicht auf die Konsequenzen. Die gierige Methode besagt, dass das Problem in Stufen gelöst werden sollte, in denen jede Eingabe als möglich betrachtet wird. Da dieser Ansatz nur auf ein unmittelbares Ergebnis ohne Rücksicht auf das Gesamtbild abzielt, gilt er als gierig.
Kernkonzept definieren
Bis jetzt wissen wir, was ein gieriger Algorithmus ist und warum er so heißt. Mit den folgenden Zeigern können Sie den Greedy-Algorithmus besser verstehen. Inzwischen ist klar, dass der Greedy-Algorithmus nur dann funktioniert, wenn ein Problem vorliegt. Dieser Ansatz ist jedoch nur anwendbar, wenn wir eine Bedingung oder Einschränkung für dieses Problem haben.
Arten von Problemen
- Minimierungsproblem: Wenn alle Bedingungen erfüllt sind, ist es einfach, eine Lösung für ein Problem zu finden. Wenn dieses Problem jedoch ein minimales Ergebnis erfordert, wird es als Minimierungsproblem bezeichnet.
- Maximierungsproblem: Ein Problem, das das maximale Ergebnis erfordert, wird als Maximierungsproblem bezeichnet.
- Optimierungsproblem: Ein Problem wird Optimierungsproblem genannt, wenn es minimale oder maximale Ergebnisse erfordert.
Arten von Lösungen
- Machbare Lösung: Wenn jetzt ein Problem auftritt, haben wir viele plausible Lösungen für dieses Problem. Unter Berücksichtigung der für dieses Problem geltenden Bedingungen wählen wir jedoch Lösungen, die die gegebene Bedingung erfüllen. Solche Lösungen, die uns helfen, Ergebnisse zu erzielen, die die gegebene Bedingung erfüllen, werden als praktikable Lösung bezeichnet .
- Optimale Lösung: Eine Lösung wird als optimal bezeichnet, wenn sie bereits realisierbar ist und das Ziel des Problems erreicht. das beste Ergebnis. Dieses Ziel könnte entweder das minimale oder das maximale Ergebnis sein. Der hier zu beachtende Punkt ist, dass jedes Problem nur eine optimale Lösung hat.
Das folgende Beispiel wird Ihnen das Verständnis der gierigen Methode erleichtern. Angenommen, man möchte das beste auf dem Markt erhältliche Auto kaufen. Eine der Methoden zur Auswahl dieses Autos ist die Analyse aller Autos auf dem Markt. Da dies sehr zeitaufwendig ist, wählt man zur Vereinfachung ein Auto von bestimmten Marken aus, in die man investieren möchte. Wenn man dies weiter einordnet, wählt man erneut die gewünschten Modelle, um die Merkmale zu überprüfen. Daher ist der hier verwendete Ansatz gierig, da diese Lösung die optimale Lösung für Sie war, obwohl alle für Sie günstigen Faktoren berücksichtigt wurden.
Kernkomponenten eines Greedy-Algorithmus
Nachdem wir diesen Mechanismus besser verstanden haben, wollen wir die Kernkomponenten eines gierigen Algorithmus untersuchen, der ihn von anderen Prozessen unterscheidet:
- Kandidatensatz: Aus diesem Satz wird eine Antwort erstellt.
- Auswahlfunktion: Wählt den besten Kandidaten aus, der in die Lösung aufgenommen werden soll.
- Machbarkeitsfunktion: In diesem Abschnitt wird berechnet, ob ein Kandidat verwendet werden kann, um zur Lösung beizutragen.
- Eine objektive Funktion: Sie weist einer vollständigen oder einer Teillösung einen Wert zu.
- Eine Lösungsfunktion: Hiermit wird angezeigt, ob eine richtige Lösung gefunden wurde.
Wo funktioniert der Greedy-Algorithmus am besten?
Greedy-Algorithmus kann auf die unten genannten Probleme angewendet werden.
- Der Greedy-Ansatz kann verwendet werden, um den minimalen Spannbaum-Graphen unter Verwendung des Prim- oder Kruskal-Algorithmus zu finden
- Das Auffinden des kürzesten Pfades zwischen zwei Scheitelpunkten ist ein weiteres Problem, das mit einem Greedy-Algorithmus gelöst werden kann. Wenn Sie den Dijkstra-Algorithmus zusammen mit dem Greedy-Algorithmus anwenden, erhalten Sie eine optimale Lösung.
- Huffman-Codierung
Vorteile
Der größte Vorteil des Greedy-Algorithmus gegenüber anderen ist, dass er in den meisten Fällen einfach zu implementieren und sehr effizient ist.
Nachteile
Der Gierige Algorithmus baut im Grunde genommen eine Lösung Teil für Teil auf und wählt den nächsten Teil so aus, dass er sofort die beste Lösung für das vorliegende Problem liefert. Infolgedessen werden die Konsequenzen der aktuellen Entscheidung weder berücksichtigt noch befürchtet. Der Greedy-Algorithmus überprüft nie die zuvor getroffenen Entscheidungen und liefert keine optimale Lösung, obwohl er eine nahezu optimale Lösung liefert . Knapsack Problem und Travelling Salesman Problem sind Beispiele für Probleme, bei denen der Greedy-Algorithmus keine optimale Lösung liefert.
- Rucksack-Problem: Am häufigsten unter dem Namen Rucksack-Problem bekannt, ist ein alltägliches Problem, mit dem viele Menschen konfrontiert sind. Angenommen, wir haben eine Reihe von Gegenständen und jeder hat ein anderes Gewicht und einen anderen Wert (Gewinn), um in einen Behälter gefüllt zu werden, oder sollte so gesammelt werden, dass das Gesamtgewicht kleiner oder gleich dem des Behälters ist, während der Gesamtgewinn maximiert wird .
Fazit
Der Greedy-Algorithmus ist am besten anwendbar, wenn eine Lösung in Echtzeit benötigt wird und ungefähre Antworten „gut genug“ sind. Offensichtlich minimiert ein gieriger Algorithmus die Zeit und stellt gleichzeitig sicher, dass eine optimale Lösung erstellt wird. Daher eignet er sich besser für Situationen, in denen weniger Zeit erforderlich ist. Nach dem Lesen dieses Artikels könnte man eine gute Vorstellung von gierigen Algorithmen haben. Darüber hinaus wird in diesem Beitrag erläutert, warum es als das beste Framework angesehen wird, das nahezu alle Programmierherausforderungen beantwortet, und Ihnen dabei hilft, zu einem bestimmten Zeitpunkt die optimale Lösung zu finden.
Um jedoch die Theorie des gierigen Algorithmus anzuwenden, muss man härter arbeiten, um die richtigen Probleme zu kennen. Obwohl es ein wissenschaftliches Konzept ist, das Logik hat, hat es auch eine Essenz von Kreativität.
Empfohlene Artikel
Dies war ein Leitfaden für What is a Greedy Algorithm. Hier haben wir das Kernkonzept, die Komponenten, den Vorteil und den Nachteil des Greedy-Algorithmus erörtert. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -
- Algorithmus in der Programmierung
- Was ist Perl?
- Einführung in den Algorithmus
- Was ist agiler Sprint?