Bài giảng Phân tích thiết kế giải thuật: Dynamic Programming (tiếp) - GV. Hà Đại Dương

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 (Xi1 và Yj) và của (Xi và Yj1)<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 />