Thiết kế và đánh giá thuật toán

Mỗi giá trị c[i,j] trong bảng c[0..m, 0..n] được tính toán theo thứ tự chính là hàng; nghĩa là hàng đầu tiên của c được điền từ trái qua phải, sau đó là hàng thứ 2

.v.v. Song song với bảng c, ta tính toán một bảng b[0..m, 0..n] có giá trị bảng tương ứng với giải pháp của bài toán con tối ưu c[i,j]. Hàm trả về các bảng b và c; trong đó c[m,n] chứa chiều dài của một xâu con chung dài nhất của X, Y.

- Xây dựng bảng c[m,n]; m = length(X), n = length(Y) trong đó:

+ c[i,j] chứa độ dài xâu con chung dài nhất của Xi và Yj; 0  i  m, 0  j  n; với c[i,j] được tính theo công thức (*);

+ c[m,n] chính là chiều dài của xâu con chung dài nhất. Ta hình dung bảng c[m,n] được lấy gốc toạ độ c[0,0] là góc trên cùng, bên trái; còn trục tung và trục hoành tương ứng với X và Y.

- Xây dựng bảng b[i,j] tương ứng để truy vết của xâu con chung dài nhất bắt đầu từ b[m,n]; trong đó b[i,j] được tính như sau:

+ Nếu xi = yj đặt b[i,j] = 0; điều này có nghĩa đây chính là một thành phần của xâu con chung dài nhất khi ta lần ngược từ dưới lên; {b[i,j] = 0 biểu thị hướng truy vết đi chéo lên của bảng c tại vị trí (i,j)};

+ Nếu xi  yj và c[i-1,j]  c[i,j-1] đặt b[i,j] = 1; điều này khẳng định xâu con chung dài nhất của Xi, Yj chính là xâu con chung dài nhất của Xi-1, Yj; hay nói cách khác nếu xi-1 = yj thì đây chính là một thành phần của xâu con chung dài nhất;

{b[i,j] = 1 biểu thị hướng truy vết đi lên thẳng đứng của bảng c tại vị trí (i,j)};

+ Nếu xi  yj và c[i-1,j]  c[i,j-1] thì b[i,j] = -1; điều này khẳng định xâu con chung dài nhất của Xi, Yj chính là xâu con chung dài nhất của Xi, Yj-1; hay nói cách khác nếu xi = yj-1 thì đây chính là một thành phần của xâu con chung dài nhất; {b[i,j]

= -1biểu thị hướng truy vết đi ngang sang trái của bảng c tại vị trí (i,j)}

- Từ b[m,n] lần ngược lên trên đến b[0,0] tìm được xâu con chung dài nhất theo thứ tự đảo ngược lại của các vị trí;

- Đảo ngược lại xâu con tìm được ta sẽ được xâu con chung dài nhất cần tìm.

Thuật toán

Xaucon(X,Y)

/* Hàm này tính toán 2 bảng c và b từ dữ liệu đầu vào là hai xâu X và Y */

