Welches sind die fünf am häufigsten verwendeten Algorithmen?

Zu den häufig verwendeten Algorithmen gehören: 1. Divide-and-Conquer-Methode; 2. Greedy-Algorithmus, eine einfachere und schnellere Entwurfstechnologie für bestimmte optimale Lösungsprobleme; 4. Backtracking-Methode; Suchmethode; 5. Branch-and-Bound-Methode.

Die fünf am häufigsten verwendeten Algorithmen sind: Divide-and-Conquer-Methode, Greedy-Algorithmus, dynamischer Programmieralgorithmus, Backtracking-Methode und Branch-and-Bound-Methode.

Was ist ein Algorithmus?

Algorithmus bezieht sich auf eine genaue und vollständige Beschreibung einer Problemlösung. Es handelt sich um eine Reihe klarer Anweisungen zur Lösung von Problemen Probleme.

Es versteht sich, dass ein Algorithmus eine Reihe von Schritten zur Lösung eines bestimmten Problems ist. Der Algorithmus muss die folgenden drei wichtigen Merkmale aufweisen:

1. Nach der Ausführung einer endlichen Anzahl von Schritten muss der Algorithmus terminieren.

2. Genauigkeit. Jeder Schritt des Algorithmus muss genau definiert sein.

3. Machbarkeit. Ein bestimmter Algorithmus muss in der Lage sein, ein bestimmtes Problem in einer bestimmten Zeitspanne zu lösen.

Die fünf am häufigsten verwendeten Algorithmen

Teile-und-herrsche-Methode

Die Teile-und-herrsche-Methode Die Methode besteht darin, ein komplexes Problem in zwei oder mehr identische oder ähnliche Unterprobleme zu unterteilen, und dann werden die Unterprobleme in kleinere Unterprobleme unterteilt ... bis die Unterprobleme schließlich einfach und direkt gelöst werden können. und die Lösung des ursprünglichen Problems ist die Zusammenführung der Lösungen der Teilprobleme.

Probleme, die mit der Divide-and-Conquer-Methode gelöst werden können, weisen im Allgemeinen die folgenden Merkmale auf:

1) Das Problem kann leicht gelöst werden, wenn der Umfang des Problems auf a reduziert wird gewissermaßen;

2). Dieses Problem kann in mehrere kleinere identische Probleme zerlegt werden, das heißt, das Problem hat optimale Unterstruktureigenschaften; Das Problem kann zu einer Lösung für dieses Problem zusammengefasst werden.

4) Jedes durch dieses Problem zerlegte Unterproblem ist unabhängig voneinander, das heißt, es gibt keine gemeinsamen Unterprobleme zwischen den Unterproblemen. Probleme.

Greedy-Algorithmus

Der Greedy-Algorithmus ist eine einfachere und schnellere Entwurfstechnologie für bestimmte optimale Lösungsprobleme.

Der gierige Methodenentwurfsalgorithmus zeichnet sich dadurch aus, dass er Schritt für Schritt vorgeht. Er trifft häufig optimale Entscheidungen auf der Grundlage der aktuellen Situation und basiert auf einer Optimierungsmaßnahme, ohne dass verschiedene mögliche Gesamtsituationen berücksichtigt werden müssen Eine optimale Lösung muss viel Zeit in Anspruch nehmen, um alle Möglichkeiten auszuschöpfen. Sie verwendet Top-Down- und iterative Methoden, um aufeinanderfolgende gierige Entscheidungen zu treffen und das gewünschte Problem in eine kleinere Teilmenge zu zerlegen Durch die gierige Auswahl kann bei jedem Schritt eine optimale Lösung für das Problem erhalten werden. Obwohl garantiert ist, dass bei jedem Schritt eine lokal optimale Lösung erhalten wird, ist die resultierende globale Lösung manchmal nicht unbedingt optimal, sodass der gierige Algorithmus keine Rückverfolgung durchführt.

Dynamischer Programmieralgorithmus

Dynamische Programmierung ist eine Methode, die in der Mathematik und Informatik zur Lösung von Optimierungsproblemen verwendet wird, die überlappende Teilprobleme enthalten. Die Grundidee besteht darin, das ursprüngliche Problem in ähnliche Teilprobleme zu zerlegen und im Prozess der Problemlösung die Lösung des ursprünglichen Problems durch die Lösungen der Teilprobleme zu erhalten. Die Idee der dynamischen Programmierung ist die Grundlage vieler Algorithmen und wird in den Bereichen Informatik und Ingenieurwesen häufig verwendet.

