Cet article décrit le plus long problème de subséquence commun (LCS) des algorithmes Java. Partagez-le pour votre référence, comme suit:
Description du problème: Une sous-séquence d'une séquence donnée est une séquence obtenue après que plusieurs éléments sont supprimés de la séquence. Pour être précis, si l'on donne la séquence x = {x1, x2,…, xm}, alors une autre séquence z = {z1, z2,…, zk} est une sous-séquence de x se réfère à l'existence d'une séquence d'indice strictement incrémentielle {i1, i2,…, ik}, telles que pour tous j = 1,2,…, k y a xij = zj. Par exemple, la séquence Z = {b, c, d, b} est une sous-séquence de la séquence x = {a, b, c, b, d, a, b}, et la séquence d'indice incrémentale correspondante est {2,3,5,7}. Étant donné deux séquences x et y, lorsque l'autre séquence Z est à la fois une sous-séquence de x et y, z est appelée subséquence commune de séquences x et y. par exemple, si x = {a, b, c, b, d, a, b} et y = {b, d, c, a, b, a}, alors la séquence {b, c, a} est une subsomètre commun de x et y, et la séquence, b, a} est une élément commun de x et y, et la séquence, a, a} A} est également une sous-séquence courante de X et Y.
Analyse des problèmes: Soit x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a}. La façon la plus simple de trouver la plus longue sous-séquence commune de X et Y est la méthode exhaustive. Pour plusieurs sous-séquences de X, vérifiez s'il s'agit également d'une sous-séquence de Y, déterminant ainsi s'il s'agit d'une sous-séquence courante de X et Y. à partir des propriétés de l'ensemble, un ensemble avec des éléments M a un total de 2 ^ M sous-séquences différentes, de sorte que la méthode exhaustive nécessite un temps de fonctionnement exponentiel. Décomposer davantage les caractéristiques du problème, le plus long problème de subséquence commun a en fait les propriétés de substructure optimales.
Supposons la plus longue sous-séquence commune des séquences x = {x1, x2, ... xm} et y = {y1, y2, ... yn} est z = {z1, z2, ... zk}. Ensuite, il y a:
(1) Si xm = yn, alors zk = xm = yn, et zk-1 est la plus longue sous-séquence commune de XM-1 et Yn-1.
(2) Si xm! = Yn et zk! = Xm, alors z est la plus longue subséquence commune de XM-1 et Y.
(3) Si xm! = Yn et zk! = Yn, alors z est la plus longue subséquence commune de x et yn-1.
Où, xm-1 = {x1, x2… xm-1}, yn-1 = {y1, y2… yn-1}, zk-1 = {z1, z2… zk-1}.
Relation récursive: utilisez c [i] [j] pour enregistrer la longueur de la plus longue sous-séquence commune des séquences XI et YJ. Où, xi = {x1, x2… xi}, yj = {y1, y2… yj}. Lorsque i = 0 ou j = 0, la séquence vide est la plus longue sous-séquence commune de Xi et YJ. À ce moment, C [i] [J] = 0; Quand i, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; Quand je, j> 0, xi! = yj,
c [i] [j] = max {c [i] [j-1], c [i-1] [j]}, établissant ainsi la relation récursive comme suit:
Construisez la solution optimale: D'après l'analyse ci-dessus, nous pouvons voir que pour trouver la plus longue sous-séquence commune de x = {x1, x2, ... xm} et y = {y1, y2, ... yn}, vous pouvez effectuer de manière récursive de la manière suivante: lorsque xm = yn, trouvez la plus longue subséquence commune de XM-1 et ynet, puis ajouter xm (= yn) pour que la queue puisse le plus x et puis ajouter XM (= yn) pour que la queue puisse le plus x et puis ajoute XM (= Yn) pour que la queue puisse la longue Y. Lorsque XM! = YN, Deux sous-problèmes doivent être résolus, c'est-à-dire pour trouver l'une des plus longues sous-séquences communes de XM-1 et Y et l'une des plus longues sous-séquences communes de X et Yn-1. La plus longue de ces deux sous-séquences communes est la plus longue sous-séquence commune de X et Y. Supposons que le tableau B [i] [J] enregistre la valeur de C [i] [J] à partir duquel le sous-problème est obtenu. À partir de B [m] [n], recherchez dans le tableau B en fonction de sa valeur. Lorsque B [i] [J] = 1, la plus longue sous-séquence commune de Xi et Yj est la sous-séquence obtenue en ajoutant Xi à la queue de XI-1 et YJ-1. Lorsque b [i] [j] = 2, cela signifie que la plus longue sous-séquence commune de Xi et YJ est la même que la plus longue sous-séquence commune de XI-1 et YJ-1. Lorsque b [i] [j] = 3, la plus longue sous-séquence commune de Xi et Yj est la même que la plus longue sous-séquence commune de XI et YJ-1.
Le code est le suivant:
package 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]; pour (int i = 1; i <m; i ++) {c [i] [0] = 0; } pour (int i = 1; i <n; i ++) {c [0] [i] = 0; } pour (int i = 1; i <m; i ++) {for (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 Résultats du test:"); 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 ("La plus longue sous-séquence commune de X et Y est:"); Lcs (b, x, x.length - 1, y.length - 1); }}Résultats en cours:
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.