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