Thuật toán quy hoạch động

Thu t toán quy ho ch đ ng

ộ

ậ

ạ

Wednesday, 4. June 2008, 10:45:22

Thu t toán ậ

ậ ấ ứ ậ ạ ệ ị ầ ể i gi ờ ớ ng h p nh v y, m c dù chúng ta v n có th chia nh bài toán thành nhi u bài đó tìm ra l ừ ẫ ề ặ ợ ể ị Trong bài Thu t toán chia đ tr chúng ta đã th y s c m nh c a k thu t Chia đ Tr ủ ỹ b ng cách chia nh bài toán c n làm. Tuy nhiên không ph i bao gi cũng có th chia ả ằ ờ ỏ i c a bài toán l n. Trong các nh bài toán thành các bài toán con và t ả ủ ỏ tr ỏ ườ toán con, nh ng th i gian thu đ c s tăng theo s mũ và thu t toán tr nên vô giá tr . ị ư ậ ờ ượ ẽ ể ố ư ậ ở

Thu t toán Qui Ho ch Đ ng (Dynamic Programming) ộ ậ ạ

, vi c chia thành các bài toán con th ế ề ầ i quy t các bài toán con, các b n s ỏ ng ch chi m th i gian là đa th c. ứ ườ ờ ỉ c l p l i nhi u l n trong quá trình tìm ẽ ượ ặ ạ ạ ẽ ế ả ỗ ỏ i này đ tra c u v sau m i khi c n đ n. Công vi c này s đòi h i ầ ộ ấ ể ệ ế ẽ ỗ Trên th c t ệ ự ế ng h p này m t bài toán con s đ Trong tr ợ ườ i gi ki m l i. Đ kh i m t th i gian m i khi gi ờ ể ả ờ ế i gi l u tr các l ứ ề ả ờ ữ ư đ ph c t p thu t toán là đa th c. ứ ậ ộ ứ ạ

ơ ơ i c a các bài toán con l ộ ả ủ ạ ầ i ờ ề i gi ữ ấ ả ạ t cho l ượ ầ ệ t c các l t i nhi u l n v ề ầ ả ủ i c a i gi ờ Qui ho chạ lý thuy t đi u khi n. qui ho ch đ ng đ Có m t cách làm còn đ n gi n h n cách đã nêu trên. Chúng ta s l u gi ẽ ư ả c dùng l i không c n bi gi ế ằ sau hay không, không quan tâm đ n vi c các l ế ờ ế bài toán chính c a chúng ta hay không. Cách làm nh v y có tên g i là ủ đ ngộ . B n thân t ả t r ng chúng có đ i này có c n thi ả ọ ư ậ ể ế c l y t ượ ấ ừ ừ ề ạ ộ

ự ế ủ ạ ộ ư t đi n các thông s vào ề c a thu t toán qui ho ch đ ng không th ng nh t nh ng đi u ố chúng là có m t cái b ng và chúng ta c n l n l ả ấ ề Cách cài đ t th c t ậ ặ ố chung nh t ầ ầ ượ ộ ấ ở cái b ng này. Đ minh h a chúng ta hãy xét m t vài ví d . ụ ả ể ọ ộ

Ví d 3: Trò ch i Tán th ụ ơ ủ(5)

ầ ự ườ ệ ị ớ i th ng cu c. Trên th c t ấ ộ s có hai tán th A, B c n đ u tr c di n v i nhau, qui đ nh chung là ng ủ c n ván s là ng ườ ng giá tr n = 4. Gi ị ả ử ắ ẽ ạ th ự ế ườ ắ ấ ả ỗ ắ ữ ầ ắ ầ ẽ ắ ấ ắ ữ ắ ầ ộ ớ ị i th ng ắ Gi ả ử tr s hai tán ướ th A, B là m nh ngang nhau và do đó sác xu t th ng, thua trong m i ván là 50/50. Gi ủ s P(i,j) là sác xu t sao cho A c n th ng thêm i ván n a , B c n th ng thêm j ván n a ữ ử thì A s ch c ch n th ng chung cu c. Chúng ta c n tính nh ng giá tr P(i,j) này v i i, j b t kỳ. ấ

