2/2/2017<br />
<br />
Analysis and Design of Algorithms<br />
<br />
Lecture 9,10<br />
<br />
Dynamic Programming<br />
Lecturer: Ha Dai Duong<br />
duonghd@mta.edu.vn<br />
<br />
2/2/2017<br />
<br />
1<br />
<br />
Nội dung<br />
1.<br />
2.<br />
3.<br />
4.<br />
5.<br />
6.<br />
7.<br />
<br />
Lược đồ chung<br />
Bài toán tính số Fibonaci<br />
Bài toán cái túi<br />
Bài toán dãy con có tổng lớn nhất<br />
Bài toán tìm xâu con chung dài nhất<br />
Đường đi ngắn nhất - TT Floyd<br />
Cây nhị phân tìm kiếm tối ưu<br />
<br />
2/2/2017<br />
<br />
2<br />
<br />
Bài toán<br />
• Cho hai xâu<br />
X = (x1,x2,…,xm) và<br />
Y = (y1,y2,…,yn)<br />
<br />
• Hãy tìm xâu con chung dài nhất của hai dãy X<br />
và Y.<br />
• Ví dụ<br />
X = KHOA HOC<br />
Y = HOA HONG<br />
2/2/2017<br />
<br />
HOA HO<br />
<br />
3<br />
<br />
1<br />
<br />
2/2/2017<br />
<br />
Ý tưởng thuật toán<br />
• Phân rã:<br />
– m: chiều dài xâu X, n: chiều dài xâu Y<br />
– Với mỗi 0≤ i ≤ m và 0 ≤ j ≤ n gọi C[i, j] là độ dài của<br />
dãy con chung dài nhất của hai dãy<br />
Xi=x1x2…xi và Yj =y1y2…yj<br />
(Qui ước X0 = rỗng, Y0= rỗng)<br />
– Khi đó C[m,n] là chiều dài xâu con chung dài nhất<br />
của X và Y.<br />
<br />
• Bài toán con: C[0,j]=0 j=1..n, C[i,0] = 0 i=1..m<br />
2/2/2017<br />
<br />
4<br />
<br />
Tổng hợp<br />
• Với i > 0, j > 0 tính C[i, j]<br />
– Nếu xi = yj thì dãy con chung dài nhất của X i và Yj<br />
sẽ thu được bằng việc bổ sung x i (cũng là yj) vào<br />
dãy con chung dài nhất của hai dãy X i-1 và Yj-1<br />
C[i,j] = C[i-1,j-1]+1<br />
– Nếu xi ≠ yj thì dãy con chung dài nhất của X i và Yj<br />
sẽ là dãy con dài hơn trong hai dãy con chung dài<br />
nhất của (Xi1 và Yj) và của (Xi và Yj1)<br />
C[i,j] = Max{C[i-1,j], C[i,j-1]}<br />
2/2/2017<br />
<br />
5<br />
<br />
Cài đặt<br />
Procedure LCS(X,Y)<br />
{<br />
For i =1 to m do c[i,0]=0;<br />
For j =1 to n do c[0,j ]=0;<br />
For i =1 to m do<br />
for j = 1 to n do<br />
If xi = yj then { c[i,j]=c[i-1,j-1]+1; b[i,j]=’’ }<br />
else<br />
If c [i-1,j]≥ c[i,j-1] then { c[i,j]=c[i-1,j]; b[i,j]=’’;}<br />
else { c[i,j]=c[i,j-1]; b[i,j]=’’;}<br />
}<br />
2/2/2017<br />
<br />
6<br />
<br />
2<br />
<br />
2/2/2017<br />
<br />
Minh họa<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
H<br />
O<br />
A<br />
H<br />
O<br />
N<br />
G<br />
2/2/2017<br />
<br />
7<br />
<br />
Khởi tạo<br />
• Y= KHOAHOC, X= HOAHONG<br />
K<br />
0<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
G<br />
<br />
0<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
0<br />
<br />
O<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
A<br />
<br />
0<br />
<br />
0<br />
<br />
A<br />
<br />
O<br />
<br />
0<br />
<br />
0<br />
<br />
O<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
2/2/2017<br />
<br />
8<br />
<br />
Lặp<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
2/2/2017<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
9<br />
<br />
3<br />
<br />
2/2/2017<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
O<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
2/2/2017<br />
<br />
10<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
?<br />
<br />
O<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
2/2/2017<br />
<br />
11<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
1<br />
<br />
O<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
2/2/2017<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
12<br />
<br />
4<br />
<br />
2/2/2017<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
O<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
<br />
0<br />
<br />
2/2/2017<br />
<br />
13<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
O<br />
<br />
0<br />
<br />
0<br />
<br />
A<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
<br />
0<br />
<br />
2/2/2017<br />
<br />
14<br />
<br />
Lặp …<br />
• X= KHOAHOC, Y= HOAHONG<br />
K<br />
<br />
H<br />
<br />
O<br />
<br />
A<br />
<br />
H O C<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
1<br />
<br />
O<br />
<br />
0<br />
<br />
0<br />
<br />
?<br />
<br />
A<br />
<br />
0<br />
<br />
O<br />
<br />
0<br />
<br />
N<br />
<br />
0<br />
<br />
G<br />
2/2/2017<br />
<br />
0<br />
<br />
H<br />
<br />
0<br />
15<br />
<br />
5<br />
<br />