Bài giảng Giải thuật nâng cao - Quy hoạch động - Ngô Quốc Việt

QUY HOẠCH ĐỘNG 
TS. NGÔ QUỐC VIỆT 
2015 
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. 
• Minh họa bài toán ba lô 0-1 
3. Bài tập 
4. DP cho Sequence Alignment 
5. 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. 
So sánh giữa chia để trị và DP 
4 
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 
5 
• 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 
6 
• 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 
7 
• 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 
8 
• 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 
9 
• 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 
10 
• Đặ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 
11 
• 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 
12 
• 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 
13 
• 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 
14 
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 
15 
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 
16 
Bảng kết quả ba lô 0-1 
17 
• 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 
18 
• 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 
19 
• 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 
20 
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 
21 
Thuật giải cho bài toán ba lô 0-1 
22 
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 
23 
Phát triển vấn đề ba lô 0-1 
24 
• 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 
25 
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 
26 
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 
27 
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 
Một số vấn đề giải quyết với DP 
28 
• 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 
29 
• 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 
30 
• 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 
31 
• 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 
32 
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 
Sequence Alignment 
• Định nghĩa: Cho hai chuỗi x = x1x2...xM, y = y1y2yN, 
 an alignment is an assignment of gaps to positions 
• 0,, N in x, and 0,, N in y, so as to line up each 
 letter in one sequence with either a letter, or a gap 
• in the other sequence 
 Giải thuật nâng cao-Lý thuyết số 33 
-AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- 
TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC 
AGGCTATCACCTGACCTCCAGGCCGATGCCC 
TAGCTATCACGACCGCGGTCGATTTGCCCGAC