Bài giảng Bài toán quy hoạch động (Dynamic programming) - Phạm Thế Bảo
14/04/2008
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ấp đầy kết quả các bài toán con theo quy luật
nào đó để có kết quả của bài toán ban đầu Æ
quy hoạch động
Phạm Thế Bảo
1
14/04/2008
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
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.
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
2
14/04/2008
Bài toán tính số tổ hợp
k
• Tính Cn bằng công thức truy hồi.
neáu k=0 hay k=n
neáu 0<k<n
⎨
⎩
Ck =
n
Ck-1 + Cnk−1
n-1
Thuật giải:
long Comb(int n, int k){
}
Phạm Thế Bảo
Đánh giá
• Gọi T(n) là thời gian tính Cn ,
k
ta có T(1)=Cvà T(n)=
giải ta có T(n)=O( )
Æ bài toán con được giải nhiều lần
Comb(4,2)
Comb(3,1)
Comb(3,2)
Comb(2,0)
Comb(2,1)
Comb(2,1)
Comb(2,2)
Phạm Thế Bảo
3
14/04/2008
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
nguyên tắc sau:
– ô(0,0)=1
– ô(i,0)=1
ô(i,i)=1 với 0<i≤n
ô(i,j)=ô(i-1,j-1)+ô(i-1,j) với 0<j<i≤n
• Ví dụ n=4
0
1
1
1
1
1
1
2
3
4
0
1
2
3
4
1
1
Tam giác Pascal
1
1
Phạm Thế Bảo
• 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
4
14/04/2008
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 div g1 và F[1,V]=X[1,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
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-xk*gk]+xk*vk} với xk chạy từ 0
đến (V div gk )
– Sau khi xác định được F[k,V] thì X[k,V] là xk
Phạm Thế Bảo
5
14/04/2008
• Để 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
2
3
4
5
3
4
5
2
1
3
5
6
3
1
Phạm Thế Bảo
v
0
1
2
3
4
5
6
7
8
9
k
1
2
3
4
5
0 0 0 0 0 0
1 4 1 4 1 8 2
2
1
0
2
0
8
2
2
0
4
0
12
3
0
0
3
0
0 0 0 0 0 0 4 0 5 1 5 1 8 0
0 0 0 0 0 0 4 0 5 0 6 1 8 0
9
9
10
10
12
12
12
12
13
13
0 0 0 0 3 1 4 0 6 2 7 1 9 3 10
0 0 1 1 3 0 4 0 6 0 7 0 9 0 10
• Cách tính:
Đồ vật gi vi
–
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
1
2
3
5
3
4
5
1
3
5
6
1
–
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
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
Phạm Thế Bảo
6
14/04/2008
• 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ô =
Bài tập: cài đặt chương trình
Phạm Thế Bảo
Bài toán người giao hàng
• Chúng ta cũng có thể dùng quy hoạch động để
giải quyết:
– Đặ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}
e
c
d
a
g
f
Phạm Thế Bảo
7
14/04/2008
– 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
8
8 trang
21340
Free
Bạn đang xem tài liệu "Bài giảng Bài toán quy hoạch động (Dynamic programming) - Phạm Thế Bảo", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_bai_toan_quy_hoach_dong_dynamic_programming_pham_t.pdf
