Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
MỤC LỤC
MỤC LỤC......................................................................................................................................1
I. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG...............................................................................3

1.1. Phương pháp quy hoạch động..............................................................3
1.2. Các bước thực hiện quy hoạch động....................................................3
1.3. Hạn chế của quy hoạch động...............................................................4
II. BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA 2 XÂU KÝ TỰ.................................5

2.1. Phát biểu bài toán.................................................................................5
2.2. Phân tích và giải quyết bài toán...........................................................5
2.3.Phương pháp quy hoạch động cho LCS (Longest Common
Subsequence).........................................................................................................5
III. BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA K XÂU KÝ TỰ............................10

3.1. Phát biểu bài toán tổng quát...............................................................10
3.2. Phân tích, giải quyết bài toán.............................................................10

Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

1


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13

MỞ ĐẦU
Trong ngành hệ thống thông tin, quy hoạch động là một phương pháp giảm
thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau
(overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Nhà toán học
Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953. Ngành

này đã được thành lập như là một chủ đề về kỹ nghệ và phân tích hệ thống đã được tổ
chức IEEE thừa nhận. Cấu trúc con tối ưu có nghĩa là các lời giải tối ưu cho các bài
toán con có thể được sử dụng để tìm các lời giải tối ưu cho bài toán toàn cục. Ví dụ,
đường đi ngắn nhất tới một đỉnh trong một đồ thị có thể được tìm thấy bằng cách:
trước hết tính đường đi ngắn nhất tới đích từ tất cả các đỉnh kề nó, rồi dùng kết quả
này để chọn đường đi toàn cục tốt nhất. Nói chung, ta có thể giải một bài toán với cấu
trúc con tối ưu bằng một quy trình ba bước:
1. Chia bài toán thành các bài toán con nhỏ hơn.
2. Giải các bài toán này một cách tối ưu bằng cách sử dụng đệ quy quy trình ba
bước này.
3. Sử dụng các kết quả tối ưu đó để xây dựng một lời giải tối ưu cho bài toán ban
đầu.
Các bài toán con được giải bằng cách chia chúng thành các bài toán nhỏ hơn, và cứ
tiếp tục như thế, cho đến khi ta đến được trường hợp đơn giản dễ tìm lời giải.
Trong bài tập về tìm xâu con chung nhỏ nhất (liên tiếp) của k chuỗi nhóm đã
vận dụng nguyên lý của quy hoạch động để giải quyết bài toán.
Qua đây nhóm bày tỏ lòng cảm ơn tới PGS.TS Đào Thanh Tĩnh đã giảng dạy
môn Phân tích đánh giá thuật toán và hướng dẫn nhóm hoàn thành bài tập này.

Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

2


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
I. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG
1.1. Phương pháp quy hoạch động.
Bellman (Richard Bellman Ernes)[1] phát biểu nguyên lý tối ưu (cũng gọi là
nguyên lý Bellman) mà ý tưởng cơ bản là như sau: “Với mỗi quá trình điều khiển tối
ưu, đối với trạng thái bắt đầu A 0, với trạng thái A trong quá trình đó, phần quá trình

kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”.
Chú ý rằng nguyên lý này được thừa nhận mà không chứng minh.
Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là
quy hoạch động. Thuật ngữ này nói lên thực chất của quá trình điều khiển là động: có
thể trong một số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng
tựu chung cả quá trình lại là tốt nhất.
Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy,
tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu
của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm
hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc
thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con
cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động,
nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải những bài toán con
nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của
chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài
toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép giải đệ
quy và cũng là nội dung phương pháp quy hoạch động.
Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con
và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp
thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được
giải hay chưa.
Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ
sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài
toán lớn nhất (bài toán ban đầu).
1.2. Các bước thực hiện quy hoạch động
Bước 1: Lập hệ thức
Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai
đoạn, sau
Njkop0 đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý
với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các “bài toán

con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán
kích thước đã cho với kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn
của nó nhằm xây dựng phương trình truy toán (dạng hàm hoặc thủ tục đệ quy).
Về một cách xây dựng phương trình truy toán:
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

3


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
Ta chia việc giải bài toán thành n giai đoạn. Mỗi giai đoạn i có trạng thái ban
đầu là t(i) và chịu tác động điều khiển d(i) sẽ biến thành trạng thái tiếp theo t(i+1) của
giai đoạn i+1 (i=1,2,…,n-1). Theo nguyên lý tối ưu của Bellman thì việc tối ưu giai
đoạn cuối cùng không làm ảnh hưởng đến kết quả toàn bài toán. Với trạng thái ban đầu
là t(n) sau khi làm giai đoạn n tốt nhất ta có trạng thái ban đầu của giai đoạn n-1 là t(n1) và tác động điều khiển của giai đoạn n-1 là d(n-1), có thể tiếp tục xét đến giai đoạn
n-1. Sau khi tối ưu giai đoạn n-1 ta lại có t(n-2) và d(n-2) và lại có thể tối ưu giai đoạn
n-2 … cho đến khi các giai đoạn từ n giảm đến 1 được tối ưu thì coi như hoàn thành
bài toán. Gọi giá trị tối ưu của bài toán tính đến giai đoạn k là Fk giá trị tối ưu của bài
toán tính riêng ở giai đoạn k là Gk thì Fk = Fk-1 + Gk
ax {G k (t ( k ), d ( k )) + Fk −1 (t ( k − 1))} (*)
Hay là: Fk (t (k )) = m
∀d ( k )

Bước 2: Tổ chức dữ liệu và chương trình
- Tổ chức dữ liệu sao cho đạt các yêu cầu sau:
- Dữ liệu được tính toán dần theo các bước.
- Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.
- Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ
liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập.
Cụ thể

- Các giá trị của Fk thường được lưu trữ trong một bảng (mảng một chiều
hoặc hai, ba, v.v… chiều).
- Cần lưu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết
quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải:
F1 (t (1)) = m ax {G 1 (t (1), d (1)) + F0 (t (0))}
∀d (1)

- Dựa vào công thức, phương trình truy toán (*) và các giá trị đã có trong
bảng để tìm dần các giá trị còn lại của bảng.
Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với các giá trị tối ưu trong
từng gian đoạn.
Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu trong từng giai đoạn đã xây
dựng, tìm ra kết quả bài toán.
Bước 3: Làm tốt hệ thức
Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thước miền nhớ.
Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng
(hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước. Trong một
số trường hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0, 1
bởi mảng hai chiều mới bằng cách dùng kỹ thuật quản lý bit.
1.3. Hạn chế của quy hoạch động
Việc tìm công thức, phương trình truy toán hoặc tìm cách phân rã bài toán nhiều
khi đòi hỏi sự phân tích tổng hợp rất công phu, dễ sai sót, khó nhận ra như thế nào là
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

4


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời
giải của các bài toán con cũng cho kết quả của bài toán lớn hơn.

Khi bảng lưu trữ đòi hỏi mảng hai, ba chiều … thì khó có thể xử lý dữ liệu với
kích cỡ mỗi chiều lớn hàng trăm.
Có những bài toán không thể giải được bằng quy hoạch động.
II. BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA 2 XÂU KÝ TỰ
2.1. Phát biểu bài toán.
Xâu con chung của hai xâu A và B là xâu P nếu ta có thể nhận được xâu P bằng
cách xóa đi một số ký tự trong xâu A hoặc trong xâu B (giữ nguyên thứ tự trước/sau
các ký tự còn lại).
Cho hai xâu ký tự A và B, tìm xâu con chung P dài nhất của A và B.
Ví dụ:
A:= "AABCDEFE", B:= "DEABCFGHN", P:="ABCF" là xâu
con chung dài nhất của A và B.
2.2. Phân tích và giải quyết bài toán
Cho hai xâu ký tự: A = (a1a2...am), B = (b1b2...bn) và P = (p1p2…pk) là xâu
con chung dài nhất của A và B.
Một cách giải quyết bài toán ta sử dụng thuật toán Brute-Force (vét cạn) [2]
tìm xâu con chung dài nhất (LCS) là tìm tất cả các xâu con của A, và tìm xem nó có
phải là xâu con ở trong B hay không, từ đó ta có thể tìm được xâu con chung dài nhất
của A và B. Mỗi xâu con của A ứng với một tập con của tập chỉ số (1,2,…,m) có nghĩa
là ta có 2m tập con, vì vậy phương pháp này đòi hỏi thời gian hàm mũ có độ phức tạp
là O(n2m) là không thể giải quyết được cho những xâu lớn.
2.3.Phương pháp quy hoạch động cho LCS (Longest Common Subsequence)
Áp dụng nguyên lý của quy hoạch động ta có thể giải quyết bài toán LCS. Gọi
T[i,j] là độ dài xâu con chung dài nhất của hai xâu A[1..i] i ≤ m và B[1..j] j ≤ n, điều này có
nghĩa là T[i,j] là độ dài xâu con chung dài nhất của i ký tự đầu của xâu A và j ký tự đầu
của xâu B. Do đó T[m,n] chính là độ dài xâu con chung dài nhất của A và B.
a). Định lý:
Cho hai xâu ký tự: A = (a 1a2...am), B = (b1b2...bn) và P = (p1p2…pk) là xâu con
chung dài nhất của A và B.
i). Nếu am = bn thì pk = am = bn và Pk-1 là một LCS của Am-1 và Bn-1.

