Quy ho ch ng - Presentation Transcriptạ độ
Ch ng III: Qui ho ch ng (Dynamic Programming) ươ ạ độ
Gi i thi u ớ ệ
Ph ng pháp th c hi n ươ ự ệ
M t s bài toán t i u gi i b ng ph ng pháp quy ho ch ng ộ ố ố ư ả ằ ươ ạ độ
1. Gi i thi u ớ ệ
Vi c th c hi n m t gi i thu t quy có th không t i u v m t th i gian/không gian nh . ệ ự ệ ộ ả ậ đệ ể ố ư ề ặ ờ ớ
Ví d : Tính ph n t th n c a dãy s Fibonaci ụ ầ ử ứ ủ ố
Function F(n: integer): integer;
2 then F:=1 Begin If n
else F:= F(n-1)+F(n-2);
End;
1.61803 ... ph c t p: O(a n ) v i a Độ ứ ạ ớ
Do F(n-1) và F(n-2) c tính m t cách c l p! S l n g i c n tính F(n) là s l n g i tính F(n-1) c ngđượ ộ độ ậ ố ầ ọ ầ để ố ầ ọ để ộ
v i s l n g i tính F(n-2). ớ ố ầ ọ để
c i m c a l i gi i quy: th c hi n bài toán t vi c phân tích m c cao xu ng m c th p. Đặ đ ể ủ ờ ả đệ ự ệ ừ ệ ở ứ ố ứ ấ
N u gi i quy t bài toán này t m c th p lên m c cao ta có gi i thu t sau: ế ả ế ừ ứ ấ ứ ả ậ
Function F(n: integer): integer;
var i: integer; a: array[1..100] of integer;
Begin
a[1]:=1; a[2]:=1;
For i:=3 to n do
a[i]:=a[i-1]+a[i-2];
F:= a[i];
End;
ph c t p: O(n) Độ ứ ạ
c i m c a l i gi i bài toán theo ph ng pháp quy ho ch ng: gi i quy t bài toán quy t m c th pĐặ đ ể ủ ờ ả ươ ạ độ ả ế đệ ừ ứ ấ
tr c, l i gi i c a chúng c l u l i và c s d ng tìm l i gi i c a các bài toán m c cao h n. ướ ờ ả ủ đượ ư ạ đượ ử ụ để ờ ả ủ ở ứ ơ
T t ng c a ph ng pháp ư ưở ủ ươ
S d ng nguyên lý: “chia tr ” ử ụ để ị
Cách ti p c n: “d i-lên” ế ậ ướ
Ph m vi áp d ng ạ ụ
Các bài toán có c b ng vi c t h p các nghi m c a các bài toán con đượ ằ ệ ổ ợ ệ ủ
Các bài toán t i u hoá r i r c ố ư ờ ạ
Nguyên lý c a ph ng pháp: ủ ươ
Nguyên lý t i u c a Bellman: Trong m t dãy t i u c a các l a ch n thì m t dãy con c a nó c ng là t i u. ố ư ủ ộ ố ư ủ ự ọ ộ ủ ũ ố ư
2. Ph ng pháp th c hi n ươ ự ệ
Phân tích bài toán (bi u di n bài toán d i d ng m t bài toán nhi u m c) ể ễ ướ ạ ộ ề ứ
Xây d ng gi i pháp quy (l p công th c truy h i) ự ả đệ ậ ứ ồ
L p b ng (s d ng các m ng tính toán các giá tr theo ki u d i-lên) ậ ả ử ụ ả để ị ể ướ
T ng h p k t qu (ki n t o m t l i gi i cho bài toán t các thông tin ã tính toán) ổ ợ ế ả ế ạ ộ ờ ả ừ đ
Xét ví d trên ụ
Phân tích bài toán: Xây d ng hàm: ự
Function F(n: integer): integer;
Gi i pháp quy: F(n) = F(n-1)+F(n-2) ả đệ
L p b ng: S d ng m ng 1 chi u a (array[1..max] of integer) tính: a[i] = F(i). v i i = 1..n . ậ ả ử ụ ả ề để ớ
C th : ụ ể
a[1] = a[2] = 1, và:
a[i] = a[i-1] + a[i-2]; v i i = 3..n, ớ
T ng h p k t qu : F(n) = a[n]; ổ ợ ế ả
ph c t p tính toán: O(n) Độ ứ ạ
Ví d tính C(k,n): t h p ch p k c a n ụ ổ ợ ậ ủ
Phân tích bài toán: Xây d ng hàm: ự
Function C(k, n: byte): longint; {gi thi t k<=n} ả ế
Gi i pháp quy: C(k,n) = C(k-1,n-1) + C(k,n-1) ả đệ
L p b ng: S d ng m t m ng 2 chi u a (array[0..max,0..max] of longint) tính: ậ ả ử ụ ộ ả ề để
a[i,j] = C(i,j), v i i = 0..k , j = i..n ớ
i j và a[i,i] = 1, C th : a[0,j] = 1, ụ ể
ng c l i: a[i,j] = a[i-1,j-1] + a[i,j-1] ượ ạ
T ng h p k t qu : C(k,n) = a[k,n] ổ ợ ế ả
ph c t p tính toán: O(k.n) Độ ứ ạ
3. M t s bài toán t i u gi i b ng ph ng pháp quy ho ch ng ộ ố ố ư ả ằ ươ ạ độ
Chi c túi xách ế
Phép nhân t h p nhi u ma tr n ổ ợ ề ậ
Các bài t p ậ
Bài toán chi c túi xách ế
M t cái kho ch a n lo i v t có kích th c và giá tr khác nhau. C th : ộ ứ ạ đồ ậ ướ ị ụ ể
N* Lo i v t i (i=1..n) có: - kích c m[i] ạ đồ ậ ỡ
R - gía tr c[i] ị
- s l ng: không h n ch ố ượ ạ ế
N*. V y h n ph i ch n l aậ ắ ả ọ ự ựM t tên tr m mang theo chi c túi có kích c là p m t danh sách các v t sộ ộ ế ỡ ộ đồ ậ ẽ
mang i nh th nào cho t ng giá tr l y c p c là l n nh t. đ ư ế để ổ ị ấ ắ đượ ớ ấ
N : s l ng lo i v t th i c nố ượ ạ đồ ậ ứ ầ ầ T c: Tìm x[1], x[2],..., x[n] (v i x[i] x[i].c[i] t giá tr c c iứ ớ đạ ị ự đạ ạ p và
x[i].m[i] x l y) sao cho: ấ
Bài toán chi c túi xách ế
Phân tích bài toán:
G i P (r, s) là bài toán chi c túi xách, v i: ọ ế ớ
N*: kích c chi c túiỡ ế ế r
N*: s các lo i v t khác nhauố ạ đồ ậ ậ s
(bài toán ban u là P (p, n) ) đầ
Các giá tr c n tìm: ị ầ
x[i].c[i] c a bài toán P (r, s)ủ ủl[r,s]: giá tr c c i ị ự đạ
u[r,s]: s l ng lo i v t s t i u c n l y (t c: x[s]) c a bài toán P (r, s) ố ượ ạ đồ ậ ố ư ầ ấ ứ ủ
Bài toán chi c túi xách P (r, s) ế
Gi i pháp quy: ả đệ
Khi s = 1:
u[r, 1] = r div m[1]
c[1] l[r, 1] = u[r, 1]
Khi s > 1:
m[s], s-1] } c[s] + l[r – k l[r, s] = max { k
r div m[s] k 0
m[s], s-1] c[s] + l[r – k’ = k’
u[r, s] = k’
L p b ng (Bài toán chi c túi xách) ậ ả ế
Procedure LapBang;
Begin
For r:=0 to p do
For s:=1 to n do
If s=1 then Tính u[r, 1] và l[r, 1]
else Tính u[r, s] và l[r, s];
End;
ph c t p tính toán: O(np 2 ) Độ ứ ạ
T ng h p k t qu (Bài toán chi c túi xách) ổ ợ ế ả ế
Procedure TongHop;
Begin
r:=p;
For s:=n downto 1 do
begin
x[s]:= u[r,s];
r:= r – x[s].m[s];
end;
End;
ph c t p tính toán: O(n) Độ ứ ạ
Bài toán Phép nhân t h p nhi u ma tr n ổ ợ ề ậ
M n ... M 2 C n tính M = M 1 ầ
m[i] (i=1..n) Trong ó: M i là ma tr n c p m[i-1] đ ậ ấ
Hãy xác nh th t th c hi n các phép nhân sao cho s phép tính là t i thi u. đị ứ ự ự ệ ố ố ể
M 3 M 2 Ví d : Tính M = M 1 ụ
5] 50] [50 20] [20 [10
M 3 có s phép toán là:ố ố M 2 ) ( M 1
5 = 12500 50 50 + 1 0 20 10
M 3 ) có s phép toán là:ố ố ( M 2 M 1
5 = 6000 50 5 + 2 0 20 10
Phép nhân t h p nhi u ma tr n ổ ợ ề ậ
Phân tích bài toán:
s M s , v i r ớ ớ ... M r+1 G i P (r, s) là bài toán nhân ma tr n: M r ọ ậ
(bài toán ban u là P (1, n) ) đầ
Giá tr c n tìm: ị ầ
k[r,s]: v trí phép toán th c hi n cu i cùng c a bài toán P (r, s) ị ự ệ ố ủ
M s ) ... M k+1 ( M k M k-1 ) ... M r+1 (M r
[r+1, s] k = k[r,s]
l[r, s]: s phép tính nhân t i u c a bài toán P (r, s) ố ố ư ủ
Phép nhân t h p nhi u ma tr n ổ ợ ề ậ
Gi i pháp quy: ả đệ
Tr ng h p 1: Khi s = r : l[r, r] = 0 ườ ợ
Tr ng h p 2: Khi s = r+1: ườ ợ
m[r+1] m[r] l[r, r+1] = m[r-1]
k[r, r+1] = r+1
Tr ng h p 3: Khi s > r+1: ườ ợ
m[s] + l[v, s] } m[v-1] l[r, s] = min { l[r, v-1] + m[r-1]
s v r+1
(v là các v trí phép toán th c hi n cu i cùng khác nhau) ị ự ệ ố
m[s] + l[v’, s] m[v’-1] = l[r, v’-1 ] + m[r-1]
(v’ là v trí t i u trong s các v trí c a v) ị ố ư ố ị ủ
k[r, s] = v’
Nh n xét : Có th ghép tr ng h p 2 vào tr ng h p 3! ậ ể ườ ợ ườ ợ
L p b ng (Bài toán phép nhân t h p nhi u ma tr n) ậ ả ổ ợ ề ậ
Procedure LapBang;
Begin
For s:=1 to n do
For r:=s downto 1 do
If r = s then l[r, r] := 0
else Tính l[r, s] và k[r, s];
End;
ph c t p tính toán: O(n 3 ) Độ ứ ạ
T ng h p k t qu (Bài toán phép nhân t h p nhi u ma tr n) ổ ợ ế ả ổ ợ ề ậ
Procedure TongHop;
Begin
writeln(‘S phép tính là t i thi u:’, l[1, n]); ố ố ể
i:=n;
TimVT(1, n); {Nh m l n l t xác nh các giá tr x[i]: v trí phép nhân c n th c hi n trong l n nhân th iằ ầ ượ đị ị ị ầ ự ệ ầ ứ
(i=1..n-1)}
writeln(‘ Th t th c hi n các phép nhân :’); ứ ự ự ệ
For i:=1 to n-1 do writeln(x[i]);
End;
Trong ó th t c TimVT c xây d ng quy nh sau: đ ủ ụ đượ ự đệ ư
Procedure TimVT(r, s);
Begin i:=i-1; vt:= k[r, s]; x[i]:= vt;
If (vt > r+1) and (vt < s) then
begin TimVT(r, vt-1);
TimVT(vt, s);
end;
End;
Bài t p ậ
1. Tính giá tr xác su t P(i, j) (i, j: byte). Bi t r ng: ị ấ ế ằ
P(i, j) = 1 n u i=0 và j>0 ế
= (P(i-1, j)+ P(i, j-1))/2 n u i>0 và j>0 ế
= 0 n u ng c l i ế ượ ạ
Bài toán xâu trong c c i: S là xâu trong c a T n u S nh n c b ng cách xoá i m t s ký t nào ó. Víự đạ ủ ế ậ đượ ằ đ ộ ố ự đ
d : ‘ABC’ là xâu trong c a ‘GAHEBOOC’ ụ ủ
Bài toán: Cho 2 xâu T1, T2. Tìm m t xâu S là xâu trong chung c a T1 và T2 có dài c c i. ộ ủ độ ự đạ
Ví d : T1=‘ABCDAE’ và T2=‘XYACADK’ có xâu ‘ACD’ là xâu trong chung v i dài c c i. ụ ớ độ ự đạ
Bài toán du l ch: M t ng i i t thành ph 0 n thành ph n và có th i ị ộ ườ đ ừ ố đế ố ể đ đ i k i 2 ….. i 1 qua n-1
thành ph khác 1, 2,..., n-1 , theo l trình : 0 n, t rong ó: 0 < i 1 < i 2 < …< i k < n, Giá vé c a xe i t thànhố ộ đ ủ đ ừ
ph i n thành ph j là c[i,j]. Tìm m t l trình t thành ph 0 n thành ph n sao cho t ng chi phí v giá véố đế ố ộ ộ ừ ố đế ố ổ ề
t c c ti u. đạ ự ể
Bài toán sinh viên ôn thi: M t sinh viên còn m ngày ôn thi n môn. Theo kinh nghi m c a anh ta, n u ônộ để ệ ủ ế
môn j trong i ngày thì c i m là a[i,j]. Gi s cho bi t các a[i,j] (v i a[i,j]<=a[i+1,j]). đượ đ ể ả ử ế ớ
x[j]=n và sinh viên tđạ ạ Tìm b x[j] (s ngày ôn môn j, v i j=1..n) sao cho max).ộ ố ớ ớ a[x[j], j] t ng i m l nổ đ ể ớ
nh t ( ấ