Datenstrukturen - Gierige Algorithmen

Ein Algorithmus wurde entwickelt, um eine optimale Lösung für ein bestimmtes Problem zu erreichen. Beim gierigen Algorithmus werden Entscheidungen aus der gegebenen Lösungsdomäne getroffen. Als gierig wird die nächstgelegene Lösung gewählt, die eine optimale Lösung zu bieten scheint.

Gierige Algorithmen versuchen, eine lokalisierte optimale Lösung zu finden, die schließlich zu global optimierten Lösungen führen kann. Im Allgemeinen bieten gierige Algorithmen jedoch keine global optimierten Lösungen.

Münzen zählen

Dieses Problem besteht darin, durch Auswahl der kleinstmöglichen Münzen bis zu einem gewünschten Wert zu zählen, und der gierige Ansatz zwingt den Algorithmus, die größtmögliche Münze auszuwählen. Wenn uns Münzen im Wert von 1, 2, 5 und 10 Pfund Sterling zur Verfügung gestellt werden und wir aufgefordert werden, 18 Pfund Sterling zu zählen, ist das gierige Verfahren -

• 1 - Wählen Sie eine 10-Pfund-Münze aus, die verbleibende Anzahl beträgt 8

• 2 - Wählen Sie dann eine 5-Pfund-Münze aus, die verbleibende Anzahl beträgt 3

• 3 - Wählen Sie dann eine 2-Pfund-Münze aus, die verbleibende Anzahl beträgt 1

• 4 - Und schließlich löst die Auswahl von 1-Pfund-Münzen das Problem

Obwohl es gut zu funktionieren scheint, müssen wir für diese Zählung nur 4 Münzen auswählen. Wenn wir das Problem jedoch geringfügig ändern, kann der gleiche Ansatz möglicherweise nicht das gleiche optimale Ergebnis erzielen.

Für das Währungssystem, in dem wir Münzen mit einem Wert von 1, 7, 10 haben, ist das Zählen von Münzen für den Wert 18 absolut optimal, aber für das Zählen wie 15 werden möglicherweise mehr Münzen als erforderlich verwendet. Zum Beispiel verwendet der gierige Ansatz 10 + 1 + 1 + 1 + 1 + 1, insgesamt 6 Münzen. Während das gleiche Problem mit nur 3 Münzen (7 + 7 + 1) gelöst werden könnte

Wir können daher den Schluss ziehen, dass der gierige Ansatz eine sofort optimierte Lösung auswählt und fehlschlägt, wenn die globale Optimierung ein Hauptanliegen ist.

Beispiele

Die meisten Netzwerkalgorithmen verwenden den gierigen Ansatz. Hier ist eine Liste von wenigen -

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

Es gibt viele ähnliche Probleme, bei denen der gierige Ansatz verwendet wird, um eine optimale Lösung zu finden.