ii). Nếu am≠ bn và pk≠am thì P là LCS của Am-1 và B.
iii). Nếu am≠ bn và pk≠bn thì P là LCS của A và Bn-1
Chứng minh:
i). Nếu pk ≠ am thì chúng ta có thể thêm am = bn vào P chứa xâu con chung của A
và B sẽ có độ dài là k+1, mâu thuẫn với giả thiết rằng P là LCS của A và B, như vậy,
chúng ta phải có pk = am = bn. Bây giờ tiền tố Pk-1 có độ dài k-1 là xâu chung của Am-1
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

5


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
và Bn-1. Chúng ta chứng minh nó là một LCS, giả sử có một xâu chung W của A m-1 và
Bn-1 có độ dài lớn hơn k-1. Khi đó, ta thêm a m = bn vào W kết quả là W có độ dài lớn
hơn k, đó là một mâu thuẫn.
ii). Nếu pk ≠ am , thì P là xâu chung của Am-1 và B. Nếu tồn tại một xâu chung W
của Am-1 và B với chiều dài lớn hơn k, khi đó W có thể là xâu chung của A m và B, trái
với giả thiết rằng P là LCS của A và B.
iii). Chứng minh tương tự như ii)
b). Công thức truy hồi cho LCS:
Qua định lý trên ta có thể rút ra một số vấn đề:
• Trường hợp i=0 hoặc j= 0 thì độ dài xâu con chung dài nhất của A và B là 0,
nghĩa là T[0,j] = T[i,0] = 0.
• Trường hợp xét ai = bj thì ta thêm pk = am = bn vào P và độ dài xâu con chung dài
nhất T[i,j] sẽ bằng độ dài xâu con chung dài nhất của A i-1 và Bj-1 là T[i-1,j-1] cộng
thêm 1.
• Ngược lại nếu ai ≠ bj ta phải tìm LCS của Ai-1 và B, tìm LCS của A và B j-1 là
T[i-1,j] và T[i,j-1]. Xâu nào lớn hơn sẽ là LCS của A và B.
0


