GVGD: Trng Phc Hi
Phng pháp quy hoch đng
(dynamic programming)
2 Trng Phc Hi
Ni dung
1. Nguyên lý quy hoch đng
3. Phng pháp quy hoch đng
4. Mt s bài toán ng dng
2. Công thc truy hi
3 Trng Phc Hi
Nguyên lý quy hoch đng
 Chia đ tr là phng pháp ch đo trong vic thit
k các thut toán có tính cht đ quy

 Chia đ tr phân nh bài toán và gii quyt đc lp
tng phn mt cách đ quy

 T tng đ quy d hiu và d cài đt nhng tiêu
tn nhiu b nh (stack lu tr các li gi)
4 Trng Phc Hi
Nguyên lý quy hoch đng
 Xét bài toán

 Tìm phn t th N ca dãy Fibonacci

 Dãy đc đnh ngha F
N
= F
N-1
+ F
N-2

vi F
0
= F
1
= 1

 Gii bng phng pháp chia đ tr

 Chia: F
n
đc chia thành F
N-1
và F
N-2


 Tr: tính F
N-1
và F
N-2
mt cách đ quy

 Gp: tính tng F
N-1
+ F
N-2
đ đc F
N

5 Trng Phc Hi

Nguyên lý quy hoch đng
 Gii thut chia đ tr cho bài toán


F(N)
If (N = 0) Or (N = 1) Then
Return 1
End If

Return F(N - 1) + F(N - 2)
End F


6 Trng Phc Hi
Nguyên lý quy hoch đng
 Minh ha s đ gii bài toán tính F(5)
F(5)
3
8
F(4) F(3)
5
F(3) F(2) F(1) F(2)
F(2) F(1)
F(1) F(0)
F(1) F(0) F(1) F(0)
3 2 2 1
1 1 1 1 1 2
1 1
7 Trng Phc Hi
Nguyên lý quy hoch đng

  phc tp ca gii thut chia đ tr áp dng cho
bài toán Fibonacci

 T(N): thi gian tính F(N)

 Phng trình đ quy biu din thi gian tính T(N)

 T(N) = T(N-1) + T(N-2)

 Gii phng trình đ quy trên ta đc
  
 






8 Trng Phc Hi
Nguyên lý quy hoch đng
 Xây dng li gii ca mt bài toán thông qua li
gii ca các bài toán con

 Các bài con tip tc đc chia nh đ gii quyt
nhng không s dng k thut đ quy

 S dng bng tra cu đ lu li kt qu đã tính
đc và tính dn đn nghim ca bài toán bng
mt công thc xác đnh
9 Trng Phc Hi

Ni dung
1. Nguyên lý quy hoch đng
3. Phng pháp quy hoch đng
4. Mt s bài toán ng dng
2. Công thc truy hi
10 Trng Phc Hi
Công thc truy hi
 Trong quá trình quay lui, đ quy s gi li nhiu
ln các bài toán con đã đc gi  các bc trc

 Gây tiêu tn thi gian thc hin lp li và tài nguyên b
nh

 Lu tr nghim ca tt c bài toán con và kt hp chúng
theo mt công thc xác đnh đ tìm nghim cho bài toán
ban đu

 Công thc kt hp nghim ca các bài toán con đ
tìm nghim ca bài toán ln hn gi là công thc
truy hi
11 Trng Phc Hi
Công thc truy hi
 Ví d 1

 Xét li bài toán tìm phn t th N ca dãy Fibonacci

 Gii bài toán  mt cách nhìn khác

 S dng bng tra lu li giá tr các s Fibonacci nhm tính
dn cho các s Fibonacci tip theo

12 Trng Phc Hi
Công thc truy hi
 To mng lu kt qu đ tra cu

 Gi F[i] là giá tr ca phn t Fibonacci th i, vy phn t
th N ca dãy Fibonacci là F[N]. Ta có

 F[0] = F[1] = 1

 Công thc truy hi

 F[i] = F[i-1] + F[i-2], vi 2 ≤ i ≤ N
1 1 ? ? ?
0 1 2 3 …
?
?
?
N
13 Trng Phc Hi
Công thc truy hi
 Gii thut s dng công thc truy hi vi đ phc
tp O(N)

Fibonacci(N)
F[0] = 1
F[1] = 1

For (i = 2; i <= N; i++)
F[i] = F[i-1] + F[i-2]
End For


Return F[N]
End Fibonacci
14 Trng Phc Hi
Công thc truy hi
 Cài đt ngôn ng

