Bài giảng Phân tích và thiết kế thuật toán - Chương 10: Bài toán quy hoạch động (Dynamic Programming) - Phạm Thế Bảo

14/04/2008
1
BÀI TOÁN QUY HOẠCH ĐỘNG 
(DYNAMIC PROGRAMMING)
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung 
• Kỹ thuật chia để trị thường dẫn tới giải thuật
đệ quyÆ có giải thuật có thời gian mũ và giải
bài toán con nhiều lần.
• Để tránh giải bài toán con nhiều lầnÆ tạo một
bảng lưu trữ kết quả các bài toán con để khi
cần sẽ sử dụng lại kết quả.
Lấ đầ kế ả á bài á h l ậ• p y t qu c c to n con t eo quy u t
nào đó để có kết quả của bài toán ban đầu Æ
quy hoạch động
Phạm Thế Bảo
14/04/2008
2
Thuật giải
1. Tạo bảng bằng cách:
ốa. Gán giá trị một s ô nào đó.
b. Gán giá trị cho các ô khác nhờ vào giá trị của các
ô trước.
2. Tra bảng và xác định kết quả của bài toán ban
đầu
Phạm Thế Bảo
Đánh giá
• Ưu điểm
– Chương trình thực thi nhanh do không tốn thời gian
giải lại bài toán con.
– Vận dụng để giải các bài toán tối ưu, có công thức truy
hồi
• Nhược điểm
– Không tìm được công thức truy hồi.
– Số lượng bài toán con cần giải và lưu trữ kết quả rất
lớn.
– Việc kết hợp lời giải của các bài toán con chưa chắc
cho lời giải của bài toán ban đầu.
Phạm Thế Bảo
14/04/2008
3
Bài toán tính số tổ hợp
• Tính Cnk bằng công thức truy hồi.
0 neáu k=0 hay k=nk ⎧⎨
Thuật giải:
long Comb(int n, int k){
1
k-1
n-1C neáu 0<k<n
n k
n
C
C −
= +⎩
}
Phạm Thế Bảo
Đánh giá
• Gọi T(n) là thời gian tính Cnk , 
ta có T(1)=C1 và T(n)=
giải ta có T(n)=O( ) 
Æ bài toán con được giải nhiều lần
Comb(4,2)
Phạm Thế Bảo
Comb(2,0)
Comb(3,2)Comb(3,1)
Comb(2,2)Comb(2,1)Comb(2,1)
14/04/2008
4
Dùng quy hoạch động
• Xây dựng một bảng có (n+1) dòng từ 0 đến n và
(n+1) cột từ 0 đến n. Điền các giá trị ô(i,j) theo
ê tắnguy n c sau:
– ô(0,0)=1 ô(i,i)=1 với 0<i≤n
– ô(i,0)=1 ô(i,j)=ô(i-1,j-1)+ô(i-1,j) với 0<j<i≤n
• Ví dụ n=4
0 1 2 3 4
0 1
Phạm Thế Bảo
1 1 1
2 1 1
3 1 1
4 1 1
Tam giác Pascal
• Thuật giải mới:
int ** Comb(int n, int k){
C[0,0]=1;
for i=1 to n do
C[i,0]=1;
C[i,i]=1;
for j=1 to i-1 do
C[i,j]=C[i-1,j-1]+C[i-1,j];
endfor
return C;
}
• Vòng lặp for j thực hiện i-1 lần. Vòng lặp i lặp
n lầnÆ
Phạm Thế Bảo
14/04/2008
5
Bài toán cái ba lô
• Giả sử X[k,V] là số lượng đồ vật k được chọn,
F[k V] tổng giá trị k đồ vật được chọn và V là,
trọng lượng còn lại của ba lô, k=1..n và
V=1..W.
• Trường hợp đơn giản nhất: chỉ có một đồ vật,
ta tính X[1,V] và F[1,V] với V=1..W như sau:
X[1 V] V di à F[1 V] X[1 V]*– , = v g1 v , = , v1
– Với g1 là trọng lượng đồ vật 1 và v1 là giá trị đồ
vật 1
Phạm Thế Bảo
• Giả sử tính được F[k-1,V], khi có thêm đồ vật thứ
k, ta sẽ tính được F[k,V] như sau: nếu chọn xk đồ
vật loại k, thì trọng lượng còn lại của ba lô dành
cho k-1 đồ vật từ 1 đến k-1 là U=V-xk*gk và tổng
giá trị k loại đồ vật đã được chọn là F[k V]=F[k-,
1,U]+xk*vk với xk từ 0 đến yk=V div gk và ta sẽ
chọn xk sao cho F[k,V] lớn nhất.
• Công thức truy hồi:
– X[1,V]=V div g1 và F[1,V]=X[1,V]*v1
F[k V]=max{F[k 1 V x *g ]+x *v } với x chạy từ 0– , - , - k k k k k
đến (V div gk )
– Sau khi xác định được F[k,V] thì X[k,V] là xk
Phạm Thế Bảo
14/04/2008
6
• Để lưu các giá trị trung gian trong quá trình tính
F[k,V], ta dùng một bảng có n dòng (từ 1 đến n) –
dòng thứ k ứng với loại đồ vật k, và W+1 cột (từ
0 đến W), cột thứ V ứng với trọng lượng V, mỗi
ồcột Vv g m 02 cột nhỏ: cột bên trái lưu F[k,V],
cột bên phải lưu X[k,V].
• Ví dụ: có 05 lọai đồ vật như bảng, ba lô có trọng
lượng W=9. Đồ vật Trọng lượng(gi) Giá trị(vi)
1 3 3
Phạm Thế Bảo
2 4 5
3 5 6
4 2 3
5 1 1
0 1 2 3 4 5 6 7 8 9
1 0 0 0 0 0 0 1 4 1 4 1 8 2 2 8 2 12 3
2 0 0 0 0 0 0 4 0 5 1 5 1 8 0 9 1 10 2 12 0
3 0 0 0 0 0 0 4 0 5 0 6 1 8 0 9 0 10 0 12 0
4 0 0 0 0 3 1 4 0 6 2 7 1 9 3 10 2 12 4 13 3
vk
5 0 0 1 1 3 0 4 0 6 0 7 0 9 0 10 0 12 0 13 0
Đồ vật gi vi
1 3 3
2 4 5
3 5 6
4 2 3
• Cách tính:
– Dòng thứ nhất, dùng công thức X[1,V]=V div g1 và F[1,V]=X[1,V]*v1
– Từ dòng 2 đến dòng 5 dùng công thức truy hồi F[k,V]=max{F[k-1, V-
xk*gk]+xk*vk} với xk chạy từ 0 đến (V div gk ).
– Ví dụ: tính F[2,7] , 
có xk={0 div 4, 1 div 4, 2 div 4, 3 div 4, 4 div 4, 5 div 4, 6 div 4, 7 div 
Phạm Thế Bảo
5 1 1
4}= {0,1}.
F[2,7] =Max{F[2-1,7-0*4]+0*5, F[2-1,7-1*4]+1*5}
=Max{F[1,7], F[1,3]+5} = Max{8,4+5} 
=
Vậy X[2,7]=1
14/04/2008
7
• Vấn đề tra bảng như thế nào để có kết quả?
– Khởi đầu trọng lượng ba lô V=W.
– Xét các đồ vật từ n đến 1, mỗi đồ vật k ứng với trọng
lượng còn lại V của ba lô, nếu X[k,V]>0 thì chọn
X[k,V] đồ vật loại k, tính lại V=V-X[k,V]*gk.
• Ví dụ: V=W=9
– Xét k=5, có X[5,9]=0Æ không chọn
– Xét k=4, có X[4,9]=3Æ chọn 3 đồ vật loại 4, tính lại
V=9-3*2=3.
– Xét k=3, có X[3,3]=0Æ không chọn
– Xét k=2, có X[2,3]=0Æ không chọn
– Xét k=1, có X[1,3]=1 Æ chọn 1 đồ vật loại 1, tính lại
V=3-1*3=0
– Tổng trọng lượng các vật trong ba lô=
– Tổng giá trị các vật trong ba lô =
Phạm Thế BảoBài tập: cài đặt chương trình
Bài toán người giao hàng
• Chúng ta cũng có thể dùng quy hoạch động để
iải ếtg quy :
– Đặt S={x1, x2, , xk} là tập con các cạnh của đồ thị
G=(V,E). Ta nói một đường đi từ v đến w phủ lên S
nếu P={v, x1, x2, , xk, w}, trong đó xi xuất hiện ở vị
trí bất kỳ, chỉ một lần.
ế– Ví dụ: đường đi từ a đ n f phủ lên {c,d,e,g}
Phạm Thế Bảo
a
c
f
e
g
d
14/04/2008
8
– Ta định nghĩa d(v,w,S) là tổng độ dài đường đi từ v
đến w phủ lên S. Nếu không có đường đi như vậy thì
đặt d(v,w,S)=∞.
– Một chu trình Hamilton nhỏ nhất Hmin của G phải có
tổng độ dài là d(Hmin)=d(o,o,V-{o}), với o là một đỉnh
nào đó trong V.
– Ta tìm Hmin như sau:
• Nếu |V |=1 (G chỉ có 1 đỉnh) thì d(Hmin)=0
• Ngược lại:
o d(v,w,{})=d(v,w)
o d(v,w,S)=min {d(v,x)+d(x,w,S-{x})}, với mọi x∈S
ố ế ồo d(v,w) là độ dài cạnh n i hai đỉnh v và w, n u không t n tại thì
d(v,w)= ∞
• Bằng cách lưu trữ các đỉnh x theo công thức đệ quy trên,
chúng ta sẽ có một chu trình Hamilton tối thiểu.
Phạm Thế Bảo