intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: Hetiheti Hetiheti | Ngày: | Loại File: PDF | Số trang:18

83
lượt xem
4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng gồm các bài tập minh họa cho phương pháp Qui hoạch động: bài toán tìm xâu con chung dài nhất, đường đi ngắn nhất - Thuật toán Floyd và bài toán cây nhị phân tìm kiếm tối ưu. Tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2