Ta có: T [ i, j ] = T [ i − 1, j − 1] + 1

max{T [ i − 1, j ], T [ i, j − 1]}

nÕui = 0, j = 0
nÕuai = b j
nÕuai ≠ b j

Giải thuật 2.1:
1).
Input (A[1,..,m], B[1,..,n])
2).
For i = 0 to m T[i,0] := 0;
For j = 0 to n T[0,j] := 0;
3).
For i = 1 to m
For j = 1 to n
If A[i] = B[j] then T[i,j] := T[i-1,j-1] + 1
Else T[i,j] := max { T[i-1,j], T[i,j-1]}
4).
Output (T[m,n])
Đánh giá: Qua giải thuật trên có hai vòng lặp for lồng nhau, trong trường hợp xấu nhất
thuật toán có độ phức tạp là O(mn), như vậy tốt hơn thuật toán Brute-Force.
Ví dụ: Cho hai xâu A:= "AABCDEFE", B:= "DEABCFGHNBBE", tìm độ dài xâu
con chung dài nhất. Ta xây dựng bảng sau:

Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

6



Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
B[j] 0 1 2 3 4 5 6 7 8 9
10 11 12
D E A B C F G H N B B E
A[i]
0
0 0 0 0 0 0 0 0 0 0
0
0
0
1
A 0 1 1 2 2 2 2 2 2 2
2
2
2
2
A 0 1 1 2 2 2 2 2 2 2
2
2
2
3
B 0 1 1 2 3 3 3 3 3 3
3
3
4
4
C 0 1 1 2 3 4 4 4 4 4
4
4

