Bài toán dãy con chung dài nhất

Ta gọi dãy con của một dãy cho trước là dãy thu được từ dãy đã cho bằng việc loại bỏ một số phần tử. Một cách hình thức, giả sử cho dãy X = <x1, x2, …, xm>, dãy Z = <z1, z2, …, zk> được gọi là dãy con của dãy X nếu tìm được dãy các chỉ số 1? i1 < i2 < … < ik ? n sao cho zi = xi j, j = 1, 2, …, k. Chẳng hạn dãy Z = < B, C, D, B> là dãy con của dãy X = <A, A, B, C, B, C, D, A, B, D, A, B> với dãy chỉ số là <3, 4, 7, 9>.

Cho hai dãy X và Y ta nói dãy Z là dãy con chung của hai dãy X và Y nếu Z là dãy con của cả hai dãy này. Ví dụ, nếu X = <A, B, C, D, E, F, G> và Y = <C, C, E, D, E, G, F> thì dãy Z = <C, D, F> là dãy con chung của hai dãy X và Y, còn dãy <B, F, G> không là dãy con chung của chúng. Dãy <C, D, F> không là dãy con chung dài nhất vì nó có độ dài 3 (số phần tử trong dãy), trong khi đó dãy <C, D, E, G> là dãy con chung của X và Y có độ dài 4. Dãy <C, D, E, G> là dãy con chung dài nhất vì không tìm được dãy con chung có độ dài 5.

được phát biểu như sau: Cho hai dãy X = <x1,x2,…,xm> và Y = <y1,y2,…,yn>. Cần tìm dãy con chung dài nhất của hai dãy X và Y.

Thuật toán trực tiếp để giải bài toán đặt ra là: Duyệt tất cả các dãy con của dãy X và kiểm tra xem mỗi dãy như vậy có là dãy con của dãy Y, và giữ lại dãy con dài nhất. Mỗi dãy con của X tương ứng với dãy chỉ số <i1,i2, …, ik> là tập con k phần tử của tập chỉ số {1, 2, …, m}, vì thế có tất cả 2m dãy con của X.Như vậy thuật toán trực tiếp đòi hỏi thời gian hàm mũ và không thể ứng dụng được trên thực tế. Ta xét áp dụng quy hoạch động để xây dựng thuật toán giải bài toán này.

Phân rã . Với mỗi 0 ? i ? m và 0 ? j ? n xét bài toán C(i,j); tính C[i,j] là độ dài của dãy con chung dài nhất của hai dãy.

Xi=<x1,x2,…,xi>

và

yi=<y1,y2,…yi>

Như vậy ta đã phân bài toán cần giải ra thành (m+1)x(n+1) bài toán con. Bản thân bài toán xuất phát là bài toán con có kích thước lớn nhất C(m,n).

Tổng hợp lời giải. Rõ ràng

c[o,j]=0,j =0,1,…,n và c[i,0]=0,i=0,1,…,m.

Giả sử i>0,j>0 ta cần tính c[i,j] là độ dài của dãy con chung lớn nhất của hai dãy Xi và Yi có hai tình huống:

Nếu Xi =Yi thì dãy con chung dài nhất của Xi vàYi sẽ thu được bằng việc bổ sung Xi vào dãy con chung dài nhất của hai dãy Xi-1và Yj-1

Nếu Xi Yi thì dãy con chung dài nhất của Xi và Yj sẽ là dãy con dài nhất trong hai dãy con chung dài nhất của (Xi và Yi) và của (Xi-1 và Yj) . Từ đó ta có công thức sau để tính C[i,j].

ci,j0,ci−1,j−1+1maxci,j−1,ci−1,j,{{ size 12{c left [i,j right ]alignl { stack { left lbrace 0, {} # right none left lbrace c left [i - 1,j - 1 right ]+1 {} # right none left lbrace "max" left lbrace c left [i,j - 1 right ],c left [i - 1,j right ] right rbrace {} # right no } } lbrace ,} {}nÕu i=0 hoÆc j=0nÕu i,j >0 vµ xi=yjnÕu i,j >0 vµ xi yj

ThuËt to¸n t×m d·y con chung dµi nhÊt cã thÓ m« t¶ nh­ sau.

Procedure LCS(X,Y);

begin

for i :=1 to m do c[i,0]:=0;

forj: =1 to n do c[0,j:=0;

for i: =1 to m do

for j: = 1to n do

if xi = yi then

begin

c[i,j]:=c[i-1,j-1]+1;

b[i,j]:=/;

end

else

if c [i-1,j] ≥ c[i,j-1] then

begin

c[i,j]:=c[i-1,j];

b[i,j]:=  ;

end

else

begin

c[i,j]:=c[i,j-1];

b[i,j]:=  ;

end;

end;

Trong thủ tục mô tả ở trên ta sử dụng biến b[i,j] để ghi nhận tình huống tối ưu khi tính giá trị c[i,j]. Sử dụng biến này ta có thể đưa ra dãy con chung dài nhất của hai dãy X và Y nhờ thủ tục sau đây:

Procedure Print LCS (b,X,i,j);

begin

if(i=0)or (j=0) then return;

if b[i,j]=/ then

begin

print LCS (b,X,i-1,j-1);

print xi; (* §­a ra ph©n tö xi *)

end

else

if b[i,j]=  then

PrintLCS (b,X,i-1,j)

else

Print LCS (b,X,i,j-1);

end;

Dễ dàng đánh giá được thời gian tính của thuật toán LCS là 0(mn).