本文實(shí)例講述了java算法之最長(zhǎng)公共子序列問(wèn)題(lcs)。分享給大家供大家參考，具體如下：
問(wèn)題描述：一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說(shuō)，若給定序列x= { x1, x2,…, xm}，則另一序列z= {z1, z2,…, zk}是x的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列 {i1, i2,…, ik}，使得對(duì)于所有j=1,2,…,k有 xij=zj。例如，序列z={b,c,d,b}是序列x={a,b,c,b,d,a,b}的子序列，相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。給定兩個(gè)序列x和y，當(dāng)另一序列z既是x的子序列又是y的子序列時(shí)，稱z是序列x和y的公共子序列。例如，若x= { a, b, c, b, d, a, b}和y= {b, d, c, a, b, a}，則序列{b,c,a}是x和y的一個(gè)公共子序列，序列{b,c,b,a}也是x和y的一個(gè)公共子序列。而且，后者是x和y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閤和y沒(méi)有長(zhǎng)度大于4的公共子序列。給定兩個(gè)序列x= {x1, x2, …, xm}和y= {y1, y2, … , yn}，要求找出x和y的一個(gè)最長(zhǎng)公共子序列。
問(wèn)題解析：設(shè)x= { a, b, c, b, d, a, b},y= {b, d, c, a, b, a}。求x，y的最長(zhǎng)公共子序列最容易想到的方法是窮舉法。對(duì)x的多有子序列，檢查它是否也是y的子序列，從而確定它是否為x和y的公共子序列。由集合的性質(zhì)知，元素為m的集合共有2^m個(gè)不同子序列，因此，窮舉法需要指數(shù)級(jí)別的運(yùn)算時(shí)間。進(jìn)一步分解問(wèn)題特性，最長(zhǎng)公共子序列問(wèn)題實(shí)際上具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
設(shè)序列x={x1,x2,……xm}和y={y1,y2,……yn}的最長(zhǎng)公共子序列為z={z1,z2,……zk}。則有：
(1)若xm=yn,則zk=xm=yn,且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。
(2)若xm!=yn且zk!=xm，則z是xm-1和y的最長(zhǎng)公共子序列。
(3)若xm!=yn且zk!=yn，則z是x和yn-1的最長(zhǎng)公共子序列。
其中，xm-1={x1,x2……xm-1}，yn-1={y1,y2……yn-1},zk-1={z1,z2……zk-1}。
遞推關(guān)系：用c[i][j]記錄序列xi和yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，xi={x1,x2……xi}，yj={y1,y2……yj}。當(dāng)i=0或j=0時(shí)，空序列是xi和yj的最長(zhǎng)公共子序列。此時(shí)，c[i][j]=0；當(dāng)i,j>0，xi=yj時(shí)，c[i][j]=c[i-1][j-1]+1；當(dāng)i,j>0，xi!=yj時(shí)，
c[i][j]=max{c[i][j-1],c[i-1][j]}，由此建立遞推關(guān)系如下：
構(gòu)造最優(yōu)解：由以上分析可知，要找出x={x1,x2,……xm}和y={y1,y2,……yn}的最長(zhǎng)公共子序列,可以按一下方式遞歸進(jìn)行：當(dāng)xm=yn時(shí)，找出xm-1和yn-1的最長(zhǎng)公共子序列，然后在尾部加上xm(=yn)即可得x和y的最長(zhǎng)公共子序列。當(dāng)xm!=yn時(shí)，必須解兩個(gè)子問(wèn)題，即找出xm-1和y的一個(gè)最長(zhǎng)公共子序列及x和yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者為x和y的最長(zhǎng)公共子序列。設(shè)數(shù)組b[i][j]記錄c[i][j]的值由哪一個(gè)子問(wèn)題的解得到的，從b[m][n]開始，依其值在數(shù)組b中搜索，當(dāng)b[i][j]=1時(shí)，表示xi和yj的最長(zhǎng)公共子序列是由xi-1和yj-1的最長(zhǎng)公共子序列在尾部加上xi所得到的子序列。當(dāng)b[i][j]=2時(shí)，表示xi和yj的最長(zhǎng)公共子序列與xi-1和yj-1的最長(zhǎng)公共子序列相同。當(dāng)b[i][j]=3時(shí)，表示xi和yj的最長(zhǎng)公共子序列與xi和yj-1的最長(zhǎng)公共子序列相同。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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]; 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; } } } 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("服務(wù)器之家測(cè)試結(jié)果："); 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("x和y的最長(zhǎng)公共子序列是："); lcs(b, x, x.length - 1, y.length - 1); }} |
運(yùn)行結(jié)果：
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
原文鏈接：http://blog.csdn.net/u014755255/article/details/50571192
