Este artigo descreve o mais longo problema de subseqüência (LCS) dos algoritmos Java. Compartilhe -o para sua referência, como segue:
Descrição do problema: Uma subsequência de uma determinada sequência é uma sequência obtida após vários elementos são excluídos da sequência. Para ser preciso, se for dada a sequência x = {x1, x2,…, xm}, então outra sequência z = {z1, z2,…, zk} é uma subseqüência de x refere -se à existência de uma sequência subscrita estritamente incremental {i1,…,…, ik}, como tudo j = 1,12. Por exemplo, a sequência z = {b, c, d, b} é uma subseqüência da sequência x = {a, b, c, b, d, a, b} e a sequência incremental correspondente é {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} também é uma subsequência comum de x e y. Além disso, o último é uma das subsequências mais comuns de X e Y, porque xey não possui subsequences comuns de comprimento maior que 4. Dadas duas seqüências x = {x1, x2,…, xm} e y = {y1, y2,…, yn}, é necessário para fina
Análise do problema: Seja x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a}. A maneira mais fácil de encontrar a subsequência mais comum de X e Y é o método exaustivo. Para múltiplas subseqüências de x, verifique se também é uma subsequência de y, determinando assim se é uma subsequência comum de x e y. A partir das propriedades do conjunto, um conjunto com elementos m tem um total de 2^m subsequences diferentes; portanto, o método exaustivo requer tempo de operação exponencial. Decompõe ainda as características do problema, o mais longo problema de subsequência comum realmente possui as propriedades ideais da subestrutura.
Suponha que a subsequência mais comum das seqüências x = {x1, x2, ... xm} e y = {y1, y2, ... yn} é z = {z1, z2, ... zk}. Então há:
(1) Se xm = yn, então zk = xm = yn e zk-1 é a subsequência comum mais longa de XM-1 e YN-1.
(2) Se xm! = Yn e zk! = Xm, então z é a subsequência mais comum de XM-1 e Y.
(3) Se xm! = Yn e zk! = Yn, então z é a subsequência mais comum de x e yn-1.
Onde, xm-1 = {x1, x2… xm-1}, yn-1 = {y1, y2… yn-1}, zk-1 = {z1, z2… zk-1}.
Relacionamento recursivo: use C [i] [J] para registrar o comprimento da subsequência mais comum das seqüências XI e YJ. Onde, xi = {x1, x2… xi}, yj = {y1, y2… yj}. Quando i = 0 ou j = 0, a sequência vazia é a subsequência mais comum de Xi e Yj. Neste momento, C [i] [j] = 0; quando eu, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; Quando eu, j> 0, xi! = yj,
c [i] [j] = max {c [i] [j-1], c [i-1] [j]}, estabelecendo assim o relacionamento recursivo da seguinte forma:
Construa a solução ideal: a partir da análise acima, podemos ver que, para encontrar a subsequência mais comum de x = {x1, x2, ... xm} e y = {y1, y2, ... yn}, você pode executar recursivamente da maneira seguinte: quando xm = yn, encontre a subestimação mais longa de xm-1 e yn-1 e depois xm xm xm xm, e depois a sub-sequença strin-1 e depois a sinuca e depois a sinuca e depois a sub-sequença com a sinuca e depois a sinuca e depois a sinuca de XM e depois a Sub-1 e depois a Sub-1 e a Yn-1 e depois a Sub-1) e depois a Sub-1) e depois a Sub-1) e depois a Sub-1) e depois a Sub-Sub-Strin-1 e depois a Sub-1) Y. Quando xm! = Yn, dois subproblemas devem ser resolvidos, ou seja, para encontrar uma das sub-seqüências mais comuns de XM-1 e Y e uma das sub-sequências mais comuns de x e yn-1. A maior dessas duas subsequências comuns é a subsequência mais comum de X e Y. Suponha que a matriz B [i] [J] registre o valor de C [i] [J] do qual o subproblema é obtido. A partir de B [m] [n], pesquise na matriz B de acordo com seu valor. Quando B [i] [J] = 1, a subsequência mais comum de Xi e Yj é a subsequência obtida pela adição de Xi à cauda de Xi-1 e YJ-1. Quando B [i] [J] = 2, significa que a subsequência mais comum de Xi e Yj é a mesma que a subsequência mais comum de XI-1 e YJ-1. Quando B [i] [J] = 3, a subsequência mais comum de Xi e Yj é a mesma que a subsequência mais comum de Xi e YJ-1.
O código é o seguinte:
pacote 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]; for (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; }}} retornar 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 dos testes:"); 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 ("A subseqüência comum mais longa de x e y é:"); LCS (B, X, X.Length - 1, Y.Length - 1); }}Resultados em execução:
Para obter mais informações sobre os algoritmos Java, os leitores interessados neste site podem visualizar os tópicos: "Estrutura de dados Java e tutorial de algoritmo", "Resumo das dicas de nó da operação Java Dom", "Resumo de dicas de operação de Java e Operação de Java" e "Resumo de Java cache" Tips "TIPS"
Espero que este artigo seja útil para a programação Java de todos.