ươ ạ ọ ộ ng pháp gi m th i gian ả ờ ạ ủ ậ ộ ấ ủ ố i u (optimal substructure). quy hoach dong Trong ngành khoa h c máy tính, quy ho ch đ ng là m t ph 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 ấ ố ư
ươ ộ c thành l p nh là m t ch đ v k ngh và phân tích h ng pháp quy ho ch đ ng vào năm ạ ệ ệ ủ ề ề ỹ ậ ư ch c IEEE th a nh n. c t Nhà toán h c Richard Bellman đã phát minh ph ọ 1953. Ngành này đã đ ộ ượ th ng đã đ ượ ổ ứ ừ ậ ố
ạ ộ
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 ổ ử
ng l ấ ắ ườ ố ư ộ ườ ượ ữ ấ ử ụ ắ ng đi ng n nh t s d ng c u trúc con t ấ i t ộ ườ i gi ng đi ng n nh t gi a hai đ nh mà nó n iC u trúc con t ỉ i u cho các bài toán con có th đ ờ ả ố ư ụ ườ ố ư c s d ng đ tìm các l ể ộ ỉ ấ ớ ng đi ng n nh t t ắ ướ ế ườ ấ ng đi toàn c c t ồ ả i m t bài toán v i c u trúc con t i u; m t đ ố ấ ể ượ ử ụ ng đi ng n nh t t ắ c h t tính đ ể ọ ườ ớ ấ n sóng i u có i ờ ộ i m t đ nh trong m t ừ i đích t ấ ớ ư t nh t, nh ấ ộ i u b ng m t ụ ố ố ư ằ ế ể ả ộ Hình 1. Tìm đ đ i di n cho m t đ ệ ạ nghĩa là các l i u cho bài toán toàn c c. Ví d , đ i t gi ụ ả ố ư c tìm th y b ng cách: tr đ th có th đ ể ượ ằ ồ ị t t c các đ nh k nó, r i dùng k t qu này đ ch n đ ề ỉ ấ ả trong hình 1. Nói chung, ta có th gi c: quy trình ba b ướ
ỏ ơ 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
i t ử ụ ự ế ể ả ố ư ộ ờ i u đó đ xây d ng m t l ả ằ ầ ứ Chia bài toán thành các bài toán con nh h n. Gi ả này. S d ng các k t qu t Các bài toán con đ ượ ti p t c nh th , cho đ n khi ta đ n đ i gi i b ng cách chia chúng thành các bài toán nh h n, và c i. ng h p đ n gi n d tìm l i gi c tr ả ố ư c gi ế ế ụ ư ế i u cho bài toán ban đ u. ỏ ơ ờ ế ượ ườ ễ ả ả ợ ơ
ồ ị ộ ấ ả ng phi chu trình mô t ướ ệ ữ ố ỗ ể ả ụ ề ớ ầ ơ ỗ ố ề ơ ế ả ề ả ể ẽ ầ ộ ộ 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à quan h gi a các bài toán con g i nhau.Nói là m t đ th có h ả ộ ồ ị 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 ộ ằ i nhi u bài toán l n h n khác nhau. Ví d , trong dãy Fibonacci, F3 = F1 s d ng đ gi ử ụ + 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 ặ ế ậ ả ố ụ ề ặ ỗ ộ
i gi i u cho các bài toán con mà nó đã gi i t i. th có th t n th i gian tính toán l ờ ể ố ơ i l ạ ờ ả ố ư ả
i gi ể ư ữ ờ ả ủ ế ả
i. Do v y, n u sau này i c a các bài toán con đã gi ế ả ượ ọ ử ụ ế ữ ư ợ ậ c tính toán. i chính bài toán đó, ta có th l y và s d ng k t qu đã đ ượ ể ấ c g i là memoization, c g i là l u tr (trong ti ng Anh đ này cũng h p nghĩa). N u ta ch c ch n r ng m t l ừ ắ ằ ắ ế t n a, ta có th xóa nó đi đ ti t ki m không gian b ể ế ữ ệ ộ ờ i ộ ể ế i cho các bài toán con mà ta i gi ể ả ờ Đ tránh vi c đó, ta l u tr l ệ i l ta c n gi ả ạ ầ H ng ti p c n này đ ượ ọ ế ậ ướ không ph i memorization, dù t ả i nào đó không còn c n thi gi ả nh . Trong m t s tr ợ ộ ố ườ ớ c r ng s c n đ n. t tr bi ẽ ầ ế ướ ằ ầ ng h p, ta còn có th tính l ế
Tóm l ạ i, quy ho ch đ ng s d ng: ộ ử ụ ạ
ấ ố i u ố ư
ng dùng m t trong hai cách ti p c n: Các bài toán con g i nhau C u trúc con t Memoization Quy ho ch đ ng th ộ ạ ườ ế ậ ộ
ố i gi i chúng. Đây ạ ườ ượ ừ ả ượ c ghi nh đ phòng tr ớ ể c chia thành các bài toán con, các bài toán con ng h p c n dùng l ợ ầ ớ i tr i và l ư ừ ướ ề ượ i gi ả c gi ế ậ ộ ế c, ả ướ ế ể ầ i cho các bài toán l n h n. Cách ti p c n này h i ơ ơ ớ i g i hàm. Tuy nhiên, đôi khi ố ờ ọ ướ c i quy t bài toán cho tr ả ế ệ ế ầ ắ ể ự ộ ổ ế ấ ố ố ớ ơ ế ỉ ố ể ố ớ ệ ứ ụ ữ ệ ệ ẳ ạ top-down (T trên xu ng): Bài toán đ i đ c gi này đ ả ượ ờ là đ quy và l u tr đ c k t h p v i nhau. ữ ượ ế ợ ệ i lên): T t c các bài toán con có th c n đ n đ u đ bottom-up (T d ấ ả sau đó đ c dùng đ xây d ng l ượ ờ ự ể t t h n v không gian b nh dùng cho ngăn x p và s l ề ớ ố ơ vi c xác đ nh t t cho vi c gi t c các bài toán con c n thi ị ấ ả ệ c tr c giác l m. không đ ượ ự ữ ế đ ng l u tr k t M t s ngôn ng l p trình hàm, n i ti ng nh t là Haskell, có th t ư ữ ậ ộ ố i g i hàm v i m t t p đ i s (argument) c th , đ tăng t c cách đánh qu c a m t l ụ ể ể ộ ậ ộ ờ ọ ả ủ 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...
ử ử ộ ặ ơ ộ ự ế ự th n c a dãy Fibonacci, tr c ti p d a [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 ả ủ 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.: ọ ầ ử ứ ệ ấ ủ ề ự ừ ặ ị
i g i hàm, trong ư ằ ọ ộ ờ ọ c g i nhi u l n: 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 ạ ế ẳ đó các hàm c a cùng m t giá tr đ ị ượ ọ ủ ẽ ạ ề ầ ộ
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) đ hay các bài toán con đ i, d n đ n m t thu t toán có th i gian lũy th a. ầ c tính l c tính hai l n. Trong các ví d l n h n, s có nhi u giá tr c a fib, ậ ị ủ ừ ượ ế ạ ẫ ộ ờ
ộ ố ượ ạ ỗ ị ủ ả
s ta có m t đ i t ng ánh x đ n gi n, nó ánh x m i giá tr c a fib đã ậ i k t qu c a giá tr đó. Ta s a đ i hàm trên nh sau đ s d ng và c p ị ư ả ủ ạ c ch đòi h i th i gian ch y O(n) thay vì th i gian ch y ạ ơ ử ổ ờ ỏ ể ử ụ ờ ượ ạ ỉ Bây gi , gi ả ử ờ c tính t đ ượ ớ ế nh t ánh x trên. Hàm thu đ ạ ậ lũy th a: ừ
c h t ta chia bài toán thành các bài toán nh ế ậ ừ ỏ ể ả ng h p này, ta cũng có th gi m ướ ế ả ữ trên xu ng, do tr ố i chúng và l u tr các k t qu . Trong tr ư ử ụ ườ ố ử ụ ế ế ợ ỉ ị đó xây d ng các giá tr l n h n: c, r i t 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 h n, r i gi ả ồ ơ 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 t ừ ỗ d h ng b ng cách s d ng cách ti p c n t ỏ ơ i lên. Cách này tính các giá tr nh h n ế ậ ừ ướ ử ụ ằ ằ c a fib tr ị ớ ủ ồ ừ ướ ự ơ
ệ ệ ầ ơ 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 ẳ ụ ạ
i m t ô b t kỳ t s ta có m t quân c có th xu t phát t ờ ạ ấ ạ ộ ng đi ng n nh t (t ng chi phí c a các ô đi qua là nh nh t) đ t ủ i hàng đ u tiên (hàng 1), ấ ầ ỏ ắ 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 ặ ể ấ ấ ổ ớ ệ ẳ ề 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 ể ế ờ ạ ờ ỉ ộ ể ặ ả ườ c m t trong ba ô (2,2), (2,3) và (2,4). Gi ộ ả ử và ta c n tìm đ ườ ầ đ ố ượ theo đ nh y sang đ ả ượ ộ
i u. Nghĩa là, l i gi ấ ấ ả ờ ớ i cho bài toán l n ố ư i cho các bài toán con. Ta đ nh nghĩa hàm q(i, j) nh sau: ị ư +---+---+---+---+---+ 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 ph thu c vào l ộ ể ệ i gi ờ ụ ả
ố i t c con đ ạ ấ ả ng đó đ có đ q(i, j) = chi phí t N u ta có th tìm đ ể ế l y giá tr nh nh t và l n ng ấ ỏ ị ấ i thi u đ đ n đ ể ế ượ ị ủ ượ c ô (i, j) ể c giá tr c a hàm này t ượ ầ ườ t c các ô n m trên hàng n, ta s ch n ẽ ọ ể ằ c đ ượ ườ ng đi ng n nh t. ắ ấ
i thi u đ đ n ô b t kỳ trong ba ô n m d i nó (do ấ ằ ố ướ D th y r ng q(i, j) b ng chi phí t 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: ộ ứ ơ ị
ng h p đ c bi ấ ễ ể ườ ệ ặ ầ ứ ẹ ọ ể ệ ầ ầ t, dòng này có Ph ng trình trên r t d hi u. Dòng đ u tiên là các tr ươ ợ i hàng 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 ạ ả ụ ả ữ đ 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. ề ơ ả ấ ệ ể ụ ố ớ
ể ễ ể ệ ạ ạ c c a bàn c , c(i, j) là hàm chi phí, và min() tr v giá ừ ị ạ ướ ủ ả ề 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 ờ tr nh nh t c a các giá tr n m trong ngo c: ỏ sau, n là kích th ị ằ ả ấ ủ ặ ị
ng đi đích ủ ườ ứ ằ ỉ ả ườ 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) ng đi ch không ph i đ C n l u ý r ng hàm này ch tính chi phí c a đ th c. Ta s nói đ n ph n đó sau. ầ ế ầ ư ự ẽ
ư ụ ề ạ ắ ả ố ể ượ ữ ị i các đ ự ể ế ặ ạ ấ ấ ấ ệ ư ơ ữ ế ả ề ạ c. 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 ng đi ng n nh t. Tuy nhiên, ta có th tính nhanh th i gian đ tính đi tính l ườ ể ờ c tính (trong 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 đã đ ơ ấ ệ ề i lên và 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 ể ừ ướ ộ ả ng đi 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 đ ỗ ườ ơ ả ộ ch m t l n, và ta có th ch n cái gì c n tính toán tr ầ ể ọ ỉ ộ ầ ướ
ầ ự ự ư ế ả ng đi th c s nh th nào. V n đ đó có th đ ộ t đ ế ườ ử ụ i quy t ế ư ữ ng đi t ng nào t Ta còn c n bi ề b ng cách s d ng m t m ng n a: "m ng nút đ ng tr ướ ả ằ d u v t v chuy n các đ ườ ấ c gi ể ượ c" p[i, j]. M ng này l u các ả i. Xét đo n mã sau: ạ ả h ừ ướ ấ ứ ớ ế ề ệ
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
m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x] := m + c(y, x)
, v n đ đ n gi n còn l ả ạ i là xác đ nh c c ti u và in nó ra. ự ể ị if m = q[y-1, x-1] p[y, x] := -1 else if m = q[y-1, x] p[y, x] := 0 else p[y, x] := 1 Bây gi ờ ấ ề ơ
function computeShortestPath() computeShortestPathArrays()
minIndex := 1 min := q[n, 1]
for i from 2 to n if q[n, i] < min minIndex := i min := q[n, i]
printPath(n, minIndex)
function printPath(y, x) print(x) print("<-")
if y = 2 print(x + p[y, x]) else printPath(y-1, x + p[y, x])
