Fünf häufig verwendete Algorithmen

Fünf häufig verwendete Algorithmen

1. Greedy-Algorithmus

Der Greedy-Algorithmus kann die lokal optimale Lösung des Problems erhalten, muss jedoch nicht unbedingt die globale optimale Lösung erhalten. Gleichzeitig hängt die Qualität der Erzielung der optimalen Lösung von der Wahl der Greedy-Strategie ab. Das Merkmal ist, dass es einfach ist und lokal optimale Lösungen erhalten kann. Genau wie bei der Hundeschlagstock-Methode ist das Niveau von Hong Qigong und Lu Youjia für die gleichen Stockmethoden sehr unterschiedlich. Daher handelt es sich auch um einen gierigen Algorithmus, und unterschiedliche gierige Strategien führen zu sehr unterschiedlichen Ergebnissen.

2. Dynamischer Programmieralgorithmus

Wenn das Optimierungsproblem wiederholte Unterprobleme und optimale Unterstrukturen aufweist, ist es Zeit für das Erscheinen dynamischer Programmierung. Der Kern des dynamischen Programmieralgorithmus besteht darin, einen Speicher zum Zwischenspeichern der Ergebnisse wiederholter Teilprobleme bereitzustellen und so eine große Anzahl wiederholter Berechnungen im rekursiven Prozess zu vermeiden. Die Schwierigkeit des dynamischen Programmieralgorithmus besteht darin, das Problem in ein Problem umzuwandeln, das durch den dynamischen Programmieralgorithmus gelöst werden kann. Wenn die Anzahl der wiederholten Teilprobleme gering ist, ist der Effekt der dynamischen Programmierung gering. Wenn das Problem eine große Anzahl wiederholter Unterprobleme aufweist, ist die dynamische Programmierung für die Verbesserung der Effizienz sehr schlecht. Genau wie bei den Kampfkünsten gilt: Wenn der Gegner stark ist, wird er stärker sein; wenn der Gegner stärker ist, wird er schwächer sein.

3. Divide and Conquer-Algorithmus

Die Logik des Divide and Conquer-Algorithmus ist einfacher, es ist nur ein Wort: teile und herrsche. Der Divide-and-Conquer-Algorithmus besteht darin, ein großes Problem in mehrere Unterprobleme zu unterteilen und die Unterprobleme dann weiter nach unten zu unterteilen, bis hin zu den Basisfällen, und zwar durch die Lösung der Basisfälle, Schritt für Schritt nach oben Und schließlich das ursprüngliche große Problem lösen. Der Divide-and-Conquer-Algorithmus ist eine typische Anwendung der Rekursion.

4. Backtracking-Algorithmus

Der Backtracking-Algorithmus ist eine typische Anwendung der Tiefenstrategie anders, dann zurückgehen Gehen Sie zur vorherigen

gegabelten Straße, wählen Sie einen Weg aus und rekursieren Sie so weiter, bis alle Pfade durchlaufen sind. Das Eight Queens-Problem ist ein klassisches Problem des Backtracking-Algorithmus, und ein weiteres klassisches Anwendungsszenario ist das Labyrinthproblem.

5. Branch-and-Bound-Algorithmus

Der Backtracking-Algorithmus ist die Tiefe zuerst, daher ist die Branch-and-Bound-Methode ein klassisches Beispiel für die Breite zuerst . Im Allgemeinen durchläuft die Backtracking-Methode den gesamten Lösungsraum, um alle Lösungen für das Problem zu erhalten, während die Branch-and-Bound-Methode darin besteht, eine Lösung zu erhalten (im Allgemeinen die optimale Lösung zu erhalten).

Empfohlenes Tutorial: „PHP-Tutorial“

Das obige ist der detaillierte Inhalt vonFünf häufig verwendete Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!