4
5
D 0 1 1 2 3 4 4 4 4 4
4
4
4
6
E 0 1 2 2 3 4 4 4 4 4
4
4
5
7
F 0 1 2 2 3 4 5 5 5 5
5
5
5
8
E 0 1 2 2 3 4 5 5 5 5
5
5
6
Bảng 0-1. Bảng phương án tìm độ dài xâu con chung dài nhất.
c). Truy vết tìm xâu con chung dài nhất:
* Giải thuật đệ quy đưa ra một xâu con chung dài nhất.
Giải thuật 2.2
Backtrackall(T[0..m,0..n], A[1..m], B[1..n], i, j)
1). If (i=0) or (j=0) then
Return R;
2). Else if A[i] = B[j] then
R = A[i] + R;

Backtrackall(T,A,B,i-1,j-1)}
Else
If T[i,j-1] >= T[i-1,j] then
Backtrackall(T,A,B,i,j-1)
If T[i-1,j] >= T[i,j-1] then
Backtrackall(T,A,B,i-1,j)
Đánh giá: gọi B(m,n) là độ phức tạp tính toán của bài toán, ta có B(m,n)=B(m1,n)+B(m,n-1)+C với C là số hữu hạn nhỏ các phép so sánh và gán, to có thể coi C =
0. Giả sử n = m ta có:
B(n,n) = 2B(n-1,n) = 2.2B(n-1,n-1) = 2.2…2.B(0,0) = 2nn
Vậy thuật toán trong trường hợp tồi nhất là O(2mn).
* Một cải tiến thuật toán truy vết.
- Ý tưởng: Ta dựa vào bảng phương án để truy vết tìm xâu chung. Xuất phát từ
ô T[m,n], giả sử đang đứng tại ô T[i,j] ta sẽ xét 2 ô trước đó là ô T[i-1,j], T[i,j-1], nếu
một trong hai ô có giá trị bằng ô T[i,j] thì ta sẽ lùi về ô đó cho tới khi hai ô trước có giá
trị nhỏ hơn ô đang đứng T[i’,j’], Khi đó A[i’] = B[j’]. Kết nạp A[i’] vào chuỗi P. Lùi về
ô T[i’-1,j’-1] và tiếp tục lặp lại cho tới T[0,0].

Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

7


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
Giải thuật 2.3:
1).
P := ‘’;
m := length(A); n := length(B);
2).
While (n>0) and (m>0) do
begin

