Java Dynamic Programming bearbeiten Distanzproblem Beispielcode

Der dynamische Planungsprozess ist: Jede Entscheidung hängt vom aktuellen Zustand ab, und dann wird der Staat übertragen. Eine Entscheidungssequenz wird in einem sich ändernden Zustand generiert, sodass dieser Entscheidungsprozess für mehrstufige Optimierung als dynamische Programmierung bezeichnet wird.

Dynamische Programmierung ist eigentlich ein allgemeiner Begriff für eine Art von Thema, kein fester Algorithmus. Die Bedeutung der dynamischen Programmierung besteht darin, den Gesamtansatz zu lösen, indem rekursive (oder Divisions- und Eroberer-) Strategien und die Unterprobleme großer Probleme gelöst werden. Die Kernidee der dynamischen Programmierung besteht darin, das Problem geschickt in mehrere Unterprobleme aufzuteilen und die Gesamtlösung für das Problem durch Berechnung der Unterprobleme zu erhalten. Die Unterprobleme können in mehr Unterprobleme aufgeteilt werden, wodurch die erforderlichen Probleme unter Verwendung von Methoden gelöst werden, die der rekursiven Iteration ähneln. Frage Beschreibung:

Für die Sequenzen S und T ist der Abstand zwischen ihnen definiert als: die Ausführung der folgenden Operationen mehrmals auf einem der beiden: 1, löschen Sie ein Zeichen; 2, ein Zeichen einfügen; 3, ändere einen Charakter. Jedes Mal, wenn die Operation durchgeführt wird, wird die Anzahl durch 1. Mindestanzahl von Umdrehung und T in eine gleiche Sequenz erhöht. Bitte geben Sie den entsprechenden Algorithmus und seine Implementierung an.

analysieren:

Angenommen, die Längen der Sequenzen S und T sind m und n, und der Bearbeitungsabstand zwischen ihnen wird als Bearbeiten [m] [n] ausgedrückt. Dann gibt es die folgenden Situationen, wenn die Sequenz betrieben wird:

A. Wenn die Endzeichen von S und T gleich sind, ist für die Endzeichen keine der obigen Definitionsvorgänge (d. H. "Bearbeiten") erforderlich, dh keine Anzahl ist erforderlich. Die Bedingung ist erfüllt: Bearbeiten [m] [n] = Bearbeiten [M-1] [N-1].

B. Wenn die Endzeichen von S und T nicht gleich sind, muss das Ende eines von beiden bearbeitet werden, und die entsprechende Anzahl wird um 1 erhöht.

B1, modifizieren Sie das Ende von s oder t, um es gleich T oder S zu machen, und bearbeiten Sie dann [m] [n] = bearbeiten [m-1] [n-1] +1;

B2, löschen Sie das Element am Ende von S, um S und T gleich zu machen, und bearbeiten Sie dann [m] [n] = bearbeiten [m-1] [n] +1;

B3, löschen Sie das Element am Ende von T, um T und S gleich zu machen, und bearbeiten Sie dann [m] [n] = bearbeiten [m] [n-1] +1;

B4, fügen Sie das Schwanzelement von T am Ende von S hinzu, um S und T gleich zu machen, dann wird die Länge von S zu m+1, aber zu diesem Zeitpunkt sind die Endelemente von S und T bereits gleich. Sie müssen nur die ersten m-Elemente von S mit den ersten N-1-Elementen von T vergleichen, also bearbeiten Sie [m] [n] = bearbeiten [m] [n-1] +1;

B5, fügen Sie das Schwanzelement von S am Ende von T hinzu, um T und S gleich zu machen. Die Situation zu diesem Zeitpunkt ist die gleiche wie B4 und erfüllt Bearbeiten [m] [n] = Bearbeiten [M-1] [n] +1;

C. Ein Sonderfall ist, dass, wenn s leer ist, [0] [n] = n; und wenn t leer ist, bearbeiten Sie [m] [0] = m; Das ist leicht zu verstehen. Zum Beispiel ist für Sequenzen "" und "ABC" der minimale Betrieb von beiden 3, dh Sequenz "" 3 Einfügungsvorgänge oder Sequenz "ABC" durchführt 3 Löschvorgänge.

Daher ist es für uns nicht schwierig, die dynamische Programmiergleichung der oben genannten Bearbeitungsabstand abzuleiten:

Daher kann die rekursive Implementierung des dynamischen Programmieralgorithmus für den Bearbeitungsabstand von String im folgenden Java -Code ausgedrückt werden:

 public static int editDistance (Zeichenfolge A, Zeichenfolge b) {if (a == null || b == null) {return -1; } return editDistance (a, A.Length () - 1, b, b.Length () - 1); } public static int editDistance (Zeichenfolge A, int M, String B, int n) {if (m <0 || n <0) {return 1; } else if (a.charat (m) == b.charat (n)) {return editDistance (a, m - 1, b, n - 1); } else {return math.min (math.min (editDistance (a, m - 1, b, n) + 1, editDistance (a, m, b, n - 1) + 1), editDistance (a, m - 1, b, n - 1) + 1); }}

AKTUALISIEREN:

Gleichzeitig können wir aus der dynamischen Programmiergleichung der Bearbeitungsentfernung sehen, dass bearbeiten [m] [n] aus Bearbeiten [m - 1] [n - 1], bearbeiten [m - 1] [n], bearbeiten [m] [n - 1], und wenn Bearbeiten ein zweidimensionaler Array, links, bearbeiten [n] [n] können unter den Erkrankungen unter den oberen und oberen Position, links, und obere Position. Das heißt, wir können das zweidimensionale Array durchqueren und dann den Stromwert durch Backtracking berechnen.

Zum Beispiel wird für die Saiten s = "Sailn" und T = "Failing" das zweidimensionale Array initialisiert als:

Da s [0] = s, t [0] = f, dann s [0]! = T [0], dann entspricht die obige zweidimensionale Matrix, bearbeiten [1] [1] = min (bearbeiten [0] [0], bearbeiten [0] [1], bearbeiten [1] [0]) + 1 d.E. bearbeiten [1] [1].

Für s [1] = a, t [1] = a, s [1] = t [1] entspricht es einer zweidimensionalen Matrix, bearbeiten [2] [2] = Bearbeiten [1] [1], also bearbeiten Sie [2] [2] = 1. Also nach dieser Regel, füllen Sie die obige zweidimensionale Matrix wie folgt aus:

Daher ist der Bearbeitungsabstand zwischen den beiden Bearbeiten [m] [n] = bearbeiten [5] [7] = 3.

Daher kann nach der obigen Idee die Java -Version der Backtracking -Lösung der dynamischen Programmierung wie folgt durchgeführt werden:

 public static int editDistance (Zeichenfolge A, Zeichenfolge b) {if (a == null || b == null) {return -1; } int [] [] matrix = new int [a.Length () + 1] [b.Length () + 1]; für (int i = 0; i <A.Length ()+1; i ++) {für (int j = 0; j <B.Length ()+1; j ++) {if (i == 0) {matrix [i] [j] = j; } else if (j == 0) {matrix [i] [j] = i; } else {if (a.charat (i - 1) == b.charat (j - 1)) {matrix [i] [j] = matrix [i - 1] [j - 1]; } else {matrix [i] [j] = 1 + math.min (math.min (matrix [i - 1] [j], matrix [i] [j - 1]), matrix [i - 1]); }}} return Matrix [A.Length ()] [B.Length ()]; }

Zusammenfassen

Das obige ist der gesamte Inhalt dieses Artikels zum Beispiel -Beispielcode für die Distanzprobleme für Java -dynamische Programmierung. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen.