Was sind algorithmische Paradigmen?

Wir sprechen im Allgemeinen über Programmierparadigmen als funktional, prozedural, objektorientiert, imperativ usw. Aber was soll ich antworten, wenn ich nach den Paradigmen der Algorithmen gefragt werde?

Zum Beispiel sind Travelling Salesman Problem, Dijkstra Shortest Path Algorithmus, Euclid GCD Algorithmus, Binäre Suche, Kruskals Minimum Spanning Tree, Tower of Hanoi algorithmische Paradigmen? Oder sind die Paradigmen vielleicht die Datenstrukturen, mit denen ich diese Algorithmen entwerfen würde?

Algorithmische Paradigmen sind :

Allgemeine Ansätze zur Konstruktion effizienter Problemlösungen

Jeder grundlegende, häufig verwendete Ansatz beim Entwerfen von Algorithmen könnte als algorithmisches Paradigma angesehen werden :

Teilen und erobern

Idee: Teilen Sie die Probleminstanz in kleinere Unterinstanzen desselben Problems auf, lösen Sie diese rekursiv und stellen Sie dann Lösungen für eine Lösung der angegebenen Instanz zusammen.

Beispiele: Mergesort, Quicksort, Strassens Algorithmus, FFT.

Gierige Algorithmen

Idee: Finden Sie eine Lösung, indem Sie immer die Wahl treffen, die im Moment optimal aussieht - schauen Sie nicht nach vorne, gehen Sie niemals zurück.

Beispiele: Prims Algorithmus, Kruskals Algorithmus.

Dynamische Programmierung

Idee: Rekursion auf den Kopf stellen.

Beispiel: Floyd-Warshall-Algorithmus für das Problem des kürzesten Pfades aller Paare.

Das Wort Paradigma lässt sich zwar in ein Beispiel übersetzen, aber so wird es in einem wissenschaftlichen Kontext nicht verwendet . Ihre Beispiele sind alle Beispiele für Algorithmen (mit Ausnahme des Problems des Handlungsreisenden, bei dem es sich um ein NP-hartes Problem handelt), von denen keines trivial genug ist, um als algorithmisches Paradigma betrachtet zu werden.

Common Design Algorithmic Paradigms:

• Teilen und Erobern : Ein Problem rekursiv in zwei oder mehr Unterprobleme desselben (oder verwandten) Typs aufteilen.
• Dynamische Programmierung : Aufteilung in eine Sammlung einfacherer Teilprobleme. Beispiel: Turm von Hanoi Puzzle
• Gieriger Algorithmus : Die Heuristik zur Problemlösung, in jeder Phase die lokal optimale Wahl zu treffen. Beispiel: Problem mit reisenden Verkäufern
• Backtracking : ist ein allgemeiner Algorithmus zum Finden aller (oder einiger) Lösungen für einige Rechenprobleme. Beispiel: Sudoku-Rätsel, das durch Backtracking gelöst wurde.
• Brute Force : Eine sehr allgemeine Technik zur Problemlösung, bei der alle möglichen Kandidaten für die Lösung systematisch aufgelistet und überprüft werden, ob jeder Kandidat die Aussage des Problems erfüllt.

Sie finden eine Reihe von Beispielen auf geeksforgeeks