a). while (n>0)and(T[m,n]=T[m,n-1]) do n:=n-1
b). while (m>0)and(T[m,n]=T[m-1,n]) do m:=m-1
c). begin
P := A[m] +P;
m := m -1 ;
n := n-1 ;
end ;
end ;
3). Output(P);
Thuật toán có độ phức tạp là O(m+n).
- Nhận xét:
Để tìm xâu con liên tiếp dài nhất của 2 chuỗi, ta thực hiện tìm kiếm xâu con liên
tục trong bước truy vết để tìm xâu con dài nhất của chuỗi đó; để thực hiện tìm kiếm
như vậy, ta sử dụng thêm một biến đếm số bước nhảy k, khi k>1 thì ta sẽ xét xâu con
liên tục vừa tìm được (P1) với xâu con liên tục đã tìm được trước đó (P2); quá trình
lặp lại khi tìm đến đầu mảng.
Giải thuật 2.4:
1).
P1=’’; P2=’’;
m := length(A); n := length(B);
2).
While (n>0) and (m>0) do
Begin
2.1) k=m;
2.2) While (n>0)and(T[m,n]=T[m,n-1]) do n:=n-1;
2.3) While (m>0)and(T[m,n]=T[m-1,n]) do m:=m-1;
2.4) Begin
If (k-m>1) then
Begin
if (Length(P1)>=Length(P2)) then P2:=P1;

P1=’’;
End;
P1=A[m]+P1;
m := m -1 ;
n := n-1 ;
end ;
End ;
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

8


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
3). Output(P);
Thuật toán có độ phức tạp là O(m+n).
Ví dụ: Xét hai xâu A:= "AABCDEFE", B:= "DEABCFGHNBBE". Ta tìm
được xâu con chung dài nhất là "ABCFE"
B[j]
A[i]
0
1
A
2
A
3
B
4
C
5
D

6
E
7
F
8
E

0
0
0
0
0
0
0
0
0
0

1
D
0
1
1
1
1
1
1
1
1


2
E
0
1
1
1
1
1
2
2
2

3
A
0
2
2
2
2
2
2
2
2

4
B
0
2
2
3

3
3
3
3
3

5
C
0
2
2
3
4
4
4
4
4

6
F
0
2
2
3
4
4
4
5
5


7
G
0
2
2
3
4
4
4
5
5

8
H
0
2
2
3
4
4
4
5
5

9
N
0
2
2
3

4
4
4
5
5

10
B
0
2
2
3
4
4
4
5
5

11
B
0
2
2
3
4
4
4
5
5


12
E
0
2
2
4
4
4
5
5
6

Bảng 0-2. Bảng truy vết tìm xâu chung dài nhất
2.4. Cải tiến phương pháp quy hoạch động cho LCS hai xâu A, B.
Dựa vào công thức quy hoạch động và bảng quy hoạch trên có thể tóm tắt lại
như sau: Khởi tạo dòng 0 của bảng, sau đó dùng dòng 0 tính dòng 1, dùng dòng 1 tính
dòng 2 v.v... tới khi tính được hết dòng n. Có thể nhận thấy rằng khi đã tính xong dòng
thứ k thì việc lưu trữ các dòng từ dòng 0 tới dòng k - 1 là không cần thiết bởi vì việc
tính dòng k + 1 chỉ phụ thuộc các giá trị lưu trữ trên dòng k. Vậy để tiết kiệm không
gian bộ nhớ ta có thể dùng hai mảng một chiều: Mảng Current lưu dòng hiện thời đang
xét của bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Current được gán các giá
trị tương ứng trên dòng 0. Sau đó dùng mảng Current tính mảng Next, mảng Next sau
khi tính sẽ mang các giá trị tương ứng trên dòng 1. Rồi lại gán mảng Current := Next
và tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương
ứng trên dòng 2 v.v... Vậy ta có giải thuật cải tiến với độ phức tạp tính toán là O(mn)
và không gian tuyến tính O(m+n) [3] như sau:
Giải thuật 2.5: (giả sử n ≥ m)
1).
Input (A[1,..,m], B[1,..,n])
2).

For j = 0 to n Current[j] := 0;
Next[0]:= 0;
3).
For i = 1 to m
a). For j = 1 to n
If A[i] = B[j] then Next[j] := Current[j-1] + 1
Else Next[j] := max { Current[j], Next[j-1]}
b). Current := Next;
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

