Gemeinsame Algorithmus-Designstrategien:
1. Teilen und erobern
Die Designidee des Teilens und Eroberns Die Methode besteht darin, ein großes Problem, das schwer direkt zu lösen ist, in k kleinere Teilprobleme zu unterteilen, die unabhängig voneinander und mit dem ursprünglichen Problem identisch sind, und dann jedes in „Teilen und Erobern“ zerlegen .
Die Divide-and-Conquer-Methode wird oft in Kombination mit Rekursion verwendet: Durch wiederholte Anwendung von Divide-and-Conquer kann das Unterproblem mit dem ursprünglichen Problemtyp in Einklang gebracht und der Maßstab kontinuierlich reduziert werden. Schließlich wird das Teilproblem so weit reduziert, dass es leicht zu lösen ist. Dies führt natürlich zu rekursiven Algorithmen.
2. Dynamische Programmierung
Die dynamische Programmiermethode ähnelt der Divide-and-Conquer-Methode und ihre Grundidee besteht darin, das ursprüngliche Problem in mehrere Teilbereiche zu zerlegen -Probleme. Im Gegensatz zur Divide-and-Conquer-Methode sind die zerlegten Teilprobleme häufig nicht unabhängig voneinander. In diesem Fall werden durch die Divide-and-Conquer-Methode einige Teilprobleme mehrmals gelöst, was offensichtlich unnötig ist. Die Methode der dynamischen Programmierung speichert die Antworten zu allen gelösten Teilproblemen während des Lösungsprozesses und vermeidet so ein wiederholtes Lösen von Teilproblemen.
Dynamische Programmierung wird häufig zur Lösung von Optimierungsproblemen eingesetzt. Ob die Methode der dynamischen Programmierung auf ein Optimierungsproblem angewendet werden kann, hängt davon ab, ob das Problem die folgenden zwei Eigenschaften aufweist:
Optimale Unterstruktureigenschaften:
Wenn die optimale Lösung des Problems seine Unterstruktur enthält Probleme Bei der optimalen Lösung von soll das Problem optimale Unterstruktureigenschaften haben.
Die überlappende Natur von Unterproblemen:
Die überlappende Natur von Unterproblemen bedeutet, dass die aus dem ursprünglichen Problem zerlegten Unterprobleme nicht unabhängig voneinander sind und sich überlappen.
3. Gierig
Wenn ein Problem optimale Unterstruktureigenschaften aufweist, kann es durch dynamische Programmierung gelöst werden. Aber manchmal gibt es einen Algorithmus, der einfacher, direkter und effizienter ist als die dynamische Programmierung – die Greedy-Methode. Die gierige Methode trifft im Moment immer die beste Wahl, was bedeutet, dass die gierige Methode nicht die insgesamt optimale Wahl berücksichtigt. Die von ihr getroffene Wahl ist in gewissem Sinne nur eine lokal optimale Wahl.
4. Backtracking
Die Backtracking-Methode besteht darin, eine Tiefensuche im Lösungsraumbaum des Problems durchzuführen, aber bevor DFS auf jedem Knoten durchgeführt wird Der Knoten muss zuerst beurteilt werden. Ist es möglich, eine Lösung für das Problem zu enthalten? Wenn es definitiv nicht enthalten ist, überspringen Sie die Suche nach dem Teilbaum, der an diesem Knoten wurzelt, und gehen Sie Schicht für Schicht zu seinen Vorgängerknoten zurück. Wenn es möglich ist, es einzudämmen, geben Sie den Unterbaum ein und führen Sie DFS durch.
5. Branch and Bound
Die Suchstrategie der Branch and Bound-Methode besteht darin, zunächst alle untergeordneten Knoten (Zweig) am aktuellen Knoten zu generieren Jeder untergeordnete Knoten, der die Einschränkungsbedingungen erfüllt, berechnet einen Funktionswert (gebunden), und dann werden alle untergeordneten Knoten, die die Einschränkungsbedingungen erfüllen, zur Live-Knoten-Prioritätswarteschlange des Lösungsraumbaums hinzugefügt. Wählen Sie dann den Knoten mit der höchsten Priorität aus der Prioritätswarteschlange des aktuellen Live-Knotens (die Priorität des Knotens wird durch den Wert seiner Grenzfunktion bestimmt) als neuen aktuellen Knoten aus. Dieser Vorgang wird wiederholt, bis ein Blattknoten erreicht ist. Der erreichte Blattknoten ist die optimale Lösung.
Das obige ist der detaillierte Inhalt vonWas sind die am häufigsten verwendeten Algorithmus-Designstrategien?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!