Este artículo describe el problema posterior común más largo (LCS) de los algoritmos Java. Compártelo para su referencia, como sigue:
Descripción del problema: Una subsecuencia de una secuencia dada es una secuencia obtenida después de que se eliminan varios elementos de la secuencia. Para ser precisos, si se le da la secuencia x = {x1, x2, ..., xm}, entonces otra secuencia z = {z1, z2, ..., zk} es una subsecuencia de x se refiere a la existencia de una secuencia de subíndice estrictamente incremental {i1, i2, ..., ik}, tal que para todas las j = 1,2, ... k hay xiJ. Por ejemplo, la secuencia Z = {B, C, D, B} es una subsecuencia de la secuencia x = {A, B, C, B, D, A, B}, y la secuencia de subíndice incremental correspondiente es {2,3,5,7}. Given two sequences X and Y, when the other sequence Z is both a subsequence of X and Y, Z is called a common subsequence of sequences X and Y. For example, if X= { A, B, C, B, D, A, B} and Y= {B, D, C, A, B, A}, then the sequence {B, C, A} is a common subsequence of X and Y, and the sequence {B, C, B, A} es también una subsecuencia común de X e Y. Además, esta última es una de las subsecuencias comunes más largas de X e Y, porque X e Y no tienen subsecuencias comunes de longitud mayor que 4. Dadas dos secuencias x = {x1, x2, ..., xm} e y = {y1, y2, ..., yn}, se requiere encontrar una de las subsecuencias comunes más largas de X e =.
Análisis de problemas: Sea x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a}. La forma más fácil de encontrar la posterior posterior más larga común de X e Y es el método exhaustivo. Para múltiples subsecuencias de X, verifique si también se trata de una subsecuencia de y, lo que determina si es una subsecuencia común de X e Y. A partir de las propiedades del conjunto, un conjunto con elementos M tiene un total de 2^m diferentes subsecuencias, por lo que el método exhaustivo requiere tiempo de operación exponencial. Despliue aún más las características del problema, el problema posterior común más largo en realidad tiene las propiedades óptimas de la subestructura.
Suponga la posterior subsecuencia común más larga de las secuencias x = {x1, x2, ... xm} e y = {y1, y2, ... yn} es z = {z1, z2, ... zk}. Luego están:
(1) Si xm = yn, entonces zk = xm = yn y zk-1 es la posterior posterior más larga común de XM-1 e YN-1.
(2) Si xm! = Yn y zk! = Xm, entonces z es la posterior subsecuencia común más larga de XM-1 e Y.
(3) Si xm! = Yn y zk! = Yn, entonces z es la posterior posterior más larga común de x e yn-1.
Donde, xm-1 = {x1, x2 ... xm-1}, yn-1 = {y1, y2 ... yn-1}, zk-1 = {z1, z2 ... zk-1}.
Relación recursiva: use c [i] [j] para registrar la longitud de la posterior subsecuencia común de las secuencias XI y YJ. Donde, xi = {x1, x2 ... xi}, yj = {y1, y2 ... yj}. Cuando i = 0 o j = 0, la secuencia vacía es la posterior subsecuencia común más larga de Xi e Yj. En este momento, c [i] [j] = 0; Cuando yo, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; Cuando yo, j> 0, xi! = yj,
c [i] [j] = max {c [i] [j-1], c [i-1] [j]}, estableciendo así la relación recursiva de la siguiente manera:
Construya la solución óptima: a partir del análisis anterior, podemos ver que para encontrar la subsecuencia común más larga de x = {x1, x2, ... xm} e y = {y1, y2, ... yn} puede realizar recursivamente de la siguiente manera: cuando xm = yn, encuentre la subsecuencia común más larga de XM-1 e ynn-1, y luego add the xm (= yn) a la cola más larga. Y. Cuando XM! = Yn, se deben resolver dos subproblemas, es decir, para encontrar una de las subsecuencias comunes más largas de XM-1 e Y y una de las sub-secuencias comunes más largas de X e Yn-1. La más larga de estas dos subsecuencias comunes es la posterior subsecuencia común más larga de X e Y. Supongamos que la matriz B [i] [j] registra el valor de c [i] [j] del que se obtiene subproblema. A partir de B [m] [n], busque en la matriz B de acuerdo con su valor. Cuando b [i] [j] = 1, la subsecuencia común más larga de Xi e Yj es la subsecuencia obtenida al agregar Xi a la cola de Xi-1 y Yj-1. Cuando b [i] [j] = 2, significa que la posterior subsecuencia común más larga de Xi e YJ es la misma que la posterior subsecuencia más larga de Xi-1 e YJ-1. Cuando B [i] [j] = 3, la posterior subsecuencia común más larga de Xi e Yj es la misma que la posterior posterior más larga de Xi y Yj-1.
El código es el siguiente:
paquete lcs; public class lcs {public static int [] [] lcslength (string [] x, string [] y) {int m = x.length; int n = y.length; int [] [] b = nuevo int [x.length] [y.length]; int [] [] c = new int [x.length] [y.length]; para (int i = 1; i <m; i ++) {c [i] [0] = 0; } para (int i = 1; i <n; i ++) {c [0] [i] = 0; } para (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 Resultados de la prueba:"); 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 posterior subsecuencia común más larga de x e y es:"); LCS (b, x, x.length - 1, y.length - 1); }}Resultados de ejecución:
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.