Dieser Artikel beschreibt das längste gemeinsame Subsequence -Problem (LCS) von Java -Algorithmen. Teilen Sie es für Ihre Referenz wie folgt weiter:
Problembeschreibung: Eine Untersequenz einer bestimmten Sequenz ist eine Sequenz, die nach mehreren Elementen aus der Sequenz gelöscht wird. Um genau zu sein, wenn die Sequenz x = {x1, x2,…, xm} angegeben ist, ist eine andere Sequenz Z = {z1, z2,…, Zk} eine SUBSEQUENZ von X ist auf die Existenz eines streng inkrementellen SubScript -Sequenz {i1, i2,…, ik}, so für alle j = 1,2, und so. Beispielsweise ist die Sequenz z = {b, c, d, b} eine Untersequenz der Sequenz x = {a, b, c, b, d, a, b}, und die entsprechende inkrementelle Abschlusssequenz ist {2,3,5,7}. Bei zwei Sequenzen x und y wird die andere Sequenz Z sowohl eine Untersequenz von x als auch y, z als gemeinsame Untersequenz von Sequenzen x und y bezeichnet. Wenn x = {a, b, c, b, d, a, b} und y = {b, d, c, a, b, a}, dann die Sequenz {b, c, {b, {b, {b, a}}}} ist ein}} -An -A -A -A -A -A -A -A -A -A -A -A -A -A -A -A -A -} und y. A} ist auch eine häufige Untersequenz von x und y. Darüber hinaus ist letzteres eine der längsten häufigen Untersequenzen von x und y, da x und y keine häufigen Länge von mehr als 4 Sequenzen aufweisen.
Problemanalyse: Sei x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a}. Der einfachste Weg, um die längste gemeinsame Untersequenz von x und y zu finden, ist die erschöpfende Methode. Überprüfen Sie bei mehreren Untersequenzen von x, ob es sich auch um eine Untersequenz von Y handelt, wodurch festgelegt wird, ob es sich um eine häufige Untersequenz von X und Y handelt. Aus den Eigenschaften des Satzes hat ein Satz mit Elementen m insgesamt 2 m verschiedene Subtonden, sodass die erschöpfende Methode eine exponentielle Betriebszeit erfordert. Weitere zersetzen die Problemmerkmale, das längste häufig vorkommende Subsequenzproblem weist tatsächlich die optimalen Unterkonstruktionseigenschaften auf.
Nehmen wir die längste gemeinsame Untersequenz der Sequenzen x = {x1, x2, ... xm} und y = {y1, y2, ... yn} IS z = {Z1, Z2, ... ZK}. Dann gibt es:
(1) Wenn xm = yn, dann ist ZK = xm = yn und ZK-1 die längste häufige Subsequenz von XM-1 und YN-1.
(2) Wenn xm! = Yn und zk!
(3) Wenn xm! = Yn und zk!
Wobei xm-1 = {x1, x2… xm-1}, yn-1 = {y1, y2… yn-1}, zk-1 = {z1, z2… ZK-1}.
Rekursive Beziehung: Verwenden Sie C [i] [j], um die Länge der längsten gemeinsamen Sequenz der Sequenzen XI und YJ aufzuzeichnen. Wo, xi = {x1, x2… xi}, yj = {y1, y2… yj}. Wenn i = 0 oder j = 0 ist, ist die leere Sequenz die längste häufige Untersequenz von Xi und YJ. Zu diesem Zeitpunkt C [i] [j] = 0; Wenn ich, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; Wenn ich, j> 0, xi! = yj,
c [i] [j] = max {c [i] [j-1], c [i-1] [j]}, wodurch die rekursive Beziehung wie folgt festgelegt wird:
Konstruieren Sie die optimale Lösung: Aus der obigen Analyse können wir sehen, dass die längste gemeinsame Untersequenz von x = {x1, x2, ... xm} und y = {y1, y2, ... yn}. Y. Wenn xm! Die längere dieser beiden gemeinsamen Subtonsen sind die längste gemeinsame Untersequenz von X und Y. Angenommen, das Array B [i] [j] zeichnet den Wert von c [i] [j] auf, aus dem das Teilproblem erhalten wird. Ausgehend von B [m] [n] suchen Sie in Array B nach seinem Wert. Wenn b [i] [j] = 1 ist, ist die längste gemeinsame Untersequenz von Xi und YJ die Untersequenz, die durch Zugabe von XI zum Schwanz von Xi-1 und YJ-1 erhalten wird. Wenn b [i] [j] = 2, bedeutet dies, dass die längste gemeinsame Untersequenz von Xi und YJ die gleiche ist wie die längste gemeinsame Subsequenz von Xi-1 und YJ-1. Wenn B [i] [j] = 3 ist, ist die längste gemeinsame Untersequenz von Xi und YJ die gleiche wie die längste gemeinsame Subsequenz von XI und YJ-1.
Der Code ist wie folgt:
Paket lcs; public class lcs {public static int [] [] lcsLength (String [] x, String [] y) {int m = x.Length; int n = y.length; int [] [] b = new int [X.Length] [Y.Length]; int [] [] c = new int [X.Length] [y.Length]; für (int i = 1; i <m; i ++) {c [i] [0] = 0; } für (int i = 1; i <n; i ++) {c [0] [i] = 0; } für (int i = 1; i <m; i ++) {für (int j = 1; j <n; j ++) {if (x [i] == y [j]) {c [i] [j] = c [i-1] [j-1]+1; B [i] [j] = 1; } else if (c [i-1] [j]> = c [i] [j-1]) {c [i] [j] = c [i-1] [j]; B [i] [j] = 2; } else {c [i] [j] = c [i] [j-1]; B [i] [j] = 3; }}} return b; } public static void lcs (int [] [] b, String [] x, int i, int j) {if (i == 0 || j == 0) return; if (b [i] [j] == 1) {lcs (b, x, i - 1, j - 1); System.out.print (x [i] + ""); } else if (b [i] [j] == 2) {lcs (b, x, i - 1, j); } else lcs (b, x, i, j-1); } public static void main (String args []) {System.out.println ("Wulin.com Testergebnisse:"); String [] x = {"", "A", "B", "C", "B", "D", "A", "B"}; String [] y = {"", "B", "D", "C", "A", "B", "A"}; int [] [] b = lcsLength (x, y); System.out.println ("Die längste gemeinsame Untersequenz von x und y ist:"); LCS (B, X, X.Length - 1, Y.Length - 1); }}Auslaufergebnisse:
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.