ồ ắ ế ế ứ ấ ể ậ ớ ứ ồ ộ ự ế ế ế ắ ế ế ắ ở N u i=0, j>0, t c là A đã th ng r i và do đó P(0,j)=1. N u i>0, j=0, t c là B đã th ng ắ và A đã thua r i, do đó P(i,0)=0. V i i, j > 0 ta có nh n xét sau: sác xu t đ A th ng ắ chung cu c d a vào ván ti p theo A th ng hay thua. N u ván ti p theo A th ng, khi đó ắ ván ti p theo thì sác xu t đ A sác xu t đ A th ng s là P(i-1,j), còn n u A thua ấ ể v n th ng chung cu c s là P(i,j-1). Vì ván ti p theo kh năng A th ng thua là 50/50 ắ ẫ ẽ ộ ẽ ấ ể ắ ế ả

ứ ạ i ta có công th c truy h i sau đ ứ ồ ể nên ta có công th c P(i,j) = (P(i-1,j)+P(i,j-1))/2. Tóm l tính P(i,j).

ừ ễ ớ ượ ồ ủ ộ ứ ạ c công th c truy h i c a đ ph c t p ứ T công th c (4) v i i+j=n ta d dàng tính đ ứ tính toán T(n) nh sau: ư

T(1) = C(C-const)

T(n) = 2T(n-1) + D (D-const)

ư ậ ệ ố ẽ

ộ ế ể ể ủ ỉ ứ ệ ử ụ ệ i c a công vi c tính toán này. (Gi ự ự ủ i h n d i h n d

n). Nh v y vi c tính toán các h s P(i,j) s có đ ph c ộ ứ ả ỹ ậ ệ ế i h n trên c a tính toán, đ hi u rõ h n ơ ớ ạ i t ″ th c s c a vi c s d ng đ qui tính toán theo công th c(4) chúng ta s th ẽ ử ứ ớ ạ ướ ủ ộ ứ ạ i c a đ ph c t p

ệ (5) Ta tính đ c T(n) = O(2 ệ ượ t p tăng theo s mũ c a n n u tính toán b ng k thu t đ qui và đây là m t k t qu ằ ủ ạ ố r t l n. Tuy nhiên công th c trên ch cho ta gi ấ ớ s ″t ự ồ ệ tính toán gi đ ượ ớ ạ ướ ủ c ký hi u là big-omega: W). ệ

c giá tr này chúng ta s tính s l n g i hàm P khi th c hi n đ qui cách ể ượ ự ẽ ệ ọ ị ệ ỹ ẽ ợ ố ầ ớ ứ ứ c a h s t ế h p là ng t Đ tính đ tính P(i,j) theo công th c (4). Công th c (4) v i i+j=n n u xem xét k s g i ý cho chúng ta v m t đ ng th c t ề ộ ẳ ự ủ ệ ố ổ ợ ứ ươ

h p ch p i t n ph n t t ầ ử ừ ậ ầ ử ố ừ ậ (t T nh n xét trên d dàng suy ra r ng s l n g i hàm P trong l , s cách ch n ra i ph n t ọ ố ầ ổ ợ ừ ậ ầ ử t p h p ban đ u n ph n t ). ầ ợ i g i P(i,j) s ít nh t là ấ ẽ ờ ọ ễ ằ ọ

V i i=j=n/2 d th y giá tr này s b ng

. V y ta v a ch ng minh đ

ễ ấ ẽ ằ ớ ị ừ ứ ậ ượ ằ c r ng

ị ấ ớ . là m t giá tr r t l n (tuy có nh h n c n d ỏ ơ ộ ậ ướ ộ ứ ạ 2n) và h u nh không th áp d ng tính toán trên th c t ự ế i đ ph c t p tính toán P(i,j) là ể ầ ư ụ

t nh t là v a tính v a đi n s vào b ng nh mô t trong hình 3 d ố ề ố ừ ừ ư ấ ả ả ướ i Cách tính P(i,j) t đây.

ượ ầ ự ư c tiên đ ý r ng hàng d ằ ướ ể ề ấ nh sau: Tr ả ẽ ướ ầ ượ i cùng ả ướ i ượ c ả ướ góc ph i d ng chéo ng nh sau: B ng h s P(i,j) đ c đi n tu n t ệ ố ả c a b ng là toàn 0 và hàng đ u tiên bên ph i s là toàn 1. Xu t phát t ủ ả ầ t đi n s vào b ng theo h chúng ta l n l ng Tây-B c d c theo đ ắ ọ v i i+j không thay đ i. Thu t toán đi n s P(i,j) vào b ng đ c mô t ả ề ố ớ ề ố ổ ừ ườ ả ư ượ ậ

(7)

Function O s(i,j: integer):real; đ

var s,k:integer;

Begin

for s:=1 to i+j do

begin P[0,s]:=1;

P[s,0]:=0;

for k:=1 to s-1 do

