DAA - Gierige Methode
Unter allen algorithmischen Ansätzen ist der einfachste und unkomplizierteste Ansatz die Greedy-Methode. Bei diesem Ansatz wird die Entscheidung auf der Grundlage der aktuell verfügbaren Informationen getroffen, ohne sich über die Auswirkungen der aktuellen Entscheidung in der Zukunft Gedanken zu machen.
Gierige Algorithmen bauen Teil für Teil eine Lösung auf und wählen den nächsten Teil so aus, dass er einen unmittelbaren Nutzen bringt. Bei diesem Ansatz werden die zuvor getroffenen Entscheidungen nie überdacht. Dieser Ansatz wird hauptsächlich zur Lösung von Optimierungsproblemen verwendet. Die gierige Methode ist einfach zu implementieren und in den meisten Fällen recht effizient. Daher können wir sagen, dass der Greedy-Algorithmus ein auf Heuristiken basierendes algorithmisches Paradigma ist, das bei jedem Schritt der lokalen optimalen Auswahl folgt, in der Hoffnung, eine globale optimale Lösung zu finden.
Bei vielen Problemen führt es nicht zu einer optimalen Lösung, obwohl es in angemessener Zeit eine ungefähre (nahezu optimale) Lösung liefert.
Komponenten des Greedy-Algorithmus
Gierige Algorithmen haben die folgenden fünf Komponenten:
A candidate set - Aus diesem Set wird eine Lösung erstellt.
A selection function - Wird verwendet, um den besten Kandidaten für die Lösung auszuwählen.
A feasibility function - Wird verwendet, um zu bestimmen, ob ein Kandidat verwendet werden kann, um zur Lösung beizutragen.
An objective function - Wird verwendet, um einer Lösung oder einer Teillösung einen Wert zuzuweisen.
A solution function - Wird verwendet, um anzuzeigen, ob eine vollständige Lösung erreicht wurde.
Anwendungsbereiche
Gieriger Ansatz wird verwendet, um viele Probleme zu lösen, wie z
Finden des kürzesten Pfades zwischen zwei Eckpunkten mithilfe des Dijkstra-Algorithmus.
Finden des minimalen Spannbaums in einem Diagramm unter Verwendung des Prim / Kruskal-Algorithmus usw.
Wo gieriger Ansatz fehlschlägt
Bei vielen Problemen findet der Greedy-Algorithmus keine optimale Lösung, außerdem kann er zu einer schlechtesten Lösung führen. Probleme wie Travelling Salesman und Knapsack können mit diesem Ansatz nicht gelöst werden.