Fünf klassische Computeralgorithmen: 1. Divide-and-Conquer-Methode, die ein komplexes Problem in zwei oder mehr identische oder ähnliche Teilprobleme unterteilt; 3. Greedy-Algorithmus; 4. Die optimale Suche; Die Methode sucht nach den optimalen Bedingungen, um das Ziel zu erreichen. 5. Branch-and-Bound-Methode.
Die Betriebsumgebung dieses Tutorials: Windows 10-System, Dell G3-Computer.
Ich fange gerade an, Lebensläufe einzureichen und nach Praktika zu suchen. Ich weiß immer noch nicht, wie ich etwas machen soll, also gerate ich in Panik. Ab heute werde ich mehr als 2 Leetcodes putzen und sie dann zusammenfassen. und fasse die Wissenspunkte verschiedener Interviewfragen zusammen.
Als ich mit Leetcode beschäftigt war, sah ich oft, wie Leute über DP sprachen. Dann ging ich zu Baidu, um herauszufinden, was DP ist, und dann wurde mir klar, dass DP einer der fünf klassischen Algorithmen ist .
Die fünf klassischen Algorithmen sind unterteilt in
1. Divide-and-Conquer-Methode: Teilen Sie ein komplexes Problem in zwei oder mehr identische oder ähnliche Teilprobleme und teilen Sie die Teilprobleme dann in kleinere Teilprobleme auf. .. Bis zum Ende können die Teilprobleme einfach und direkt gelöst werden, und die Lösung des ursprünglichen Problems ist die Zusammenführung der Lösungen der Teilprobleme.
2. Dynamische Programmiermethode: Jede Entscheidung hängt vom aktuellen Zustand ab und führt sofort zu einem Zustandsübergang. Eine Entscheidungssequenz wird in einem sich ändernden Zustand generiert, daher wird dieser mehrstufige Optimierungsentscheidungsprozess zur Lösung von Problemen als dynamische Programmierung bezeichnet.
3. Greedy-Algorithmus: Treffen Sie bei der Lösung eines Problems immer die aktuell beste Wahl. Mit anderen Worten, ohne die Berücksichtigung der insgesamt optimalen Lösung war das, was er machte, in gewissem Sinne nur eine lokal optimale Lösung. Zu den gängigen Greedy-Algorithmen gehören: Prim-Algorithmus und Kruskal-Algorithmus (beide suchen nach minimalen Spannbäumen).
Grundidee: Zerlegen Sie das Problem in mehrere kleine Probleme, erhalten Sie nach und nach die lokal optimale Lösung für jedes Teilproblem und fügen Sie sie schließlich zur Lösung des ursprünglichen Problems zusammen.
4. Backtracking-Methode: Der Backtracking-Algorithmus ist eigentlich ein Aufzählungs-ähnlicher Suchversuchsprozess. Er sucht hauptsächlich nach der Lösung des Problems, wenn festgestellt wird, dass die Lösungsbedingungen nicht mehr erfüllt sind. „Backtrack“ und kehren Sie zurück, um etwas anderes auszuprobieren. Pfad. Bei der retrospektiven Methode handelt es sich um eine Auswahlsuchmethode, bei der nach den Auswahlbedingungen gesucht wird, 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 funktioniert nicht ist die Backtracking-Methode, und der Punkt in einem bestimmten Zustand, der die Backtracking-Bedingungen erfüllt, wird als „Backtracking-Punkt“ bezeichnet.
5. Branch-and-Bound-Methode: Ähnlich wie die Backtracking-Methode ist es auch ein Algorithmus, der im Lösungsraumbaum T des Problems nach der Lösung des Problems sucht. Im Allgemeinen sind die Lösungsziele der Branch-and-Bound-Methode und der Backtracking-Methode jedoch unterschiedlich. Das Lösungsziel der Backtracking-Methode besteht darin, alle Lösungen in T zu finden, die die Einschränkungsbedingungen erfüllen, während das Lösungsziel der Branch-and-Bound-Methode darin besteht, eine Lösung zu finden, die die Einschränkungsbedingungen erfüllt, oder eine Lösung zu finden, die die Einschränkung erfüllt Bedingungen, damit ein bestimmtes Ziel erreicht wird Der Funktionswert erreicht die maximale oder minimale Lösung, die in gewissem Sinne die optimale Lösung ist.
1. Divide-and-Conquer-Methode Die 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 das Ausmaß des Problems verringert wird bis zu einem gewissen Grad
2) Das Problem kann in mehrere kleinere identische Probleme zerlegt werden, das heißt, das Problem weist optimale Unterstruktureigenschaften auf.
3) Die Lösungen der durch dieses Problem zerlegten Unterprobleme können zur Lösung dieses Problems kombiniert werden
4) Die aus diesem Problem zerlegten Unterprobleme sind unabhängig voneinander, das heißt, die Unterprobleme enthalten keine allgemeinen Unterfragen.
Wenn Sie nicht über das dritte Merkmal verfügen, können Sie die Verwendung der dynamischen Programmierung (DP) oder der Greedy-Methode in Betracht ziehen.
Wenn Sie nicht über das vierte Merkmal verfügen, können Sie die Verwendung dynamischer Programmierung in Betracht ziehen.
Grundlegende Schritte der Divide-and-Conquer-Methode:
Schritt 1 Zerlegung: Zerlegen Sie das ursprüngliche Problem in mehrere kleinere, unabhängige Teilprobleme mit derselben Form wie das ursprüngliche Problem.
Schritt 2 Lösung: Wenn das Teilproblem klein ist Größe und einfache Lösung, dann direkt lösen, andernfalls jedes Unterproblem rekursiv lösen
Schritt 3 Zusammenführen: Kombinieren Sie die Lösungen jedes Unterproblems zur Lösung des ursprünglichen Problems.
2. Der größte Unterschied zwischen der dynamischen Programmiermethode
und der Divide-and-Conquer-Methode besteht darin, dass bei Problemen, die für die Lösung durch die dynamische Programmiermethode geeignet sind, die nach der Zerlegung erhaltenen Teilprobleme dies häufig nicht sind unabhängig voneinander (d. h. das nächste Unterproblem Die Lösung jeder Stufe basiert auf der Lösung der vorherigen Unterstufe zur weiteren Lösung).
Anwendbare Bedingungen:
Probleme, die durch dynamische Programmierung gelöst werden können, haben im Allgemeinen drei Eigenschaften:
(1) Optimierungsprinzip: Wenn die Lösung des in der optimalen Lösung des Problems enthaltenen Teilproblems auch optimal ist, ist The Man sagt, dass das Problem eine optimale Unterstruktur hat, das heißt, es erfüllt das Optimierungsprinzip.
(2) Keine Nachwirkung: Das heißt, sobald der Zustand einer bestimmten Stufe bestimmt ist, wird er von nachfolgenden Entscheidungen in diesem Zustand nicht beeinflusst. Mit anderen Worten: Der Prozess nach einem bestimmten Zustand hat keinen Einfluss auf den vorherigen Zustand, sondern bezieht sich nur auf den aktuellen Zustand.
(3) Es gibt überlappende Unterprobleme: Das heißt, die Unterprobleme sind nicht unabhängig und ein Unterproblem kann in der nächsten Entscheidungsphase mehrfach verwendet werden. (Diese Eigenschaft ist keine notwendige Bedingung für die Anwendung der dynamischen Programmierung, aber ohne diese Eigenschaft hat der dynamische Programmieralgorithmus keine Vorteile gegenüber anderen Algorithmen.)
Fall:
Es gibt n Schritte und eine Person geht einen hinauf Stellen Sie jedes Mal eine Stufe oder zwei Stufen, fragen Sie, wie viele Möglichkeiten es gibt, n Stufen hinaufzugehen.
Analyse: Der Schlüssel zur Implementierung der dynamischen Programmierung liegt darin, ob die dynamische Programmiertabelle genau und sinnvoll zur Abstraktion praktischer Probleme verwendet werden kann. In diesem Problem sei f(n) die Anzahl der Wege, um n Schritte nach oben zu gehen.
Wenn n 1 ist, ist f(n) = 1, wenn n 2 ist, ist f(n) = 2, das heißt, wenn es nur einen Schritt gibt, ist die Anzahl der Methoden eins, und es gibt sie Zwei Schritte. Zu diesem Zeitpunkt beträgt die Anzahl der Methoden 2. Wenn wir also n Schritte nach oben gehen wollen, müssen wir einen Schritt von n-1 Schritten oder zwei Schritte von n-2 Schritten machen, also muss die Anzahl der Wege, um n Schritte zu erreichen, der Zahl der Methode zum Erreichen von n-1 Schritten plus sein die Summe der Anzahl der Wege, um n-2 Schritte zu erreichen. Das heißt, f(n) = f(n-1)+f(n-2), wir verwenden dp[n], um die dynamische Programmiertabelle darzustellen, dp[i],i>0,i<=n, was angibt Erreichen von Level i Die Anzahl der Schritte.
int fun(int n){
if (n==1||n==2)
return n;
/*判断n-1的状态有没有被计算过*/
if (!dp[n-1])
dp[n-1] = fun(n-1);
if(!dp[n-2])
dp[n-2]=fun(n-2);
return dp[n-1]+dp[n-2];
}Nach dem Login kopieren
3. Greedy-Algorithmus
Der Greedy-Algorithmus bedeutet, dass man bei der Lösung eines Problems immer die aktuell beste Wahl trifft. Mit anderen Worten, wir betrachten nicht die insgesamt optimale Lösung, sondern erstellen nur in gewissem Sinne eine lokal optimale Lösung. Der Greedy-Algorithmus erhält nicht für alle Probleme die optimale Gesamtlösung. Der Schlüssel liegt in der Auswahl der Greedy-Strategie. Die ausgewählte Greedy-Strategie darf keine Nachwirkungen haben, d bezieht sich nur auf den aktuellen Stand.
Die allgemeinen Schritte zur Lösung von Problemen sind:
1. Erstellen Sie ein mathematisches Modell zur Beschreibung des Problems.
2. Teilen Sie das zu lösende Problem in mehrere Teilprobleme auf des Teilproblems;
4. Kombinieren Sie die lokal optimale Lösung des Teilproblems zu einer Lösung des ursprünglichen Problems.
Beispiel: Geldwechselproblem
Dieses Problem kommt in unserem täglichen Leben häufiger vor. Angenommen, es gibt c0-, c1-, c2-, c3-, c4-, c5- und c6-Banknoten zu 1 Yuan, 2 Yuan, 5 Yuan, 10 Yuan, 20 Yuan, 50 Yuan bzw. 100 Yuan. Wie viele Banknoten müssen mindestens verwendet werden, um mit diesem Geld K Yuan zu bezahlen? Unter Verwendung der Idee eines gierigen Algorithmus ist es offensichtlich, dass in jedem Schritt möglichst nur Banknoten mit einem großen Nennwert verwendet werden können. Wir tun dies natürlich in unserem täglichen Leben. Die Werte wurden im Programm in aufsteigender Reihenfolge angeordnet.
public class charge {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int res = charge(84);
System.out.println(res);
}
private static int charge(int money) {
int count = 0;
int value[] = {50,20,10,5,2,1};
while(money>0){
int length = value.length;
for(int i=0;i=value[i]){
money=money-value[i];
count++;
//System.out.println(money);
}
}
}
return count;
}
}
4. Backtracking-Methode
Die Backtracking-Methode ist eine Methode zur systematischen Suche nach Lösungen für Probleme. Versuchen Sie während des Suchvorgangs, die Lösung für das Problem zu finden. Wenn Sie feststellen, dass Sie sie nicht finden können, gehen Sie einen Schritt zurück und gehen Sie zurück nach oben (Bereinigungsprozess). Backtracking kann für viele komplexe und umfangreiche Probleme eingesetzt werden. Die Grundidee der Backtracking-Methode besteht darin, der Tiefensuchstrategie zu folgen und die Suche vom Wurzelknoten aus zu starten. Wenn dies der Fall ist, muss festgestellt werden, ob dieser die Lösung des Problems enthält enthalten, setzen Sie die Suche von diesem Knoten aus fort. Wenn er nicht enthalten ist, suchen Sie zurück zum übergeordneten Knoten. Wenn die Backtracking-Methode verwendet wird, um alle Lösungen des Problems zu finden, muss sie bis zur Wurzel zurückverfolgt werden und alle möglichen Teilbäume des Wurzelknotens müssen vor dem Beenden durchsucht worden sein. Und wenn Sie die Backtracking-Methode verwenden, um eine Lösung zu finden, können Sie aufhören, solange Sie eine Lösung für das Problem finden.
Beschneidungsfunktionen, die üblicherweise in der Backtracking-Methode verwendet werden: (1) Einschränkungsfunktion: Subtrahieren Sie Teilbäume, die die Einschränkungen am Knoten nicht erfüllen. (2) Grenzfunktion: Subtrahieren Sie Teilbäume, die nicht die optimale Lösung erhalten können. Allgemeine Schritte: 1. Bestimmen Sie den Lösungsraum des Problems 2. Verwenden Sie für die Suche geeignete Methoden, um den Lösungsraum zu organisieren
4. Verwendung während des Suchvorgangs. Bereinigungsfunktionen vermeiden ungültige Suchen.
5. Die Branch-and-Bound-Methode ähnelt der Backtracking-Methode. Es handelt sich ebenfalls um einen Algorithmus, der im Lösungsraumbaum T des Problems nach der Lösung des Problems sucht. Im Allgemeinen sind die Lösungsziele der Branch-and-Bound-Methode und der Backtracking-Methode jedoch unterschiedlich. Das Lösungsziel der Backtracking-Methode besteht darin, alle Lösungen in T zu finden, die die Einschränkungsbedingungen erfüllen, während das Lösungsziel der Branch-and-Bound-Methode darin besteht, eine Lösung zu finden, die die Einschränkungsbedingungen erfüllt, oder eine Lösung zu finden, die die Einschränkung erfüllt Bedingungen, damit ein bestimmtes Ziel erreicht wird Der Funktionswert erreicht die maximale oder minimale Lösung, die in gewissem Sinne die optimale Lösung ist.
(1) Zweigsuchalgorithmus
Der sogenannte „Zweig“ besteht darin, die Breitenstrategie zu verwenden, um alle Zweige des E-Knotens nacheinander zu durchsuchen, dh alle benachbarten Knoten, und die Knoten zu verwerfen, die dies nicht tun Erfüllen Sie die Einschränkungen und klicken Sie auf die verbleibenden Knoten, um der Slipknot-Tabelle beizutreten. Wählen Sie dann einen Knoten aus der Tabelle als nächsten E-Knoten aus und setzen Sie die Suche fort.
Je nachdem, wie der nächste E-Knoten ausgewählt wird, gibt es verschiedene Methoden zur Zweigsuche.
1) FIFO-Suche
2) LIFO-Suche
3) Prioritätswarteschlangensuche
(2) Branch-and-Bound-Suchalgorithmus
Der allgemeine Prozess der Branch-and-Bound-Methode Aufgrund unterschiedlicher Lösungsziele verfügen die Branch-and-Bound-Methode und die Backtracking-Methode über unterschiedliche Suchmethoden im Lösungsraumbaum T. Die Backtracking-Methode durchsucht den Lösungsraumbaum T nach der Tiefe zuerst, während die Branch-and-Bound-Methode den Lösungsraumbaum T nach der Breite zuerst oder nach den geringsten Kosten zuerst durchsucht.
Die Suchstrategie der Branch-and-Bound-Methode lautet: Generieren Sie am Erweiterungsknoten zunächst alle untergeordneten Knoten (Zweig) und wählen Sie dann das nächste Erweiterungspaar aus der aktuellen Live-Knotentabelle aus. Um den nächsten Erweiterungsknoten effektiv auszuwählen und den Suchvorgang zu beschleunigen, wird an jedem Live-Knoten ein Funktionswert (Grenze) berechnet und basierend auf diesen berechneten Funktionswerten wird ein bester Wert aus der aktuellen Live-Knoten-Tabelle ausgewählt. Günstige Knoten dienen als Erweiterungsknoten, um die Suche in Richtung des Zweigs mit der optimalen Lösung im Lösungsraumbaum voranzutreiben und so schnellstmöglich eine optimale Lösung zu finden.
Die Branch-and-Bound-Methode durchsucht den Lösungsraumbaum des Problems oft nach der Breite zuerst oder nach minimalen Kosten (maximaler Nutzen). Der Lösungsraumbaum eines Problems ist ein geordneter Baum, der den Lösungsraum des Problems darstellt. Zu den häufigsten gehören Teilmengenbäume und Permutationsbäume. Beim Durchsuchen des Lösungsraumbaums eines Problems verwenden die Branch-and-Bound-Methode und die Backtracking-Methode unterschiedliche Erweiterungsmethoden für den aktuellen Erweiterungsknoten. Bei der Branch-and-Bound-Methode hat jeder Live-Knoten nur eine Chance, ein Erweiterungsknoten zu werden. Sobald ein Live-Knoten zu einem erweiterten Knoten wird, werden alle seine untergeordneten Knoten auf einmal generiert. Von diesen untergeordneten Knoten werden diejenigen verworfen, die zu undurchführbaren oder nicht optimalen Lösungen führen, und die verbleibenden untergeordneten Knoten werden zur Liste der aktiven Knoten hinzugefügt. Anschließend wird ein Knoten aus der Live-Knotentabelle zum aktuellen Erweiterungsknoten genommen und der obige Knotenerweiterungsprozess wird wiederholt. Dieser Vorgang wird fortgesetzt, bis die gewünschte Lösung gefunden wird oder die Liveknot-Tabelle leer ist.
Einige Unterschiede zwischen der Backtracking-Methode und der Branch-and-Bound-Methode
Einige Probleme können tatsächlich entweder mit der Backtracking-Methode oder der Branch-and-Bound-Methode gut gelöst werden, andere jedoch nicht. Vielleicht benötigen wir eine spezifischere Analyse – wann sollten wir Branch and Bound und wann Backtracking verwenden?
Einige Unterschiede zwischen der Backtracking-Methode und der Branch-and-Bound-Methode:
Die Suchmethode der Methode für den Lösungsraumbaum Gemeinsame Datenstrukturen zum Speichern von Knoten Gemeinsame Anwendungen von Knotenspeicherfunktionen
Die Backtracking-Methode durchsucht zuerst alle möglichen Sub -Knoten des Stapels Live-Knoten Nachdem die Punkte durchlaufen wurden, werden sie vom Stapel entfernt, um alle Lösungen herauszufinden, die die Einschränkungen erfüllen
Verzweigungs- und Bindungsmethode Breite erste oder minimale Verbrauchsprioritätssuchwarteschlange, Prioritätswarteschlange Jeder Knoten hat nur Eine Chance, ein Live-Knoten zu werden, um herauszufinden, dass die Einschränkungen erfüllt sind. Eine Lösung oder die optimale Lösung in einem bestimmten Sinne.
Weitere Informationen zu diesem Thema finden Sie in der Spalte „FAQ“!
Das obige ist der detaillierte Inhalt vonWas sind die fünf klassischen Computeralgorithmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
