Phân tích thiết kế thuật giải - Quy hoạch động

QUY HOẠCH ĐỘNG TS. NGÔ QUỐC VIỆT 2015 PHÂN TÍCH THIẾT KẾ THUẬT GIẢI Nội dung 2 1. Giới thiệu 2. Giải quyết một số bài toán bằng quy hoạch động.  Ba lô 0-1  Nhân ma trận 3. Bài tập 4. Hỏi đáp. Giới thiệu 3  Quy hoạch động (dynamic programming) nhằm giải quyết bài toán tìm:  Trong đó, u là biến (một hay nhiều chiều), g(u) là hàm lượng giá, U là tập điều kiện ràng buộc.  Là thuật giải dạng bottom-up. Nghĩa là các bài toán “con” (không phải được chia từ bài toán lớn theo dạng chia để trị) được giải trước, và tổng hợp để ra kết quả của bài toán lớn. Giới thiệu 4  Giống chia để trị ở chỗ: chia thành các bài toán con để giải quyết  Khác chia để trị ở chỗ  Các lời giải con không độc lập.  Các lời giải con được lưu trữ trong bảng kết quả. So sánh giữa chia để trị và DP 5 DP: lời giải con phụ thuộc  thuật giải luỹ thừa Chia để trị: lời giải con độc lập. Các bước giải quyết 6  Xây dựng lời giải cho từng bài toán nhỏ.  Xây dựng công thức hồi quy nhằm xác định lời giải ở các bước sau.  Để tránh độ phức tạp luỹ thừa  lưu trữ các lời giải con vào bảng tra (để không phải giải lại như đệ quy). Minh hoạ DP với bài toán Knapsack 7  DỮ LIỆU: n item  wi = cân nặng của item i  vi = giá trị của item i  W = sức chứa của knapsack  GIẢI PHÁP: tìm tập con S các item sao cho trọng lượng không vươt quá W  MỤC TIÊU: tìm cực đại giá trị của S Bài toán Knapsack 8  Nghĩa là tìm: tập con S sao cho với  Được gọi là bài toán 0-1 Knapsack.  Chú ý: tìm cực đại theo giá trị thay vì theo trọng lượng hay kích thước của balô. Thuật giải đơn giản 9  Sắp xếp các items theo “price per pound” vi/wi  Lấy từng item theo thứ tự này bỏ vào balô, nếu vẫn còn bỏ được (chú ý đến điều kiện ràng buộc).  Sinh viên hãy đánh giá thuật giải này (có tìm được KQ tối ưu không?) Sử dụng DP cho Knapsack 0-1 10  Minh hoạ kết quả khác biệt giữa thuật giải đơn giản (tham lam) và DP Sử dụng DP cho Knapsack 0-1 11  Đặt 𝑲[𝒋] là giá trị tối ưu của các item chứa trong ba lô kích thước 𝒋 (< 𝑾).  Yêu cầu cuối cùng cần tìm là K[M].  Để tìm K[W, n], cần xác định các lời giải con bao gồm 𝑖 (0 < 𝑖 < 𝑛) item đầu tiên cho ba lô có kích thước (0 < 𝑗 < 𝑊). Sử dụng DP cho Knapsack 0-1 12  Ký hiệu các lời giải con là: 𝐾[𝑗, 𝑖].  Xét mảng hai chiều 𝑲[𝟎. . 𝑾, 𝟎. . 𝒏], trong đó  𝑲[𝒋, 𝒊] là giá trị tối ưu của các item trong giỏ có kích thước j, chỉ sử dụng các item 1,,i.  Nhận xét: 𝑲[𝒋, 𝟎] = 𝟎 (không có item để lấy)  Nhận xét 𝑲[𝟎, 𝒊] = 𝟎 (kích thước balô bằng 0) Sử dụng DP cho Knapsack 0-1 13  Công thức tính K[j, i] được xác định bởi các lời giải con như sau  Trường hợp đặc biệt, nếu wi > W (kích thước item i lớn hơn cả kích thước ba lô, thì       ii viwjK ijK ijK ]1,[ ]1,[ max],[ ]1,[],[  ijKijK Sử dụng DP cho Knapsack 0-1 14  Giả sử đã tìm được K[j,i-1], hỏi cách tìm K[j, i]  Trả lời câu hỏi là có nên lấy item i bỏ vô balô (và có thể lấy các item khác ra cho có chỗ) không?  Nghĩa là chọn giữa  𝑲[ 𝒋 − 𝒘𝒊, 𝒊 − 𝟏] + 𝒗𝒊 (sử dụng item i)  𝑲[ 𝒋𝒊, 𝒊 − 𝟏] (không sử dụng item i) Sử dụng DP cho Knapsack 0-1 15 K[ j,0] = 0 K[ j,i ] = max( K[ j-wi,i-1] +vi , K[ j,i-1] ) nếu j  wi K[ j,i ] = K[ j, i-1 ] nếu j < wi Công thức hồi quy trong thuật giải DP cho bài toán ba lô 0-1 Bảng kết quả ba lô 0-1 16 Hình minh hoạ từ dưới lên trên, cột biểu diễn kích thước ba lô, hàng biều diễn số lượng item Bảng kết quả ba lô 0-1 17 Bảng kết quả ba lô 0-1 18  Cần giữ lại lời giải con nào đã chọn (để còn biết là các item nào trong ba lô) Bảng kết quả ba lô 0-1 19  Theo hình trên, chúng ta sẽ ghi kết quả vào ma trận từ bottom-up, trái-phải Bảng kết quả ba lô 0-1 20  Theo vết chúng ta sẽ biết được các item trong ba lô. • Kết quả: item 8, 5, 4, 2. Thuật giải cho bài toán ba lô 0-1 21 for j  0 to m do K[ j,0 ]  0 for i  1 to n do for j  0 to n K[ j,i ] K[ j,i-1 ] if j  wi and vi+K[ j-wi,i-1 ] > K[ j,i-1] then K[ j,i ] vi+K[ j-wi,i-1 ] Thuật giải cho bài toán ba lô 0-1 22 Thuật giải cho bài toán ba lô 0-1 23 for j  0 to m do K[ j,0 ]  0 for i  1 to n do for j  0 to m K[ j,i ]  K[ j,i-1 ] Get [ j,i]  false if j  wi and vi+K[ j-wi,i-1 ] > K[ j,i] then K[ j,i ] vi+K[ j-wi,i-1 ] Get [ j,i ]  true Thuật giải output các item có trong ba lô j  M for i  n downto 1 do if Get[ j,I ] then print(i); j j-wi Ví dụ minh hoạ ba lô 0-1 24 Phát triển vấn đề ba lô 0-1 25  Giải quyết ra sao nếu trọng lượng hay kích thước (ba lô và item) là số thực (và có thể giá trị cũng là số thực). Xét trường hợp giá trị nguyên trước.  Xét L[0..S, 0..n], trong đó L[j, i] là trọng lượng (hay kích thước) tối thiểu của các item (chỉ dùng các item 1, ..i) với tổng giá trị >= j trong ba lô.  S = tổng giá trị của tất cả item. Phát triển vấn đề ba lô 0-1 26 L[ j,0 ] = 0 L[ 0,i ] = ? L[ j,i ] = min ( L[j,i-1] , L[j-vi,i-1] + wi ) Chọn item i Không chọn item i L[ j,i-1] L[ j-vi , i-1] + wi if j  vi Phát triển vấn đề ba lô 0-1 27 for j 0 to S do L[ j,0 ] 0 for i 0 to n do for j 0 to S do L[ j,i ] = L[ j,i-1] if j vi and L[ j-vi,i-1 ] + wi < L[ j,i ] then L[ j,i ]  L [ j-vi, i-1 ] + wi Bài tập ba lô 0-1 28 1. Hãy xây dựng bảng kết quả ba lô 0-1 với các đầu vào như sau  W = 17 2. Điều gì xảy ra nếu các item không theo thứ tự tăng như trên. Item Kích thước (wi) Giá trị (vi) 1 1 3 2 3 6 3 4 17 4 7 19 5 9 21 6 10 27 Bài toán nhân dãy ma trận 29  Đặt vấn đề: nhân dãy N các ma trân A1.A2...An, sao cho số phép nhân ít nhất.  Thuật giải đơn giản: nhân A1 cho A2, lấy ma trận KQ nhân A3, cứ tiếp tục như vậy cho đến ma trận An.  Nhận xét rằng, phép nhân ma trận có tính kết hợp, vì vậy có thể nhân theo thứ tự khác (vd như từ cuối lên đầu).  Thứ tự nhân ảnh hưởng đến tổng số phép nhân cần thực hiện  cần xác định thứ tự tối ưu. Nhân dãy ma trận-Ví dụ 30  Cho các ma trận: A1(10x100), A2(100x5), A3(5x50), A4(50x1) A1A2A3A4 sẽ là ma trận 10x1.  Có 5 thứ tự nhân  (A1(A2(A3A4)))  ((A1A2)(A3A4))  (((A1A2) A3) A4)  ((A1(A2A3)) A4)  (A1((A2A3) A4))  Đặt: Aij = Ai...Aj. Số phép nhân cho từng cách là Nhân dãy ma trận-Ví dụ 31 • (A1(A2(A3A4)))  A34=A3A4, có 250 phép nhân, kq là ma trận 5x1.  A24=A2A34, có 500 phép nhân, kq là ma trận 100x1.  A14=A1A24, có 1000 phép nhân, kq là ma trận 10x1. Cần 1750 phép nhân cho thứ tự nhân trên • (A1A2)(A3A4))  A12=A1A2, có 5000 phép nhân, kq là ma trận 10x5.  A34=A3A4, có 250 phép nhân, kq là ma trận 5x1.  A14=A12A34, có 50 phép nhân, kq là ma trận 10x1. Cần 5300 phép nhân cho thứ tự nhân trên Nhân dãy ma trận-Ví dụ 32 • (((A1A2)A3) A4)  A12=A1A2, có 5000 phép nhân, kq là ma trận 10x5.  A13=A12A3, có 2500 phép nhân, kq là ma trận 10x50.  A14=A13A4, có 500 phép nhân, kq là ma trận 10x1. Cần 800 phép nhân cho thứ tự nhân trên • ((A1(A2A3)) A4)  A23=A2A3, có 25000 phép nhân, kq là ma trận 100x50.  A13=A1A23, có 50000 phép nhân, kq là ma trận 10x50.  A14=A13A4, có 500 phép nhân, kq là ma trận 10x1. Cần 75500 phép nhân cho thứ tự nhân trên Nhân dãy ma trận-Ví dụ 33 • (A1 ((A2A3)A4))  A23=A2A3, có 25000 phép nhân, kq là ma trận 100x50.  A24=A23A4, có 5000 phép nhân, kq là ma trận 100x1.  A14=A1A24, có 1000 phép nhân, kq là ma trận 10x1. Cần 31000 phép nhân cho thứ tự nhân trên • Nhận xét 1: thứ tự nhân là quan trọng. • Nhận xét 2: bài toán trở thành xác định vị trí thích hợp cho các dấu ngoặc. • Số cách đặt dấu ngoặc là:     1 1 )().()( n i inTiTnT  2/3/4)( nOnT n Nhân dãy ma trận với DP 34  Nhận xét: công thức trong DP luôn có tính đệ quy. Chúng ta có thể cài đặt theo các phương pháp  Đệ quy bình thường (dạng chia để trị: top-down)  Vòng lặp (bottom-up).  Đặt: M[i, j] là số phép nhân dãy ma trận Mi...Mj  Mỗi ma trận Mk có chiều là pk-1 x pk.  Chiều của các ma trận lưu trữ trong mảng một chiều: P = . i=1, n, j = 1, n. Nhân dãy ma trận với DP 35  Công thức xác định số phép nhân tối ưu là:  Yêu cầu cuối cùng là xác định m[1,n].  Ngoài ra cần giữ lại vị trí tối ưu của các dấu ngoặc.          jipppjkmkim ji jim jki jki )],1[],[min( 0 ],[ 1 Nhân dãy ma trận với DP-Ví dụ 36 A1(30x35), A2(35x15), A3(15x5), A4(5x10), A5(10x20), A6(20x25) Nhân dãy ma trận với DP-Ví dụ 37 Vị trí các dấu ngoặc Mã nguồn DP nhân dãy ma trận 38 Matrix_Chain_Order (P) { //P mảng một chiều chứa số chiều của Ai n = length(P) – 1 for i = 1, n m[i,i] = 0 for L = 2, n for i = 1, n – L + 1 j = i + L – 1 m [i, j] = ∞ for k = i, j-1 q = m[i, k] + m[k+1, j] + pi-1pkpj if q < m[i,j] m[i,j] = q s[i,j] = k return m and s } Mã nguồn đệ quy nhân dãy ma trận 39 RMC(P, i, j) { if i = j return 0 m [i, j] = ∞ for k = i, j-1 q = RMC(P, i, k) + RMC(P, k+1, j) + pi-1pkpj if q < m[i,j] m[i,j] = q s[i,j] = k return m[i,j] and s } Tóm tắt DP 40  Định dạng vấn đề (hiển nhiên cho mọi bài toán)  Định nghĩa đệ quy giá trị của lời giải tối ưu  Cách tính toán giá trị của lời giải tối ưu (top-down, bottom-up)  Theo vết để xác định lời giải tối ưu. Một số vấn đề giải quyết với DP 41  Cho hai chuỗi: xây dựng thuật giải xác định chuỗi giống nhau dài nhất của hai chuỗi đã cho (xem tài liệu)  Xác định mức độ tương tự của hai chuỗi (ứng dụng trong: kiểm tra từ, từ điển web, computational biology. Một số vấn đề giải quyết với DP Bài toán Sequence Alignment 42  Giải quyết vấn đề sequence alignment trong computational biology Một số vấn đề giải quyết với DP Bài toán Sequence Alignment 43  Input: 2 chuỗi X=x1x2..xM, và Y=y1y2..yN.  Ký hiệu: {1, 2,..,M}, và {1, 2,..,N} là vị trí  2 chuỗi.  Matching: tập các cặp vị trí (i, j) sao cho mỗi item xuất hiện tối đa trong 1 cặp.  Alignment: matching sao cho không có crossing, nghĩa là.  Mục tiêu: tìm alignment sao cho cost nhỏ nhất. Một số vấn đề giải quyết với DP Bài toán tìm cực tiểu lỗi nhỏ nhất 44  Cho N điểm trong mặt phẳng hai chiều , tìm đường thẳng y = ax+b sao cho cực tiểu lỗi Lỗi đạt cực tiểu khi thoả Một số vấn đề giải quyết với DP Bài toán tìm cực tiểu lỗi nhỏ nhất 45 3. Cho n điểm trong mặt phẳng hai chiều , tìm các đoạn thẳng (không phải một đường thẳng) sao cho cực tiểu lỗi (miễn thi 1 sinh viên)  Cực tiểu tổng của các tổng lỗi bình phương E trên từng đoạn thẳng.  Cực tiểu L số đoạn thẳng. 0,  ccLEHàm định dạng vấn đề Đặt OPT(j)= minimum cost của các điểm p1, p2, ..., pj. e(i, j)= lỗi cực tiểu của các điểm pi, pi+1,.., pj