9


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
4).
Output (Current[n])
Khi đó ta có giải thuật truy vết tìm xâu con chung dài nhất như sau:
Giải thuật 2.6: (giả sử n ≥ m)
1).
P := ‘’;
m := length(A); n := length(B);
2).
While (n>0) do
begin
a). while (n>0)and(Current[n]=Current[n-1]) do n:=n-1
b).
begin
P := B[n] +P;
n := n-1 ;
end ;

end ;
3). Output(P);

III. BÀI TOÁN XÂU CON CHUNG DÀI NHẤT CỦA K XÂU KÝ TỰ
3.1. Phát biểu bài toán tổng quát.
Cho các xâu ký tự:

(

)

(

)

A1 = a11 , a12 ,..., a1m1 ,

(

)

A2 = a21 , a22 ,..., a2m 2 ,

...,

An = an1 , an2 ,..., anmn . Tìm xâu con chung dài nhất của A1,A2, …,An. Ký hiệu

MLCS(A1,A2, …,An).
3.2. Phân tích, giải quyết bài toán.
Để tìm hiểu bài toán tổng quát ta xét ví dụ trong trường hợp 3 xâu A 1, A2, A3

như sau: A1 = “T CCACA” , A2 = “ACCAAG” và A3 = “AC”.
Bao giờ chúng ta cũng có thuật toán vét cạn, khi đó độ phức tạp tính toán là
O(m2m32m1) trong đó m1, m2, m3 lần lượt là độ dài của 3 xâu. Điều này là không thể
thực hiện được nếu chiều dài của các xâu lớn và có nhiều xâu hơn.
Nếu ta áp dụng phương pháp quy hoạch động cho từng cặp xâu một, giả dụ như
tìm B = LCS(A1,A2), sau đó tìm LCS(B, A3), thì khi đó độ phức tạp tính toán sẽ là
O(m1m2m3l) với l là độ dài xâu B. Đồng thời có thể ta không tìm được MLCS.

A1=

T C C A C A

Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

10


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
A2= A C C A A G
A1=

T C C A C A

A2= A C C A A G
A3= A C
Hình 0-1. LCS(A1,A2) và MLCS(A1,A2,A3)
Ta tìm thấy B = LCS(A1,A2) = “CCAA”, sau đó ta tìm LCS(B, A 3) = “A” hoăc
“C”, trong khi đó MLCS(A1,A2,A3) = “AC”.
Như vậy ta dùng phương pháp quy hoạch động cho bài toán 3 xâu sử dụng bảng
phương án 3 chiều như sau:

nÕui = 0 or j = 0 or k= 0
0

nÕuA 1[i] = A 2[ j ] = A 3[ k ]
T[i,j,k] = T[i - 1,j - 1,k - 1]+ 1
max{ T[i - 1,j, k],T[i,j - 1,k],T[i,j, k - 1]} choc¸ctrêng hîp kh¸c


Tổng quát cho trường hợp N xâu ký tự:
0
nÕu i1 = 0 or ... or i n = 0

nÕu A1[i1 ] = A 2 [i2 ] = ... = A n [in ]
T[i1,i2,,in] = T[i1 - 1, i 2 - 1,.., i n - 1] + 1
max{ T[i - 1, i ,.., i ], T[i , i - 1,..., i ], T[i , i ,.., i - 1]} cho c¸c trêng hîp kh¸c
1
2
n
1 2
n
1 2
n


Giải thuật 3.1: Cho trường hợp 3 xâu
1).
Input (A1[1,..,m1], A2[1,..,m2], A3[1,..,m3])
2).
For i = 0 to m1 T[i,0,0] := 0;
For j = 0 to m2 T[0,j,0] := 0;