{

m=length(X); n=length(Y);

for( i= 0; i<=m;i++)

c[i,0]=0;

for( i= 0; i<=n;i++)

c[0,i]=0;

for( i= 1; i<=m;i++) for( j= 1; j<=n;j++)

if (X[i] == Y[j])

{

}

else

c[i,j]= c[i-1,j-1]+1; b[i,j]= 0 ;

if (c[i-1,j]  c[i,j-1])

{

}

else

{

}

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

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

In ra xâu con chung dài nhất

Sau khi đã xây dựng được các bảng b và c, ta sẽ sử dụng các bảng này để in ra xâu con chung dài nhất.

Bắt đầu từ b[m,n] trong bảng b ta tiến hành dò ngược lên trên. Với một b[i,j] bất kỳ (0  i  m, 0  j  n) ta chia làm 3 trường hợp:

- Nếu b[i,j] = -1 và (i > 0 và j > 0) thì ta truy vết ngang sang trái của bảng c, tức là xét bài toán con ứng với Xi-1 và Yj.

- Nếu b[i,j] = 0 và (i > 0 và j > 0) thì xi = yj = zc[i,j] chính là một thành phần của xâu con chung dài nhất; xét bài toán con ứng với Xi-1, Yj-1 và in ra giá trị đó.

- Nếu b[i,j] = 1 và (i > 0 và j > 0) thì ta truy vết lên thẳng đứng của bảng c, tức là xét bài toán con ứng với Xi và Yj-1.

Như vậy sau khi dò ngược lên trên ta in ra được xâu con chung dài nhất của X và Y.

Thuật toán In_XCCDN in ra xâu con chung dài nhất

In_XCCDN(b,c,i,j)

{

if ((i == 0)||(j == 0) return; if (b[i,j] == 0)

{

In_XCCDN(b,c,i-1,j-1)

printf(X[i])

}

else

{

if (b[i,j] == 1) In_XCCDN(b,c,i-1,j) else In_XCCDN(b,c,i,j-1);

}

Ví dụ 6.3.

Cho xâu X=ABCDAD; xâu Y=BDCABAD; Tìm xâu con chung dài nhất Z; ta có thể mô tả các bước của thuật toán trong các bảng sau

j	0 yj	1 B	2 D	3 C	4 A	5 B	6 A	7 D
0	xi	0	0	0	0	0	0	0	0
1	A	0	0	0	0	1	1	1	1
2	B	0	1	1	1	1	2	2	2
3	C	0	1	1	2	2	2	2	2
4	D	0	1	2	2	2	2	2	3
5	A	0	1	2	2	3	3	3	3
6	D	0	1	2	2	3	3	3	4

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

Hình 6.8. Bảng c

1	2	3	4	5	6	7
1	1	1	1	0	-1	-1	-1
2	0	-1	-1	1	0	-1	-1
3	1	1	0	-1	1	1	1
4	1	0	1	1	1	1	0
5	1	1	1	0	-1	0	1
6	1	1	1	1	1	1	0

Hình 6.9. Bảng b

Trong bảng c các phần tử của dòng ứng với i=0 và cột ứng với j=0 đều có giá trị 0 do các lệnh:

for( i= 0; i<=m;i++) c[i,0]=0;

for( i= 0; i<=n;i++) c[0,i]=0;

Từ hàng 1 đến hàng 6 các phần tử của các bảng b và c được xác định do các lệnh:

for( i= 1; i<=m;i++)

for( j= 1; j<=n;j++) if (X[i] == Y[j])

{

}

else

c[i,j]= c[i-1,j-1]+1; b[i,j]= 0 ;

if (c[i-1,j]  c[i,j-1])

{

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

}

else

{

}

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

Việc in ra xâu con chung dài nhất được thực hiện qua hàm In_XCCDN(b,c,6,7). Quá trình tìm (và in ra) xâu con chung dài nhất được minh họa trong các bảng qua các ô bôi đen, theo đó xâu con chung dài nhất được in ra sẽ là: ABAD

3) Đánh giá độ phức tạp của thuật toán

Đối với thuật toán Xaucon(X,Y) phép toán tích cực có thể coi là phép so sánh X[i] == Y[j], phép này nằm trong hai vòng for lồng nhau là

for( i= 1; i<=m;i++)

for( j= 1; j<=n;j++)

Do đó độ phức tạp của thuật toán là O(mn).

Đối với In_XCCDN(b,c,i,j) gọi đệ quy lẫn nhau với đầu vào ban đầu là bộ (b,c,i=m, j=n). Nhưng dù thế nào thì ở bước 2 hoặc bước 3 ít nhất giá trị của i hoặc của j (hoặc của cả 2) bị giảm đi 1. Thuật toán dừng khi i=0 hoặc j=0; do đó trong trường hợp xấu nhất thuật toán cũng chỉ mất m+n bước, hay nói cách khác độ phức tạp của thuật toán là O(m+n).

Sau khi gọi Xaucon(X,Y) sẽ gọi In_XCCDN(b,c,i,j). Do vậy độ phức tạp tính toán của thuật toán tìm xâu con chung dài nhất của hai xâu sẽ là O(mn).

* Nhận xét

Đối với hai thuật toán Xaucon và In_XCCDN ở trên ta phải sử dụng thêm một bảng phụ b[0..m,0..n] để truy vết khi xác định một xâu con chung dài nhất. Tuy nhiên việc xác định một xâu con chung dài nhất này chỉ cần dựa vào thông tin của bảng c; hay nói cách khác từ c[m,n] truy ngược lên đến c[0,0], tại mỗi vị trí c[i,j] ta có thể xác định được bước truy vết tiếp theo chỉ cần dựa vào bộ ba giá trị {c[i,j], c[i- 1,j], và c[i,j-1]} mà không cần xem xét bảng phụ b. Chính vì vậy ta có thể cải thiện không gian bộ nhớ khi bỏ qua bảng b. Khi đó các hàm Xaucon và In_XCCDN sẽ có sự thay đổi như sau:

Xaucon(X,Y)

/* Hàm này tính toán bảng c từ dữ liệu đầu vào là hai xâu X và Y */

{

m=length(X); n=length(Y);

for( i= 0; i<=m;i++)

c[i,0]=0;

for( i= 0; i<=n;i++)

c[0,i]=0;

for( i= 1; i<=m;i++) for( j= 1; j<=n;j++)

if (X[i] == Y[j]) c[i,j]= c[i-1,j-1]+1;

else

if (c[i-1,j]  c[i,j-1])

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

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

}

In_XCCDN(c,i,j)

/* Đưa ra xâu con chung dài nhất*/

{

z= ’’;

i= m; j= n;

While ((i>0) && (j>0))

if (X[i] == Y[j])

{

z= z + X[i]; i= i-1;

j= j-1;

}

else

if (c[i-1,j]  c[i,j-1]) i= i-1;

else

j:= j-1;

return(Z);

}

BÀI TẬP CHƯƠNG 6

1. Cho hai dãy số nguyên

X = 12, 5, 50, 35, 11, 45, 60

Y = 6, 5, 40, 35, 21, 55, 45, 60, 9

Hãy mô phỏng quá trình áp dụng thuật toán tìm xâu con chung dài nhất để tìm dãy con chung dài nhất của X và Y.

2. Bài toán chia quà

Minh và Nhật là hai anh em sinh đôi, trong ngày sinh nhật, hai anh em nhận được n món quà. Trên món quà i có ghi giá tiền x[i]. Hai anh em quyết định phân chia n món quà thành hai phần, mỗi người được sở hữu một phần. Hãy sử dụng kỹ thuật quy hoạch động phân chia sao cho chênh lệch giá trị của hai phần quà là ít nhất.

Hướng dẫn:

- Gọi t là tổng giá trị của n món quà : t =  x[i]

- Gọi m là nửa tổng giá trị của n món quà: m = t/2

- Phải tìm tập y {1,2, ... ,n} sao cho  x[i] với iy gần m nhất

- Để diễn đạt phần tử thứ i của tập {1,2,... ,n} thuộc tập y, ta sẽ ký hiệu y[i]=1, ngược lại ta ký hiệu y[i]=0

- Gọi f[i,j] là tổng giá trị lớn nhất trong trường hợp có i món quà và giá trị tối đa là j (nghĩa là tổng giá trị của các món quà được chọn không quá j)  f[n,m] là giá trị cần tìm.

- Xây dựng được công thức như sau:

f[i,0]=0, i =1..n

và f[0,j]=0, j =1..m

f[i-1,j-x[i]]+x[i] (món quà thứ i được chọn) f[i,j] = max f[i-1,j] (món quà thứ i không được chọn)

i =1..n và j =1..m

Thuật toán:

For i:=1 to n do

For j:=1 to m do Nếu x[i]j thì