Thu t toán quy ho ch đ ngậ ạ ộ
Wednesday, 4. June 2008, 10:45:22
Thu t toánậ
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ằ ỏ ầ ả ờ ể
nh bài toán thành các bài toán con và t đó tìm ra l i gi i c a bài toán l n. Trong cácỏ ừ ờ ả ủ ớ
tr 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ườ ợ ư ậ ặ ẫ ể ỏ ề
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)ậ ạ ộ
Trên th c t , vi c chia thành các bài toán con th ng ch chi m th i gian là đa th c.ự ế ệ ườ ỉ ế ờ ứ
Trong tr ng h p này m t bài toán con s đ c l p l i nhi u l n trong quá trình tìmườ ợ ộ ẽ ượ ặ ạ ề ầ
ki m l i gi i. Đ kh i m t th i gian m i khi gi i quy t các bài toán con, các b n sế ờ ả ể ỏ ấ ờ ỗ ả ế ạ ẽ
l u tr các l i gi i này đ tra c u v sau m i khi c n đ n. Công vi c này s đòi h iư ữ ờ ả ể ứ ề ỗ ầ ế ệ ẽ ỏ
đ ph c t p thu t toán là đa th c.ộ ứ ạ ậ ứ
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 t t c các l iộ ơ ả ơ ẽ ư ữ ấ ả ờ
gi i c a các bài toán con l i không c n bi t r ng chúng có đ c dùng l i nhi u l n vả ủ ạ ầ ế ằ ượ ạ ề ầ ề
sau hay không, không quan tâm đ n vi c các l i gi i này có c n thi t cho l i gi i c aế ệ ờ ả ầ ế ờ ả ủ
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à ủ ư ậ ọ Qui ho chạ
đ ngộ. B n thân t qui ho ch đ ng đ c l y t lý thuy t đi u khi n.ả ừ ạ ộ ượ ấ ừ ế ề ể
Cách cài đ t th c t c a thu t toán qui ho ch đ ng không th ng nh t nh ng đi uặ ự ế ủ ậ ạ ộ ố ấ ư ề
chung nh t chúng là có m t cái b ng và chúng ta c n l n l t đi n các thông s vàoấ ở ộ ả ầ ầ ượ ề ố
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)
Gi s có hai tán th A, B c n đ u tr c di n v i nhau, qui đ nh chung là ng i th ngả ử ủ ầ ấ ự ệ ớ ị ườ ắ
tr c n ván s là ng i th ng cu c. Trên th c t th ng giá tr n = 4. Gi 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 đóộ ự ế ắ ế ế ắ
sác xu t đ A th ng s là P(i-1,j), còn n u A thua ván ti p theo thì sác xu t đ Aấ ể ắ ẽ ế ở ế ấ ể
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ẫ ắ ộ ẽ ế ả ắ
nên ta có công th c P(i,j) = (P(i-1,j)+P(i,j-1))/2. Tóm l i ta có công th c truy h i sau đứ ạ ứ ồ ể
tính P(i,j).
T công th c (4) v i i+j=n ta d dàng tính đ c công th c truy h i c a đ ph c t pừ ứ ớ ễ ượ ứ ồ ủ ộ ứ ạ
tính toán T(n) nh sau:ư
T(1) = C(C-const)
T(n) = 2T(n-1) + D (D-const)
(5) Ta tính đ c T(n) = O(2ượ n). Nh v y vi c tính toán các h s P(i,j) s có đ ph cư ậ ệ ệ ố ẽ ộ ứ
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 i h n trên c a tính toán, đ hi u rõ h nấ ớ ứ ỉ ớ ạ ủ ể ể ơ
s ″t 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ự ồ ệ ự ự ủ ệ ử ụ ệ ứ ẽ ử
tính toán gi i h n d i c a công vi c tính toán này. (Gi i h n d i c a đ ph c t pớ ạ ướ ủ ệ ớ ạ ướ ủ ộ ứ ạ
đ c ký hi u là big-omega: W).ượ ệ
Đ tính đ 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ể ượ ị ẽ ố ầ ọ ự ệ ệ
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 ng t c a h s t h p làề ộ ẳ ứ ươ ự ủ ệ ố ổ ợ
(t h p ch p i t n ph n t , s cách ch n ra i ph n t t t p h p ban đ u n ph n 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 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ậ ừ ứ ượ ằ
c n d i đ ph c t p tính toán P(i,j) làậ ướ ộ ứ ạ là m t giá tr r t l n (tuy có nh h nộ ị ấ ớ ỏ ơ
2n) và h u nh không th áp d ng tính toán trên th c t .ầ ư ể ụ ự ế
Cách tính P(i,j) t 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ố ấ ừ ừ ề ố ả ư ả ướ
đây.
B ng h s P(i,j) đ c đi n tu n t nh sau: Tr c tiên đ ý r ng hàng d i cùngả ệ ố ượ ề ầ ự ư ướ ể ằ ướ
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 góc ph i d iủ ả ầ ả ẽ ấ ừ ả ướ
chúng ta l n l t đi n s vào b ng theo h ng Tây-B c d c theo đ ng chéo ng cầ ượ ề ố ả ướ ắ ọ ườ ượ
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 nh sau:ớ ổ ậ ề ố ả ượ ả ư
Function O s(i,j: integer):real; đ(7)
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àỉ ờ ư ậ ổ ố ờ ừ ặ ẽ
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ớ ắ ạ ấ ự ệ ủ ươ ề
b ng s so sánh v i vi c g i đ qui, và đó là t t ng c a thu t toán qui ho ch đ ng.ả ố ớ ệ ọ ệ ư ưở ủ ậ ạ ộ
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 s có m t đa giác trên m t ph ng v i các đ nh cho tr 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.ỏ ơ ạ ổ ố ỏ ấ
M t cách ch n dây cung nh v y đ c g i là m t ộ ọ ư ậ ượ ọ ộ Phân ho ch tam giác t i thi uạ ố ể .
Hình 4 mô t 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ả ộ ạ ớ ộ ạ ừ ữ ệ ẽ
ta tính đ 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.ố ư
Bây gi chúng ta s dùng k thu t qui ho ch đ ng đ gi i bài toán phân ho ch tamờ ẽ ỹ ậ ạ ộ ể ả ạ
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ể ệ ệ ỏ ẽ ệ ỉ ủ 0,
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 đ c g i là ẽ ượ ọ Giá trị c a phân ho ch này. Tr c tiên chúng ta có m t s nh n xét sauủ ạ ướ ộ ố ậ
đây:
B đ 1.ổ ề 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ũng có t i thi u m t đ nh đ c n i v i m t dây cung.ố ể ộ ỉ ượ ố ớ ộ
Gi s Vả ử i,Vi-1 là hai đ nh k mà không đ c n i v i b t c dây dung nào c a phânỉ ề ượ ố ớ ấ ứ ủ
ho ch tam giác. Khi đó vùng phân ho ch ch a c nh Vạ ạ ứ ạ iVi+1 s ph i ch a thêm hai c nhẽ ả ứ ạ
n a là Vữi-1Vi và Vi+1Vi+2 và do đó vùng phân ho ch này không là tam giác.ạ
B đ 2.ổ ề Gi s (Vả ử i,Vj) là m t dây cung c a phân ho ch tam giác, khi đó ph i t n t iộ ủ ạ ả ồ ạ
m t đ nh Vộ ỉ 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ẽ ạ ủ ặ ủ
ho ch.ạ
Th t v y, c nh (Vậ ậ ạ i,Vj) ph i là c nh c a m t tam giác c a phân ho ch. Đ nh th 3ả ạ ủ ộ ủ ạ ỉ ứ
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ỳ,ể ắ ầ ế ạ ố ư ọ ỉ ề ấ
ch ng h n Vẳ ạ 0 và V1. Khi đó ph i t n t i đ nh Vk sao cho Vả ồ ạ ỉ 0Vk và V1Vk là c nh ho cạ ặ
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 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ượ ầ ầ ớ ụ ạ ả
s ta ch n đ nh Vử ọ ỉ 3 v i cung Vớ0V3, khi đó s đ a v 2 bài toán con ng v i hai đa giácẽ ư ề ứ ớ
sau đây:
Ti p theo chúng ta c n gi i quy t bài toán phân ho ch tam giác cho hai tr ng h pế ầ ả ế ạ ườ ợ
t 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 cungươ ứ ớ ụ ớ ế ắ ầ ừ
V3V5 thì s chia thành 2 bài toán con n a t ng ng v i hai đa giác con là (Vẽ ữ ươ ứ ớ 3,V4,V5) và
(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. ế ậ ư ậ ẽ ờ ố ớ
Chú thích c a ng i vi t.ủ ườ ế
(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 i v i nhau theo hình th c xét l n l t t ng ph n t đ u c a cácộ ạ ớ ứ ầ ượ ừ ầ ử ầ ủ
dãy này.
(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 d a trên ýế ị ậ ế ộ ắ ứ ự ự
t 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ưở ầ ằ ư ệ ớ ề
toán tìm ki m trên các dãy con này.ế
(3) Ph ng pháp tính nhân trong nhà tr ng ph thông. Chia nh vi c nhân 2 s n-chươ ườ ổ ỏ ệ ố ữ
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).
(4) T i đây s có b n th c m c r ng th thì t i sao không d y cách nhân m i này choớ ẽ ạ ắ ắ ằ ế ạ ạ ớ
h c sinh ngay t trên gh nhà tr ng. Tuy nhiên thu t toán mô t đây hoàn toànọ ừ ế ườ ậ ả ở
không t t h n cách nhân thông th ng tr ng ph thông v i n<5000. Ma(.t kha'c no'ố ơ ườ ở ườ ổ ớ
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.