TTNT
CH NG 1 : THU T TOÁN – THU T GI IƯƠ Ậ Ậ Ả
I. KHÁI NI M THU T TOÁN – THU T GI IỆ Ậ Ậ Ả
II. THU T GI I HEURISTICẬ Ả
III. CÁC PH NG PHÁP TÌM KI M HEURISTICƯƠ Ế
III.1. C u trúc chung c a bài toán tìm ki mấ ủ ế
III.2. Tìm ki m chi u sâu và tìm ki m chi u r ngế ề ế ề ộ
III.3. Tìm ki m leo đ iế ồ
III.4. Tìm ki m u tiên t i u (best-first search)ế ư ố ư
III.5. Thu t gi i ATậ ả
III.6. Thu t gi i AKTậ ả
III.7. Thu t gi i A*ậ ả
III.8. Ví d minh h a ho t đ ng c a thu t gi i A*ụ ọ ạ ộ ủ ậ ả
III.9. Bàn lu n v A*ậ ề
III.10. ng d ng A* đ gi i bài toán Ta-canhỨ ụ ể ả
III.11. Các chi n l c tìm ki m laiế ượ ế
I. T NG QUAN THU T TOÁN – THU T GI IỔ Ậ Ậ Ả
Trong quá trình nghiên c u gi i quy t các v n đ – bài toán, ng i ta đã đ a ra nh ngứ ả ế ấ ề ườ ư ữ
nh n xét nh sau:ậ ư
Có nhi u bài toán cho đ n nay v n ch a tìm ra m t cách gi i theo ki u thu tề ế ẫ ư ộ ả ể ậ
toán và cũng không bi t là có t n t i thu t toán hay không.ế ồ ạ ậ
Có nhi u bài toán đã có thu t toán đ gi i nh ng không ch p nh n đ c vìề ậ ể ả ư ấ ậ ượ
th i gian gi i theo thu t toán đó quá l n ho c các đi u ki n cho thu t toán khóờ ả ậ ớ ặ ề ệ ậ
đáp ng.ứ
Có nh ng bài toán đ c gi i theo nh ng cách gi i vi ph m thu t toán nh ngữ ượ ả ữ ả ạ ậ ư
v n ch p nh n đ c.ẫ ấ ậ ượ
1
TTNT
T nh ng nh n đ nh trên, ng i ta th y r ng c n ph i có nh ng đ i m i cho kháiừ ữ ậ ị ườ ấ ằ ầ ả ữ ổ ớ
ni m thu t toán. Ng i ta đã m r ng hai tiêu chu n c a thu t toán: tính xác đ nh vàệ ậ ườ ở ộ ẩ ủ ậ ị
tính đúng đ n. Vi c m r ng tính xác đ nh đ i v i thu t toán đã đ c th hi n qua cácắ ệ ở ộ ị ố ớ ậ ượ ể ệ
gi i thu t đ quy và ng u nhiên. Tính đúng c a thu t toán bây gi không còn b t bu cả ậ ệ ẫ ủ ậ ờ ắ ộ
đ i v i m t s cách gi i bài toán, nh t là các cách gi i g n đúng. Trong th c ti n cóố ớ ộ ố ả ấ ả ầ ự ễ
nhi u tr ng h p ng i ta ch p nh n các cách gi i th ng cho k t qu t t (nh ngề ườ ợ ườ ấ ậ ả ườ ế ả ố ư
không ph i lúc nào cũng t t) nh ng ít ph c t p và hi u qu . Ch ng h n n u gi i m tả ố ư ứ ạ ệ ả ẳ ạ ế ả ộ
bài toán b ng thu t toán t i u đòi h i máy tính th c hiên nhi u năm thì chúng ta cóằ ậ ố ư ỏ ự ề
th s n lòng ch p nh n m t gi i pháp g n t i u mà ch c n máy tính ch y trong vàiể ẵ ấ ậ ộ ả ầ ố ư ỉ ầ ạ
ngày ho c vài gi .ặ ờ
Các cách gi i ch p nh n đ c nh ng không hoàn toàn đáp ng đ y đ các tiêu chu nả ấ ậ ượ ư ứ ầ ủ ẩ
c a thu t toán th ng đ c g i là các thu t gi i. Khái ni m m r ng này c a thu tủ ậ ườ ượ ọ ậ ả ệ ở ộ ủ ậ
toán đã m c a cho chúng ta trong vi c tìm ki m ph ng pháp đ gi i quy t các bàiở ử ệ ế ươ ể ả ế
toán đ c đ t ra.ượ ặ
M t trong nh ng thu t gi i th ng đ c đ c p đ n và s d ng trong khoa h c tríộ ữ ậ ả ườ ượ ề ậ ế ử ụ ọ
tu nhân t o là các cách gi i theo ki u Heuristicệ ạ ả ể
II. THU T GI I HEURISTICẬ Ả
Thu t gi i Heuristic là m t s m r ng khái ni m thu t toán. Nó th hi n cách gi iậ ả ộ ự ở ộ ệ ậ ể ệ ả
bài toán v i các đ c tính sau:ớ ặ
Th ng tìm đ c l i gi i t t (nh ng không ch c là l i gi i t t nh t)ườ ượ ờ ả ố ư ắ ờ ả ố ấ
Gi i bài toán theo thu t gi i Heuristic th ng d dàng và nhanh chóngả ậ ả ườ ễ
đ a ra k t qu h n so v i gi i thu t t i u, vì v y chi phí th p h n.ư ế ả ơ ớ ả ậ ố ư ậ ấ ơ
Thu t gi i Heuristic th ng th hi n khá t nhiên, g n gũi v i cáchậ ả ườ ể ệ ự ầ ớ
suy nghĩ và hành đ ng c a con ng i.ộ ủ ườ
Có nhi u ph ng pháp đ xây d ng m t thu t gi i Heuristic, trong đó ng i ta th ngề ươ ể ự ộ ậ ả ườ ườ
d a vào m t s nguyên lý c b n nh sau:ự ộ ố ơ ả ư
Nguyên lý vét c n thông minh:ạ Trong m t bài toán tìm ki m nào đó, khiộ ế
không gian tìm ki m l n, ta th ng tìm cách gi i h n l i không gian tìm ki mế ớ ườ ớ ạ ạ ế
ho c th c hi n m t ki u dò tìm đ c bi t d a vào đ c thù c a bài toán đặ ự ệ ộ ể ặ ệ ự ặ ủ ể
nhanh chóng tìm ra m c tiêu.ụ
Nguyên lý tham lam (Greedy): L y tiêu chu n t i u (trên ph m vi toànấ ẩ ố ư ạ
c c) c a bài toán đ làm tiêu chu n ch n l a hành đ ng cho ph m vi c c bụ ủ ể ẩ ọ ự ộ ạ ụ ộ
c a t ng b c (hay t ng giai đo n) trong quá trình tìm ki m l i gi i.ủ ừ ướ ừ ạ ế ờ ả
Nguyên lý th t :ứ ự Th c hi n hành đ ng d a trên m t c u trúc th t h p lýự ệ ộ ự ộ ấ ứ ự ợ
c a không gian kh o sát nh m nhanh chóng đ t đ c m t l i gi i t t.ủ ả ằ ạ ượ ộ ờ ả ố
2
TTNT
Hàm Heuristic: Trong vi c xây d ng các thu t gi i Heuristic, ng i taệ ự ậ ả ườ
th ng dùng các hàm Heuristic. Đó là các hàm đánh già thô, giá tr c a hàm phườ ị ủ ụ
thu c vào tr ng thái hi n t i c a bài toán t i m i b c gi i. Nh giá tr này, taộ ạ ệ ạ ủ ạ ỗ ướ ả ờ ị
có th ch n đ c cách hành đ ng t ng đ i h p lý trong t ng b c c a thu tể ọ ượ ộ ươ ố ợ ừ ướ ủ ậ
gi i.ả
Bài toán hành trình ng n nh t – ng d ng nguyên lý Greedyắ ấ ứ ụ
Bài toán: Hãy tìm m t hành trình cho m t ng i giao hàng đi qua n đi m khác nhau,ộ ộ ườ ể
m i đi m đi qua m t l n và tr v đi m xu t phát sao cho t ng chi u dài đo n đ ngỗ ể ộ ầ ở ề ể ấ ổ ề ạ ườ
c n đi là ng n nh t. Gi s r ng có con đ ng n i tr c ti p t gi a hai đi m b t kỳ. ầ ắ ấ ả ử ằ ườ ố ự ế ừ ữ ể ấ
T t nhiên ta có th gi i bài toán này b ng cách li t kê t t c con đ ng có th đi, tínhấ ể ả ằ ệ ấ ả ườ ể
chi u dài c a m i con đ ng đó r i tìm con đ ng có chi u dài ng n nh t. Tuy nhiên,ề ủ ỗ ườ ồ ườ ề ắ ấ
cách gi i này l i có đ ph c t p 0(n!) (m t hành trình là m t ả ạ ộ ứ ạ ộ ộ hoán v ịc a n đi m, doủ ể
đó, t ng s hành trình là s l ng hoán v c a m t t p n ph n t là n!). Do đó, khi sổ ố ố ượ ị ủ ộ ậ ầ ử ố
đ i lý tăng thì s con đ ng ph i xét s tăng lên r t nhanh.ạ ố ườ ả ẽ ấ
M t cách gi i đ n gi n h n nhi u và th ng cho k t qu t ng đ i t t là dùng m tộ ả ơ ả ơ ề ườ ế ả ươ ố ố ộ
thu t gi i Heuristic ng d ng nguyên lý Greedy. T t ng c a thu t gi i nh sau:ậ ả ứ ụ ư ưở ủ ậ ả ư
T đi m kh i đ u, ta li t kê t t c quãng đ ng t đi m xu t phát cho đ n nừ ể ở ầ ệ ấ ả ườ ừ ể ấ ế
đ i lý r i ch n đi theo con đ ng ng n nh t.ạ ồ ọ ườ ắ ấ
Khi đã đi đ n m t đ i lý, ch n đi đ n đ i lý k ti p cũng theo nguyên t c trên.ế ộ ạ ọ ế ạ ế ế ắ
Nghĩa là li t kê t t c con đ ng t đ i lý ta đang đ ng đ n nh ng đ i lý ch aệ ấ ả ườ ừ ạ ứ ế ữ ạ ư
đi đ n. Ch n con đ ng ng n nh t. L p l i quá trình này cho đ n lúc khôngế ọ ườ ắ ấ ặ ạ ế
còn đ i lý nào đ đi.ạ ể
B n có th quan sát hình sau đ th y đ c quá trình ch n l a. Theo nguyên lý Greedy,ạ ể ể ấ ượ ọ ự
ta l y tiêu chu n hành trình ng n nh t c a bài toán làm tiêu chu n cho ch n l a c cấ ẩ ắ ấ ủ ẩ ọ ự ụ
b . ộTa hy v ng r ng, khi đi trên n đo n đ ng ng n nh t thì cu i cùng ta s có m tọ ằ ạ ườ ắ ấ ố ẽ ộ
hành trình ng n nh t.ắ ấ Đi u này không ph i lúc nào cũng đúng. V i đi u ki n trongề ả ớ ề ệ
hình ti p theo thì thu t gi i cho chúng ta m t hành trình có chi u dài là 14 trong khiế ậ ả ộ ề
hành trình t i u là 13. K t qu c a thu t gi i Heuristic trong tr ng h p này ch l chố ư ế ả ủ ậ ả ườ ợ ỉ ệ
1 đ n v so v i k t qu t i u. Trong khi đó, đ ph c t p c a thu t gi i Heuristic nàyơ ị ớ ế ả ố ư ộ ứ ạ ủ ậ ả
ch là 0(nỉ2).
3
TTNT
Hình : Gi i bài toán s d ng nguyên lý Greedyả ử ụ
T t nhiên, thu t gi i theo ki u Heuristic đôi lúc l i đ a ra k t qu không t t, th m chíấ ậ ả ể ạ ư ế ả ố ậ
r t t nh tr ng h p hình sau.ấ ệ ư ườ ợ ở
4
TTNT
Bài toán phân vi c – ng d ng c a nguyên lý th tệ ứ ụ ủ ứ ự
M t công ty nh n đ c h p đ ng gia công m chi ti t máy Jộ ậ ượ ợ ồ ế 1, J2, … Jm. Công ty có n
máy gia công l n l t là Pầ ượ 1, P2, … Pn. M i chi ti t đ u có th đ c gia công trên b tọ ế ề ể ượ ấ
kỳ máy nào. M t khi đã gia công m t chi ti t trên m t máy, công vi s ti p t c choộ ộ ế ộ ệ ẽ ế ụ
đ n lúc hoàn thành, không th b c t ngang. Đ gia công m t vi c Jế ể ị ắ ể ộ ệ 1 trên m t máy b tộ ấ
kỳ ta c n dùng m t th i gian t ng ng là tầ ộ ờ ươ ứ 1. Nhi m v c a công ty là ph i làm sao giaệ ụ ủ ả
công xong toàn b n chi ti t trong th i gian s m nh t.ộ ế ờ ớ ấ
Chúng ta xét bài toán trong tr ng h p có 3 máy Pườ ợ 1, P2, P3 và 6 công vi c v i th i gianệ ớ ờ
là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. ta có m t ph ng án phân công (L) nh hình sau:ộ ươ ư
Theo hình này, t i th i đi m t=0, ta ti n hành gia công chi ti t Jạ ờ ể ế ế 2 trên máy P1, J5 trên P2
và J1 t i Pạ3. T i th i đi m t=2, công vi c Jạ ờ ể ệ 1 đ c hoàn thành, trên máy Pượ 3 ta gia công
ti p chi ti t Jế ế 4. Trong lúc đó, hai máy P1 và P2 v n đang th c hi n công vi c đ u tiênẫ ự ệ ệ ầ
mình … S đ phân vi c theo hình trên đ c g i là l c đ GANTT. Theo l c đơ ồ ệ ở ượ ọ ượ ồ ượ ồ
này, ta th y th i gian đ hoàn thành toàn b 6 công vi c là 12. Nh n xét m t cách c mấ ờ ể ộ ệ ậ ộ ả
tính ta th y r ng ph ng án (L) v a th c hi n là m t ph ng án không t t. Các máyấ ằ ươ ừ ự ệ ộ ươ ố
P1 và P2 có quá nhi u th i gian rãnh.ề ờ
Thu t toán tìm ph ng án t i u Lậ ươ ố ư 0 cho bài toán này theo ki u vét c n có đ ph c t pể ạ ộ ứ ạ
c O(mn) (v i m là s máy và n là s công vi c). Bây gi ta xét đ n m t thu t gi iỡ ớ ố ố ệ ờ ế ộ ậ ả
Heuristic r t đ n gi n (đ ph c t p O(n)) đ gi i bài toán này.ấ ơ ả ộ ứ ạ ể ả
S p x p các công vi c theo th t gi m d n v th i gian gia công.ắ ế ệ ứ ự ả ầ ề ờ
L n l t s p x p các vi c theo th t đó vào máy còn d nhi u th iầ ượ ắ ế ệ ứ ự ư ề ờ
gian nh t.ấ
V i t t ng nh v y, ta s có m t ph ng án L* nh sau:ớ ư ưở ư ậ ẽ ộ ươ ư
5