For k = 0 to m3 T[0,0,k] := 0;
3).
For i = 1 to m1
For j = 1 to m2
For k = 1 to m3
If A1[i] = A2[j]=A3[k] then T[i,j,k] := T[i-1,j-1,k-1] + 1
Else T[i,j,k] := max { T[i-1,j,k]; T[i,j-1,k]; T[i,j,k-1]}
4).
Output (T[m1,m2,m3]).
Đánh giá : Thuật toán sử dụng 3 vòng lặp for lồng nhau nên thuật toán có độ
phức tạp tính toán và bộ nhớ là O(m1m2m3).
Dưới đậy là giải thuật truy vết tìm một xâu chung dài nhất của 3 xâu.
Giải thuật 3.2:
1).
P := “”;
m1 := length(A1); m2 := length(A2); m3 := length(A3)
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

11


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
2).

While (m1>0) and (m2>0) and (m3>0) do
begin
a). while (m1>0)and(T[m1,m2,m3]=T[m1-1,m2,m3]) do m1:=m1-1
b). while (m2>0)and(T[m1,m2,m3]=T[m1,m2-1,m3]) do m2:=m2-1
c). while (m3>0)and(T[m1,m2,m3]=T[m1,m2,m3-1]) do m3:=m3-1
d). begin

P := A1[m1] +P;
m1 := m1 -1 ; m2 := m2 -1 ; m3 := m3-1 ;
end ;
end ;
3). Output(P);
- Số phép so sánh của vòng lặp while = min(m1,m2,m3)
- Số phép so sánh trong vòng lặp, gồm 3 vòng lặp while: m1+m2+m3
=> số phép tính cần thực hiện:
(m1+m2+m3)*min(m1,m2,m3)=(m1+m2+m3)*kmin
Thuật toán có độ phức tạp là O((m1+m2+m3)*kmin)=O(m*n)
KẾT LUẬN
Trong bài báo cáo này nhóm đã phân tích bài toán, sử dụng các giải pháp để
giải quyết bài toán trong trường hợp của k xâu ký tự. Dưới đây là bảng đánh giá một
số thuật toán chính trên.
Tên thuật toán

Độ phức tạp tính
toán
m
Vét cạn cho 2 xâu
O(n2 )
Quy hoạch động cho 2 xâu
O(mn)
Cải tiến theo phương pháp của O(mn)
Hirschberg
Quy hoạch động cho 3 xâu
O(mnp)
Quy hoạch động cho k xâu

Độ phức tạp không

gian
O(m+n)
O(m)
O((m+n+p)*k)

TÀI LIỆU THAM KHẢO
Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

12


Phân Tích Và Đánh Gia Thuất Toán – Nhóm 13
[1] />[2] T.H. Cormen, C.E. Leiserson, R.L.Rivest, C.Stein, "Introduction to Algorithms",
Second Edition, the MIT Press, McGraw-Hill, 2001
[3] DanielA.Hirschberg. “ A linear space algorithm for computing maximal common
subsequences”, Communications of the ACM,18(6):341-343,1975
[4] />[5] Hunt, J.W. & Szymanski, T.G.: A Fast Algorithm for Computing Longest
Common Subsequences, Comm. of the ACM, Vol. 20, NO. 5, 1977, pp. 350-353
[6] L.Bergroth,H.Hakonen, T.Raita, Asurvey of longest common Subsequence
algorithms, in: String Processing and Information Retrieval(SPIRE), IEEE
Computer Society,2000, pp.39–48.
[7] C.S. Iliopoulos,M.S. Rahman, New effcient algorithms for LCS and constrained
LCS problem, in: H. Broersma, S.S. Dantchev, M. Johnson, S. Szeider (Eds.),
Algorithms and Complexity in Durham 2007—Proceedings of the Third ACiD
Workshop, 17–19 September 2007, Durham, UK, ACiD, Texts in Algorithmics,
vol. 9, King’s College, London, ISBN 978-1-904987- 55-0, 2007, pp. 83–94.].
[8] J.Y. Yang, Y. Xu, and Y. Shang, An Efficient Parallel Algorithm for Longest
Common Subsequence Problem on GPUs. Proceedings of the World Congress on
Engineering 2010 Vol I. WCE 2010, June 30 - July 2, 2010, London U.K.


Giáo viên hướng dẫn : PGS.TS Đào Thanh Tĩnh

13