P[k,s-k]:=(P[k-1,s-k]+P[k,s-k-1])/2;

end;

O s:=(P[i,j]); đ

End; {O s}đ

ậ ờ Ta hãy th phân tích thu t toán trên. Vòng l p bên trong là O(s) th i gian, hai l nh gán ặ 0 và 1 ch là O(1) th i gian, nh v y t ng s th i gian tính t ố ờ ệ ẽ vòng l p ngoài s là ư ậ ổ ử ỉ ừ ặ ờ

ắ ạ ươ ng c a thu t toán qui ho ch đ ng. b ng s so sánh v i vi c g i đ qui, và đó là t ả v i n=i+j. Ch c các b n đã th y s kỳ di u c a ph ớ ớ ề ng pháp đi n ộ ạ ệ ủ ậ ủ ấ ự t ư ưở ệ ọ ệ ố

Ví d 4: Bài toán Phân ho ch Tam giác ụ ạ

ộ ẽ ạ ộ ọ ỹ ẳ ộ ỉ ớ ể ữ ầ ỉ ố Ta s xét thêm m t ví d n a minh h a cho k thu t qui ho ch đ ng, đó là bài toán tam giác hóa đa giác. Gi ướ c. Yêu c u n i các ″cung″ n i gi a hai đ nh b t kỳ c a đa giác đ chia đa giác thành các ố ấ ấ tam giác nh h n (phân ho ch tam giác) sao cho t ng các dây cung n i là nh nh t. ỏ ỏ ơ ể . i thi u M t cách ch n dây cung nh v y đ ố ọ ậ ụ ữ s có m t đa giác trên m t ph ng v i các đ nh cho tr ặ ả ử ủ ố ổ ạ ộ Phân ho ch tam giác t c g i là m t ạ ư ậ ượ ọ ộ

ừ ữ ệ ớ ẽ Hình 4 mô t ta tính đ m t đa giác 7 c nh v i m t phân ho ch tam giác. T d li u trên hình v ạ ả ộ ạ c t ng chi u dài c a phân ho ch này là ủ ộ ạ ề ượ ổ

tuy nhiên phân ho ch này không ạ là t i u. ố ư

ỹ ờ ẽ ạ ạ ể ệ ể ả ệ ộ ẽ ủ ệ ỉ ủ ề ồ c tiên chúng ta có m t s nh n xét sau c g i là chúng ta s dùng k thu t qui ho ch đ ng đ gi ậ ỏ ồ ổ ạ ề Giá trị c a phân ho ch này. Tr ộ ộ ố ướ ủ ậ i bài toán phân ho ch tam Bây gi 0, giác này. Đ ti n cho vi c theo d i, chúng ta s ký hi u các đ nh c a đa giác là V V1,.., Vn-1 theo chi u kim đ ng h . T ng chi u dài các dây cung c a m t phân ho ch ạ s đ ẽ ượ ọ đây:

ủ ề ấ ỉ ờ B đ 1. cũng có t ọ i thi u m t đ nh đ ổ ề Trong m i phân ho ch tam giác, hai đ nh k nhau b t kỳ c a đa giác bao gi c n i v i m t dây cung. ộ ạ ượ ố ớ ộ ỉ ể ố

s V ượ ố ớ ấ ứ ủ ẽ ả ạ

i-1Vi và Vi+1Vi+2 và do đó vùng phân ho ch này không là tam giác.

ả ử i,Vi-1 là hai đ nh k mà không đ Gi ỉ ề ho ch tam giác. Khi đó vùng phân ho ch ch a c nh V ạ n a là V ữ c n i v i b t c dây dung nào c a phân ạ iVi+1 s ph i ch a thêm hai c nh ứ ạ ứ ạ

s (V ủ ạ ộ ả ồ ạ i ả ử k sao cho (Vi,Vk) và (Vk,Vj) s là c nh c a đa giác ho c dây cung c a phân

i,Vj) là m t dây cung c a phân ho ch tam giác, khi đó ph i t n t ủ

ủ ẽ ạ ặ B đ 2. ổ ề Gi m t đ nh V ộ ỉ ho ch.ạ

