이 기사에서는 Java 알고리즘의 가장 긴 공통 후속 문제 (LCS)를 설명합니다. 다음과 같이 참조에 대해 공유하십시오.
문제 설명 : 주어진 서열의 후속 시열은 여러 요소가 서열로부터 삭제 된 후에 얻은 서열이다. 정확하게 말하면, 시퀀스 x = {x1, x2,…, xm}이 주어지면, 또 다른 시퀀스 z = {z1, z2,…, zk}는 x의 후속 시점은 엄격하게 증분 첨자 서열 {i1, i2,…, ik}의 존재를 의미합니다. 예를 들어, 시퀀스 z = {b, c, d, b}는 시퀀스 x = {a, b, c, b, d, a, b}의 후속 시퀀스이고, 해당 증분 첨자 서열은 {2,3,5,7}입니다. 두 개의 시퀀스 x와 y가 주어지면, 다른 서열 z가 x와 y의 하단 시퀀스 일 때, z는 시퀀스 x와 y의 공통 후속 시열이라고 불린다. a}는 또한 x와 y의 일반적인 후속입니다. 또한, 후자는 x와 y의 가장 긴 일반적인 후속 중 하나입니다. x와 y는 4보다 큰 일반적인 후속을 갖지 않기 때문에 x = {x1, x2,…, xm}과 y = {y1, y2,…, yn}을 감안할 때, x 및 y를 가장 길게 찾는 데 필요합니다.
문제 분석 : x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a}를하자. x와 y의 가장 긴 공통 후속을 찾는 가장 쉬운 방법은 철저한 방법입니다. x의 다중 후속도의 경우, y의 후속 시퀀스인지 확인하여 x 및 y의 일반적인 후속 시퀀스인지 여부를 결정합니다. 세트 M의 특성으로부터, 요소 M이있는 세트는 총 2^m의 후속 시퀀스를 가지므로, 철저한 방법에는 지수 작동 시간이 필요합니다. 문제 특성을 더욱 분해하면 가장 긴 일반적인 후속 문제는 실제로 최적의 하위 구조 특성을 갖습니다.
시퀀스의 가장 긴 일반적인 후속 x = {x1, x2, ... xm} 및 y = {y1, y2, ... yn}이 z = {z1, z2, ... zk}이라고 가정합니다. 그런 다음 다음이 있습니다.
(1) XM = YN 인 경우 ZK = XM = YN 및 ZK-1은 XM-1 및 YN-1의 가장 긴 일반적인 후속입니다.
(2) xm! = yn 및 zk! = xm 인 경우 Z는 XM-1 및 Y의 가장 긴 일반적인 후속입니다.
(3) xm! = yn 및 zk! = yn 인 경우 z는 x와 yn-1의 가장 긴 일반적인 후속입니다.
여기서 xm-1 = {x1, x2… xm-1}, yn-1 = {y1, y2… yn-1}, zk-1 = {z1, z2… zk-1}.
재귀 관계 : c [i] [j]를 사용하여 시퀀스 XI 및 YJ의 가장 긴 일반적인 후속의 길이를 기록하십시오. 여기서 xi = {x1, x2… xi}, yj = {y1, y2… yj}. i = 0 또는 j = 0 일 때, 빈 시퀀스는 XI와 YJ의 가장 긴 일반적인 후속입니다. 이때, c [i] [j] = 0; i, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; i, j> 0, xi! = yj,
C [i] [j] = max {c [i] [j-1], c [i-1] [j]}, 다음과 같이 재귀 관계를 설정합니다.
최적의 솔루션 구성 : 위의 분석에서 x = {x1, x2, ... xm} 및 y = {y1, y2, ... yn}의 가장 긴 일반적인 후속을 찾기 위해 다음과 같은 방식으로 재귀 적으로 수행 할 수 있습니다. xm = yn이면 xm-1 및 yn-1의 가장 긴 공통 후속도를 찾을 수 있습니다. Y. XM! = YN 일 때, 두 개의 하위 프로젝트를 해결해야합니다. 이 두 가지 공통 후속 중 하나는 x와 y의 가장 긴 공통 후속입니다. 배열 b [i] [j]가 하위 프로 블렘이 얻은 c [i] [j]의 값을 기록한다고 가정 해 봅시다. b [m] [n]에서 시작하여 값에 따라 배열 B에서 검색하십시오. b [i] [j] = 1 인 경우, xi와 yj의 가장 긴 일반적인 하단은 xi-1 및 yj-1의 꼬리에 xi를 추가함으로써 얻은 후속입니다. b [i] [j] = 2 인 경우, Xi와 YJ의 가장 긴 일반적인 후속은 XI-1 및 YJ-1의 가장 긴 일반적인 후속과 동일하다는 것을 의미합니다. b [i] [J] = 3 인 경우, Xi와 YJ의 가장 긴 일반적인 후속은 Xi 및 YJ-1의 가장 긴 일반적인 후속과 동일합니다.
코드는 다음과 같습니다.
패키지 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; } for (int i = 1; i <n; i ++) {c [0] [i] = 0; } for (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; }}} 반환 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 테스트 결과 :"); 문자열 [] x = { ","a ","b ","c ","b ","d ","a ","b "}; 문자열 [] y = { "", "b", "d", "c", "a", "b", "a"}; int [] [] b = lcslength (x, y); System.out.println ( "x와 y의 가장 긴 일반적인 후속은 :"); lcs (b, x, x.length -1, y.length -1); }}실행 결과 :
Java 알고리즘에 대한 자세한 내용은이 사이트에 관심이있는 독자들이 주제를 볼 수 있습니다. "Java 데이터 구조 및 알고리즘 자습서", "Java Operation Dom Node Tips 요약", "Java 파일 및 디렉토리 작동 팁 요약"및 "Java Cache Operation Tips의 요약"을 볼 수 있습니다.
이 기사가 모든 사람의 Java 프로그래밍에 도움이되기를 바랍니다.