int Fibonacci(int N)
{

int F[MAX];
F[0] = F[1] = 1;
for (int i = 2; i <= N; i++)
F[i] = F[i-1] + F[i-2];


return F[N];
}
15 Trng Phc Hi
Công thc truy hi
 Ví d 2

 T hp chp k ca N phn t đc đnh ngha nh sau





 Cho 2 s nguyên dng k ≤ N. Tính 



















 



16 Trng Phc Hi
Công thc truy hi
 To bng lu tr nghim ca các bài toán con

 Gi C[i][j] là giá tr ca 


, vy giá tr ca 



là C[N][k].
Ta có
 C[0][j] = 0,j (vì 


)
 C[i][0] = 1, i (vì 


)

 Công thc truy hi

 C[i][j] = C[i-1][j] + C[i-1][j-1],  i  [1 N], j  [1 k]



17 Trng Phc Hi
Công thc truy hi
 Minh ha quá trình xây dng bng đ tính C[N][k]
0

1

2

3

4


5

0

1

0

0

0

0

0

1

1

2

1

3

1

4


1

5

1

0 0 0 0 1
0 0 0 1 2
0 0 1 3 3
0 1 4 6 4
1 5 10 10 5
18 Trng Phc Hi
Công thc truy hi
 Gii thut s dng bng tra cu đ phc tp O(n
2
)

ToHop(N, k)
For (j = 0; j <= k; j++) C[0][j] = 0
For (i = 0; i <= N; i++) C[i][0] = 1

For (j = 1; j <= k; j++)
For (i = 1; i <= N; i++)
C[i][j] = C[i-1][j] + C[i-1][j-1]

End For
End For

Return C[N][k]


End ToHop
19 Trng Phc Hi
Công thc truy hi
 Cài đt ngôn ng

int ToHop(int N, int k)
{

for (int i = 0; i <= N; i++)
C[i][0] = 1;
for (int j = 1; j <= k; j++)
C[0][j] = 0;


for (int j = 1; j <= k; j++)
for (int i = 1; i <= N; i++)
C[i][j] = C[i-1][j] + C[i-1][j-1];

return C[N][k];
}
20 Trng Phc Hi
Ni dung
1. Nguyên lý quy hoch đng
3. Phng pháp quy hoch đng
4. Mt s bài toán ng dng
2. Công thc truy hi
21 Trng Phc Hi
Phng pháp quy hoch đng
 Quy hoch đng do Bellman đ xut nhm gii

quyt các bài toán ti u có bn cht đ quy

 Quy hoch đng có c s là nguyên lý ti u
Bellman

 Nu đng đi t A đn B là ti u và gi s đng đi này
qua trung gian C thì đng đi t C đn B cng ti u

 Quy hoch đng bt đu t vic tìm nghim tt c
bài toán c s và kt hp chúng đ dn tìm nghim
ca bài toán ban đu
22 Trng Phc Hi
Phng pháp quy hoch đng
 Quy hoch đng gii bài toán theo phng pháp
ln ngc lên (bottom-up)

 Chia nh bài toán thành các bài toán con nh nht và tìm
nghim ca chúng (
c s quy hoch đng)

 Lu tr nghim ca các bài toán con vào bng tra cu
(bng phng án quy hoch đng)

 S dng công thc truy hi đ ln gii các bài toán ln hn
dn đt đc bài toán ban đu
23 Trng Phc Hi
Phng pháp quy hoch đng
 iu kin đ áp dng phng pháp quy hoch
đng cho các bài toán


 Nghim ca bài toán có th xác đnh đc t nghim ca
các bài toán con (xác đnh công thc truy hi)

 Nghim ca các bài toán con có th đc lu tr đc theo
mt hình thc chp nhn đc (bng phng án)

 Xác đnh công thc truy hi là công vic ch yu
và phc tp nht ca phng pháp quy hoch đng
24 Trng Phc Hi
Phng pháp quy hoch đng
 Các bc gii mt bài toán bng phng pháp quy
hoch đng

 Tìm công thc xây dng nghim ca bài toán thông qua
nghim ca các bài toán nh hn: công thc truy hi

 Tìm nghim ca bài toán con nh nht: xác đnh c s quy
hoch đng

 To bng lu tr nghim ca các toán con và tính dn
nghim ca các bài toán ln hn da vào công thc truy
hi: bng phng án quy hoch đng
25 Trng Phc Hi
Phng pháp quy hoch đng
 Quy hoch đng không hiu qu trong các trng
hp sau

 Không tìm đc công thc truy hi

 S lng bài toán con quá nhiu, kích thc bng phng

án quá ln

 S kt hp nghim ca các bài toán con cha chc tìm
đc nghim ca bài toán ban đu