quy hoach dong
Trong ngành khoa h c máy tính, quy ho ch đ ng là m t ph ng pháp gi m th i gianọ ạ ộ ộ ươ ả ờ
ch y c a các thu t toán th hi n các tính ch t c a các bài toán con g i nhauạ ủ ậ ể ệ ấ ủ ố
(overlapping subproblem) và c u trúc con t i u (optimal substructure). ấ ố ư
Nhà toán h c Richard Bellman đã phát minh ph ng pháp quy ho ch đ ng vào nămọ ươ ạ ộ
1953. Ngành này đã đ c thành l p nh là m t ch đ v k ngh và phân tích hượ ậ ư ộ ủ ề ề ỹ ệ ệ
th ng đã đ c t ch c IEEE th a nh n. ố ượ ổ ứ ừ ậ
M c l c [ n] ụ ụ ẩ
1 T ng quan ổ
2 Ví d ụ
2.1 Dãy Fibonacci
2.2 Bàn c ờ
3 Các thu t toán s d ng quy ho ch đ ng ậ ử ụ ạ ộ
4 Liên k t ngoài ế
5 Tham kh o ả
[s a] T ng quan ử ổ
Hình 1. Tìm đ ng đi ng n nh t s d ng c u trúc con t i u; m t đ ng l n sóngườ ắ ấ ử ụ ấ ố ư ộ ườ ượ
đ i di n cho m t đ ng đi ng n nh t gi a hai đ nh mà nó n iC u trúc con t i u cóạ ệ ộ ườ ắ ấ ữ ỉ ố ấ ố ư
nghĩa là các l i gi i t i u cho các bài toán con có th đ c s d ng đ tìm các l iờ ả ố ư ể ượ ử ụ ể ờ
gi i t i u cho bài toán toàn c c. Ví d , đ ng đi ng n nh t t i m t đ nh trong m tả ố ư ụ ụ ườ ắ ấ ớ ộ ỉ ộ
đ th có th đ c tìm th y b ng cách: tr c h t tính đ ng đi ng n nh t t i đích tồ ị ể ượ ấ ằ ướ ế ườ ắ ấ ớ ừ
t t c các đ nh k nó, r i dùng k t qu này đ ch n đ ng đi toàn c c t t nh t, nhấ ả ỉ ề ồ ế ả ể ọ ườ ụ ố ấ ư
trong hình 1. Nói chung, ta có th gi i m t bài toán v i c u trúc con t i u b ng m tể ả ộ ớ ấ ố ư ằ ộ
quy trình ba b c: ướ
Chia bài toán thành các bài toán con nh h n. ỏ ơ
Gi i các bài toán này m t cách t i u b ng cách s d ng đ quy quy trình ba b cả ộ ố ư ằ ử ụ ệ ướ
này.
S d ng các k t qu t i u đó đ xây d ng m t l i gi i t i u cho bài toán ban đ u. ử ụ ế ả ố ư ể ự ộ ờ ả ố ư ầ
Các bài toán con đ c gi i b ng cách chia chúng thành các bài toán nh h n, và cượ ả ằ ỏ ơ ứ
ti p t c nh th , cho đ n khi ta đ n đ c tr ng h p đ n gi n d tìm l i gi i. ế ụ ư ế ế ế ượ ườ ợ ơ ả ễ ờ ả
Hình 2. Đ th bài toán con cho dãy Fibonacci. Đây không ph i là m t c u trúc cây màồ ị ả ộ ấ
là m t đ th có h ng phi chu trình mô t quan h gi a các bài toán con g i nhau.Nóiộ ồ ị ướ ả ệ ữ ố
r ng m t bài toán có các bài toán con trùng nhau có nghĩa là m i bài toán con đó đ cằ ộ ỗ ượ
s d ng đ gi i nhi u bài toán l n h n khác nhau. Ví d , trong dãy Fibonacci, F3 = F1ử ụ ể ả ề ớ ơ ụ
+ F2 and F4 = F2 + F3 - khi tính m i s đ u ph i tính F2. Vì tính F5 c n đ n c F3 vàỗ ố ề ả ầ ế ả
F4, m t cách tính F5 m t cách ngây th có th s ph i tính F2 hai l n ho c nhi u h n.ộ ộ ơ ể ẽ ả ầ ặ ề ơ
Đi u này áp d ng m i khi có m t các bài toán con g i nhau: m t cách ti p c n ngâyề ụ ỗ ặ ố ộ ế ậ
th có th t n th i gian tính toán l i l i gi i t i u cho các bài toán con mà nó đã gi i. ơ ể ố ờ ạ ờ ả ố ư ả
Đ tránh vi c đó, ta l u tr l i gi i c a các bài toán con đã gi i. Do v y, n u sau nàyể ệ ư ữ ờ ả ủ ả ậ ế
ta c n gi i l i chính bài toán đó, ta có th l y và s d ng k t qu đã đ c tính toán.ầ ả ạ ể ấ ử ụ ế ả ượ
H ng ti p c n này đ c g i là l u tr (trong ti ng Anh đ c g i là memoization,ướ ế ậ ượ ọ ư ữ ế ượ ọ
không ph i memorization, dù t này cũng h p nghĩa). N u ta ch c ch n r ng m t l iả ừ ợ ế ắ ắ ằ ộ ờ
gi i nào đó không còn c n thi t n a, ta có th xóa nó đi đ ti t ki m không gian bả ầ ế ữ ể ể ế ệ ộ
nh . Trong m t s tr ng h p, ta còn có th tính l i gi i cho các bài toán con mà taớ ộ ố ườ ợ ể ờ ả
bi t tr c r ng s c n đ n. ế ướ ằ ẽ ầ ế
Tóm l i, quy ho ch đ ng s d ng: ạ ạ ộ ử ụ
Các bài toán con g i nhau ố
C u trúc con t i u ấ ố ư
Memoization
Quy ho ch đ ng th ng dùng m t trong hai cách ti p c n: ạ ộ ườ ộ ế ậ
top-down (T trên xu ng): Bài toán đ c chia thành các bài toán con, các bài toán conừ ố ượ
này đ c gi i và l i gi i đ c ghi nh đ phòng tr ng h p c n dùng l i chúng. Đâyượ ả ờ ả ượ ớ ể ườ ợ ầ ạ
là đ quy và l u tr đ c k t h p v i nhau. ệ ư ữ ượ ế ợ ớ
bottom-up (T d i lên): T t c các bài toán con có th c n đ n đ u đ c gi i tr c,ừ ướ ấ ả ể ầ ế ề ượ ả ướ
sau đó đ c dùng đ xây d ng l i gi i cho các bài toán l n h n. Cách ti p c n này h iượ ể ự ờ ả ớ ơ ế ậ ơ
t t h n v không gian b nh dùng cho ngăn x p và s l i g i hàm. Tuy nhiên, đôi khiố ơ ề ộ ớ ế ố ờ ọ
vi c xác đ nh t t c các bài toán con c n thi t cho vi c gi i quy t bài toán cho tr cệ ị ấ ả ầ ế ệ ả ế ướ
không đ c tr c giác l m. ượ ự ắ
M t s ngôn ng l p trình hàm, n i ti ng nh t là Haskell, có th t đ ng l u tr k tộ ố ữ ậ ổ ế ấ ể ự ộ ư ữ ế
qu c a m t l i g i hàm v i m t t p đ i s (argument) c th , đ tăng t c cách đánhả ủ ộ ờ ọ ớ ộ ậ ố ố ụ ể ể ố
giá call-by-name (c ch này đ c g i là call-by-need). Vi c này ch có th đ i v i cácơ ế ượ ọ ệ ỉ ể ố ớ
hàm không có hi u ng ph , tính ch t này luôn luôn đúng trong ngôn ng Haskellệ ứ ụ ấ ữ
nh ng ít khi đúng trong các ngôn ng l p trình m nh l nh, ch ng h n Pascal, C, C++,ư ữ ậ ệ ệ ẳ ạ
Java...
[s a] Ví d ử ụ
[s a] Dãy Fibonacci ử
M t cài đ t đ n gi n c a m t hàm tính ph n t th n c a dãy Fibonacci, tr c ti p d aộ ặ ơ ả ủ ộ ầ ử ứ ủ ự ế ự
theo đ nh nghĩa toán h c. Cài đ t này th c hi n r t nhi u tính toán th a.: ị ọ ặ ự ệ ấ ề ừ
function fib(n)
if n = 0 or n = 1
return n
else
return fib(n − 1) + fib(n − 2)
L u ý r ng n u ta g i, ch ng h n, fib(5), ta s t o ra m t cây các l i g i hàm, trongư ằ ế ọ ẳ ạ ẽ ạ ộ ờ ọ
đó các hàm c a cùng m t giá tr đ c g i nhi u l n: ủ ộ ị ượ ọ ề ầ
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
C th , fib(2) đ c tính hai l n. Trong các ví d l n h n, s có nhi u giá tr c a fib,ụ ể ượ ầ ụ ớ ơ ẽ ề ị ủ
hay các bài toán con đ c tính l i, d n đ n m t thu t toán có th i gian lũy th a. ượ ạ ẫ ế ộ ậ ờ ừ
Bây gi , gi s ta có m t đ i t ng ánh x đ n gi n, nó ánh x m i giá tr c a fib đãờ ả ử ộ ố ượ ạ ơ ả ạ ỗ ị ủ
đ c tính t i k t qu c a giá tr đó. Ta s a đ i hàm trên nh sau đ s d ng và c pượ ớ ế ả ủ ị ử ổ ư ể ử ụ ậ
nh t ánh x trên. Hàm thu đ c ch đòi h i th i gian ch y O(n) thay vì th i gian ch yậ ạ ượ ỉ ỏ ờ ạ ờ ạ
lũy th a: ừ
var m := map(0 → 1, 1 → 1)
function fib(n)
if n not in keys(m)
m[n] := fib(n − 1) + fib(n − 2)
return m[n]
Đây là cách ti p c n t trên xu ng, do tr c h t ta chia bài toán thành các bài toán nhế ậ ừ ố ướ ế ỏ
h n, r i gi i chúng và l u tr các k t qu . Trong tr ng h p này, ta cũng có th gi mơ ồ ả ư ữ ế ả ườ ợ ể ả
t ch hàm s d ng không gian tuy n tính (O(n)) xu ng ch còn s d ng không gianừ ỗ ử ụ ế ố ỉ ử ụ
h ng b ng cách s d ng cách ti p c n t d i lên. Cách này tính các giá tr nh h nằ ằ ử ụ ế ậ ừ ướ ị ỏ ơ
c a fib tr c, r i t đó xây d ng các giá tr l n h n: ủ ướ ồ ừ ự ị ớ ơ
function fib(n)
var previousFib := 1, currentFib := 1
repeat n − 1 times
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
Phiên b n bottom-up này g n v i vòng l p m nh l nh đ n gi n dùng cho vi c tínhả ầ ớ ặ ệ ệ ơ ả ệ
hàm Fibonacci có trong môn h c nh p môn khoa h c máy tính. ọ ậ ọ
Trong c hai ví d trên, ta ch tính fib(2) m t l n, r i s d ng nó đ tính c fib(4) vàả ụ ỉ ộ ầ ồ ử ụ ể ả
fib(3), thay vì tính nó m i l n c n tính fib(4) hay fib(3). ỗ ầ ầ
[s a] Bàn c ử ờ
Xét m t bàn c hình vuông n × n và m t hàm chi phí c(i, j) tr v chi phí liên quan đ nộ ờ ộ ả ề ế
ô i,j (i là ch s hàng, j là ch s c t). Ví d : bàn c 5 × 5 : ỉ ố ỉ ố ộ ụ ờ
+---+---+---+---+---+
5 | 6 | 7 | 4 | 7 | 8 |
+---|---|---|---|---+
4 | 7 | 6 | 1 | 1 | 4 |
+---|---|---|---|---+
3 | 3 | 5 | 7 | 8 | 2 |
+---|---|---|---|---+
2 | 2 | 6 | 7 | 0 | 2 |
+---|---|---|---|---+
1 | 7 | 3 | 5 | 6 | 1 |
+---+---+---+---+---+
1 2 3 4 5
Trong ví d , ta có ch ng h n c(1, 3) = 5 ụ ẳ ạ
Gi s ta có m t quân c có th xu t phát t i m t ô b t kỳ t i hàng đ u tiên (hàng 1),ả ử ộ ờ ể ấ ạ ộ ấ ạ ầ
và ta c n tìm đ ng đi ng n nh t (t ng chi phí c a các ô đi qua là nh nh t) đ t iầ ườ ắ ấ ổ ủ ỏ ấ ể ớ
đ c hàng cu i cùng (hàng n), v i đi u ki n quân c ch có th ti n th ng ho c ti nượ ố ớ ề ệ ờ ỉ ể ế ẳ ặ ế
theo đ ng chéo sang trái ho c sang ph i. Nghĩa là, m t quân c t i ô (1,3) có thườ ặ ả ộ ờ ạ ể
nh y sang đ c m t trong ba ô (2,2), (2,3) và (2,4). ả ượ ộ
+---+---+---+---+---+
5 | | | | | |
+---|---|---|---|---+
4 | | | | | |
+---|---|---|---|---+
3 | | | | | |
+---|---|---|---|---+
2 | | x | x | x | |
+---|---|---|---|---+
1 | | | O | | |
+---+---+---+---+---+
1 2 3 4 5
Bài toán này th hi n tính ch t c u trúc con t i u. Nghĩa là, l i gi i cho bài toán l nể ệ ấ ấ ố ư ờ ả ớ
ph thu c vào l i gi i cho các bài toán con. Ta đ nh nghĩa hàm q(i, j) nh sau: ụ ộ ờ ả ị ư
q(i, j) = chi phí t i thi u đ đ n đ c ô (i, j) ố ể ể ế ượ
N u ta có th tìm đ c giá tr c a hàm này t i t t c các ô n m trên hàng n, ta s ch nế ể ượ ị ủ ạ ấ ả ằ ẽ ọ
l y giá tr nh nh t và l n ng c con đ ng đó đ có đ c đ ng đi ng n nh t. ấ ị ỏ ấ ầ ượ ườ ể ượ ườ ắ ấ
D th y r ng q(i, j) b ng chi phí t i thi u đ đ n ô b t kỳ trong ba ô n m d i nó (doễ ấ ằ ằ ố ể ể ế ấ ằ ướ
ch có th đ n đ c (i,j) t các ô này) c ng thêm c(i, j). Ví d : ỉ ể ế ượ ừ ộ ụ
+---+---+---+---+---+
5 | | | | | |
+---|---|---|---|---+
4 | | | A | | |
+---|---|---|---|---+
3 | | B | C | D | |
+---|---|---|---|---+
2 | | | | | |
+---|---|---|---|---+
1 | | | | | |
+---+---+---+---+---+
1 2 3 4 5
Bây gi , ta đ nh nghĩa q(i, j) m t cách chính th c h n: ờ ị ộ ứ ơ
Ph ng trình trên r t d hi u. Dòng đ u tiên là các tr ng h p đ c bi t, dòng này cóươ ấ ễ ể ầ ườ ợ ặ ệ
m c đích d n d p cho tính ch t đ quy. Dòng th hai mô t nh ng gì x y ra t i hàngụ ọ ẹ ấ ệ ứ ả ữ ả ạ
đ u tiên, đ ta có xu t phát đi m. Dòng th ba, ph n đ quy, là ph n quan tr ng nh t.ầ ể ấ ể ứ ầ ệ ầ ọ ấ
V c b n, nó gi ng v i ví d A,B,C,D. ề ơ ả ố ớ ụ
T đ nh nghĩa này, ta có th d dàng t o m t đo n mã đ quy đ tính q(i, j). Trongừ ị ể ễ ạ ộ ạ ệ ể
đo n mã gi sau, n là kích th c c a bàn c , c(i, j) là hàm chi phí, và min() tr v giáạ ả ướ ủ ờ ả ề
tr nh nh t c a các giá tr n m trong ngo c: ị ỏ ấ ủ ị ằ ặ
function minCost(i, j)
if j = 0 or j = n + 1
return infinity
else if i = 1
return c(i, j)
else
return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)
C n l u ý r ng hàm này ch tính chi phí c a đ ng đi ch không ph i đ ng đi đíchầ ư ằ ỉ ủ ườ ứ ả ườ
th c. Ta s nói đ n ph n đó sau. ự ẽ ế ầ
Cũng nh ví d v dãy Fibonacci, hàm trên ch y r t r t lâu do nó ph i t n hàng núiư ụ ề ạ ấ ấ ả ố
th i gian đ tính đi tính l i các đ ng đi ng n nh t. Tuy nhiên, ta có th tính nhanhờ ể ạ ườ ắ ấ ể
h n r t nhi u n u hàm trên th c hi n công vi c l u tr các giá tr đã đ c tính (trongơ ấ ề ế ự ệ ệ ư ữ ị ượ
m t m ng). Ho c, ta còn có th nhanh h n n a n u tính toán theo ki u t d i lên vàộ ả ặ ể ơ ữ ế ể ừ ướ
m t m ng hai chi u q[i, j]. T i sao? Đ n gi n là vì khi đó ta tính toán m i đ ng điộ ả ề ạ ơ ả ỗ ườ
ch m t l n, và ta có th ch n cái gì c n tính toán tr c. ỉ ộ ầ ể ọ ầ ướ
Ta còn c n bi t đ ng đi th c s nh th nào. V n đ đó có th đ c gi i quy tầ ế ườ ự ự ư ế ấ ề ể ượ ả ế
b ng cách s d ng m t m ng n a: "m ng nút đ ng tr c" p[i, j]. M ng này l u cácằ ử ụ ộ ả ữ ả ứ ướ ả ư
d u v t v chuy n các đ ng đi t h ng nào t i. Xét đo n mã sau: ấ ế ề ệ ườ ừ ướ ớ ạ
function computeShortestPathArrays()
for x from 1 to n
q[1, x] := c(1, x)
for y from 1 to n
q[y, 0] := infinity
q[y, n + 1] := infinity
for y from 2 to n
for x from 1 to n