Dynamische Programmiermethoden werden normalerweise verwendet, um Optimierungsprobleme zu lösen. Jede Lösung mit dem optimalen Wert wird stattdessen als optimale Lösung bezeichnet Von der optimalen Lösung kann es mehrere Lösungen geben, die alle den optimalen Wert erreichen.

Schritte beim Entwurf eines dynamischen Programmieralgorithmus:

1), charakterisieren die strukturellen Eigenschaften einer optimalen Lösung

2), rekursiv den Wert der optimalen Lösung definieren

3), berechnen Sie den Wert der optimalen Lösung, normalerweise unter Verwendung der Bottom-up-Methode

4), verwenden Sie die berechneten Informationen, um eine optimale Lösung zu konstruieren

Dynamische Programmierung und Division -und-herrsche-Methode Ähnlich wie bei der Lösung des ursprünglichen Problems werden die Lösungen der Teilprobleme kombiniert, um die Lösung des ursprünglichen Problems zu lösen. Der Unterschied zur Teile-und-herrsche-Methode besteht darin, dass die Teilprobleme des Die Teile-und-Herrsche-Methode existiert unabhängig voneinander, während die dynamische Programmierung angewendet wird, wenn sich die Teilprobleme überschneiden.

Backtracking-Methode

Die Backtracking-Methode (Explorations- und Backtracking-Methode) ist eine optimale Suchmethode, die nach den optimalen Bedingungen vorwärts sucht, um das Ziel zu erreichen. Aber wenn Sie einen bestimmten Schritt in der Erkundung erreichen und feststellen, dass die ursprüngliche Wahl nicht optimal ist oder das Ziel nicht erreichen kann, werden Sie einen Schritt zurücktreten und eine andere Wahl treffen. Diese Technik des Zurückgehens und erneuten Versuchens, wenn sie nicht funktioniert die Backtracking-Methode und der Punkt in einem bestimmten Zustand, der die Backtracking-Bedingungen erfüllt. Wird als „Lookback-Punkt“ bezeichnet.

Die Grundidee besteht darin, den Lösungsraumbaum ausgehend vom Wurzelknoten gemäß der Tiefensuchstrategie im Lösungsraumbaum, der alle Lösungen des Problems enthält, gründlich zu untersuchen. Wenn ein Knoten untersucht wird, muss zunächst festgestellt werden, ob der Knoten die Lösung für das Problem enthält. Wenn dies der Fall ist, fahren Sie mit der Erkundung von diesem Knoten aus fort Vorfahren. Knoten-Backtracking.

Branch-and-Bound-Methode

Die Branch-and-Bound-Methode ist ein sehr weit verbreiteter Algorithmus. Die Verwendung dieses Algorithmus ist sehr geschickt und es gibt verschiedene Arten von Problemlösungen verschiedene Methoden. Nicht dasselbe.

Die Grundidee der Branch-and-Bound-Methode besteht darin, den Raum aller möglichen Lösungen (eine begrenzte Anzahl) des Optimierungsproblems mit Einschränkungen zu durchsuchen. Wenn der Algorithmus speziell ausgeführt wird, wird der gesamte mögliche Lösungsraum kontinuierlich in immer kleinere Teilmengen (Zweige genannt) unterteilt und eine untere oder obere Grenze (Abgrenzung genannt) für den Wert der Lösung in jeder Teilmenge berechnet. Nach jeder Verzweigung werden keine weiteren Verzweigungen zu den Teilmengen vorgenommen, deren Grenzen den bekannten zulässigen Lösungswert überschreiten. Auf diese Weise können viele Teilmengen der Lösung (d. h. viele Knoten im Suchbaum) ignoriert werden, wodurch die Suche eingegrenzt wird Umfang. Dieser Prozess wird fortgesetzt, bis eine zulässige Lösung gefunden wird, deren Wert nicht größer als die Grenzen einer Teilmenge ist. Daher kann dieser Algorithmus im Allgemeinen die optimale Lösung erhalten.

Das obige ist der detaillierte Inhalt vonWelches sind die fünf am häufigsten verwendeten Algorithmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!