Python - Algorithmusklassen

Algorithmen sind eindeutige Schritte, die uns durch die Verarbeitung von null oder mehr Eingaben eine genau definierte Ausgabe liefern sollten. Dies führt zu vielen Ansätzen beim Entwerfen und Schreiben der Algorithmen. Es wurde beobachtet, dass die meisten Algorithmen in die folgenden Kategorien eingeteilt werden können.

Gierige Algorithmen

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.

Gierige Algorithmen suchen daher zu diesem Zeitpunkt nach einer einfachen Lösung, ohne zu berücksichtigen, wie sich dies auf die zukünftigen Schritte auswirkt. Es ähnelt der Art und Weise, wie Menschen Probleme lösen, ohne die vollständigen Details der bereitgestellten Eingaben durchzugehen.

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

Problem mit dem reisenden Verkäufer
Prims Minimal Spanning Tree-Algorithmus
Kruskals Minimal Spanning Tree-Algorithmus
Dijkstras Minimal Spanning Tree-Algorithmus

Teilen und erobern

Diese Klasse von Algorithmen beinhaltet das Aufteilen des gegebenen Problems in kleinere Unterprobleme und das anschließende unabhängige Lösen jedes Unterproblems. Wenn das Problem nicht weiter unterteilt werden kann, beginnen wir, die Lösung mit jedem der Unterprobleme zusammenzuführen, um die Lösung für das größere Problem zu finden.

Die wichtigen Beispiele für Divide and Conquer-Algorithmen sind -

Zusammenführen, sortieren
Schnelle Sorte
Kruskals Minimal Spanning Tree-Algorithmus
Binäre Suche

Dynamische Programmierung

Bei der dynamischen Programmierung wird das größere Problem in kleinere unterteilt, im Gegensatz zum Teilen und Erobern wird jedoch nicht jedes Unterproblem einzeln gelöst. Vielmehr werden die Ergebnisse kleinerer Unterprobleme gespeichert und für ähnliche oder überlappende Unterprobleme verwendet. Meist werden diese Algorithmen zur Optimierung verwendet. Vor dem Lösen des vorliegenden Unterproblems versucht der dynamische Algorithmus, die Ergebnisse der zuvor gelösten Unterprobleme zu untersuchen.

Dynamische Algorithmen sind für eine Gesamtoptimierung des Problems und nicht für die lokale Optimierung motiviert.

Die wichtigen Beispiele für dynamische Programmieralgorithmen sind -

Fibonacci-Zahlenreihe
Rucksackproblem
Turm von Hanoi