ứ i,Vj) ph i là c nh c a m t tam giác c a phân ho ch. Đ nh th 3 ủ ủ ạ ả ạ ộ ỉ ậ ậ Th t v y, c nh (V chính là Vk c n tìm. ạ ầ

Đ b t đ u tìm ki m phân ho ch tam giác t i u, chúng ta ch n 2 đ nh k b t kỳ, ể ắ ầ ế ạ ố ư ề ấ ọ ỉ

i đ nh Vk sao cho V

0 và V1. Khi đó ph i t n t

ạ ẳ ả ồ ạ ỉ ặ 0Vk và V1Vk là c nh ho c ạ ạ ư ậ ư ọ ề ừ ớ ở ị ớ ả ớ ỗ ng ng v i 2 đa giác con xác đ nh b i dây cung v a tìm ươ ứ c phân chia đa giác ban đ u thành 2 ph n. V i ví d đa giác 7 c nh đã nêu trên gi ụ ầ 0V3, khi đó s đ a v 2 bài toán con ng v i hai đa giác 3 v i cung V ầ ẽ ư ề ạ ứ ớ ớ ỉ ch ng h n V dây cung c a phân ho ch. V i m i cách ch n k nh v y ta đ a bài toán tìm phân ủ ho ch v 2 bài toán con, t ạ đ ượ s ta ch n đ nh V ọ ử sau đây:

i quy t bài toán phân ho ch tam giác cho hai tr ầ ế ả ạ ế ụ ớ ợ ng h p cung 3,V4,V5) và ữ ươ ứ ế ớ ẽ Ti p theo chúng ta c n gi t ớ ươ ứ V3V5 thì s chia thành 2 bài toán con n a t (V0,V3,V5,V6). Cách ti p c n nh v y s có th i gian tăng s mũ v i n. ư ậ ẽ ườ ng ng v i hình 5 trên. Ví d v i Bài toán con 2, n u chúng ta b t đ u t ắ ầ ừ ng ng v i hai đa giác con là (V ố ế ậ ớ ờ

Chú thích c a ng t. ủ i vi ườ ế

ộ ắ ế ắ t t ng ph n t đ u c a các ậ ầ i v i nhau theo hình th c xét l n l ạ ớ ế ầ ử ầ ủ ầ ượ ừ (1) S p x p tr n. Thu t toán s p x p tách dãy ban đ u thành 2 dãy và sau đó ti n hành ế ″tr n″ hai dãy này l ứ ộ dãy này.

d a trên ý ị ế ứ ự ự ế ậ ộ ng luôn chia dãy đã cho thành 2 ph n b ng nhau và đ a vi c tìm trên dãy l n v bài ắ ệ ề ư ầ ằ ớ (2) Tìm ki m nh phân. Thu t toán tìm ki m trên m t dãy đã s p th t t ưở toán tìm ki m trên các dãy con này. ế

ng pháp tính nhân trong nhà tr ươ ỏ ệ ườ ổ ữ ộ ố ỗ ớ ậ ổ ư ậ ệ ấ ờ ng ph thông. Chia nh vi c nhân 2 s n-ch (3) Ph ố s XY thành n bài toán con, m i bài toán con nhân X v i m t s có m t ch s . V i ớ ố ữ ố ộ m i bài toán con nh v y vi c nhân m t O(n) th i gian, do v y t ng s đ ph c t p là ố ộ ứ ạ ỗ O(n2).

ớ ạ ế ạ ạ ớ ng. Tuy nhiên thu t toán mô t đây hoàn toàn ừ ắ trên gh nhà tr ế ắ ằ ườ t h n cách nhân thông th ng ố ơ ậ ổ ườ ớ

i sao không d y cách nhân m i này cho (4) T i đây s có b n th c m c r ng th thì t ẽ h c sinh ngay t ả ở ọ tr ng ph thông v i n<5000. Ma(.t kha'c no' không t ở ườ la.i qua' phu+'c ta.p va` kho^ng sa'ng su?a nhu+ thua^.t toa'n ho.c sinh ddang su+? du.ng hie^.n nay.

World Series Ođs, chúng tôi s a l ừ ử ạ ớ i cho thích h p h n v i ợ ơ (5) Nguyên tác là c m t ụ t Nam. c a Vi th c t ự ế ủ ệ

(6) Cách tính nh sau: ư

V i i=j=n/2 ta c n ph i ch ng minh: ứ ầ ả ớ

ứ ứ ẵ ớ ấ ẳ s nó đã đúng v i n, ta s ch ng minh nó cũng đúng v i n+2. Ta ch ng minh b t đ ng th c này qui n p theo n (n-ch n). V i n=2, b t đ ng th c là ạ ứ hi n nhiên. Gi ẽ ứ ấ ẳ ớ ả ử ể ớ

Th t v y khi đó ta có: ậ ậ

ặ ằ theo qui n p giá tr này s l n h n ho c b ng ẽ ớ ạ ơ ị