Tài liệu Thuật toán thuật giải

[email protected] Ebook Team 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 nh ng nh n xét như sau: – bài toán, ngư i ta ã ưa ra 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. 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 1 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 tu nhân t o là các cách gi i theo ki u Heuristic n và s d ng trong khoa h c trí 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 suy nghĩ và hành ng c a con ngư i. nhiên, g n gũi v i cách 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. 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 2 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 lý r i ch n i theo con ư ng ng n nh t. i m xu t phát cho nn Khi ã i nm 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(n2). 3 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. 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 J1, J2, … Jm. Công ty có n máy gia công l n lư t là P1, 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 J1 trên m t máy b t kỳ ta c n dùng m t th i gian tương ng là t1. 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 P1, 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: 4 Theo hình này, t i th i i m t=0, ta ti n hành gia công chi ti t J2 trên máy P1, J5 trên P2 và J1 t i P3. T i th i i m t=2, công vi c J1 ư c hoàn thành, trên máy P3 ta gia công ti p chi ti t J4. 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 L0 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 gian nh t. t ó vào máy còn dư nhi u th i V i tư tư ng như v y, ta s có m t phương án L* như sau: Rõ ràng phương án L* v a th c hi n cũng chính là phương án t i ưu c a trư ng h p này vì th i gian hoàn thành là 8, úng b ng th i gian c a công vi c J3. Ta hy v ng r ng m t gi i Heuristic ơn gi n như v y s là m t thu t gi i t i ưu. Nhưng ti c thay, 5 ta d dàng ưa ra ư c m t trư ng h p mà thu t gi i Heuristic không ưa ra ư c k t qu t i ưu. N u g i T* là th i gian gia công xong n chi ti t máy do thu t gi i Heuristic ưa ra và T0 là th i gian t i ưu thì ngư i ta ã ch ng minh ư c r ng , M là s máy V i k t qu này, ta có th xác l p ư c sai s mà chúng ta ph i gánh ch u n u dùng Heuristic thay vì tìm m t l i gi i t i ưu. Ch ng h n v i s máy là 2 (M=2) ta có , và ó chính là sai s c c i mà trư ng h p th c này, s máy càng l n thì sai s càng l n. trên ã gánh ch u. Theo công Trong trư ng h p M l n thì t s 1/M xem như b ng 0 . Như v y, sai s t i a mà ta ph i ch u là T* 4/3 T0, nghĩa là sai s t i a là 33%. Tuy nhiên, khó tìm ra ư c nh ng trư ng h p mà sai s úng b ng giá tr c c i, dù trong trư ng h p x u nh t. Thu t gi i Heuristic trong trư ng h p này rõ ràng ã cho chúng ta nh ng l i gi i tương i t t. III. CÁC PHƯƠNG PHÁP TÌM KI M HEURISTIC Qua các ph n trư c chúng ta tìm hi u t ng quan v ý tư ng c a thu t gi i Heuristic (nguyên lý Greedy và s p th t ). Trong m c này, chúng ta s i sâu vào tìm hi u m t s k thu t tìm ki m Heuristic – m t l p bài toán r t quan tr ng và có nhi u ng d ng trong th c t . III.1. C u trúc chung c a bài toán tìm ki m 6 ti n l i cho vi c trình bày, ta hãy dành chút th i gian làm rõ hơn " i tư ng" quan tâm c a chúng ta trong m c này. M t cách chung nh t, nhi u v n -bài toán ph c t p u có d ng "tìm ư ng i trong th " hay nói m t cách hình th c hơn là "xu t phát t m t nh c a m t th , tìm ư ng i hi u qu nh t n m t nh nào ó". M t phát bi u khác thư ng g p c a d ng bài toán này là : Cho trư c hai tr ng thái T0 và TG hãy xây d ng chu i tr ng thái T0, T1, T2, ..., Tn-1, Tn = TG sao cho : th a mãn m t i u ki n cho trư c (thư ng là nh nh t). Trong ó, Ti thu c t p h p S (g i là không gian tr ng thái – state space) bao g m t t c các tr ng thái có th có c a bài toán và cost(Ti-1, Ti) là chi phí bi n it tr ng thái Ti-1 sang tr ng thái Ti. Dĩ nhiên, t m t tr ng thái Ti ta có nhi u cách bi n i sang tr ng thái Ti+1. Khi nói n m t bi n i c th t Ti-1 sang Ti ta s dùng thu t ng hư ng i (v i ng ý nói v s l a ch n). Hình : Mô hình chung c a các v n -bài toán ph i gi i quy t b ng phương pháp tìm ki m l i gi i. Không gian tìm ki m là m t t p h p tr ng thái - t p các nút c a th . Chi phí c n thi t chuy n t tr ng thái T này sang tr ng thái Tk ư c bi u di n dư i d ng các con s n m trên cung n i gi a hai nút tư ng trưng cho hai tr ng thái. a s các bài toán thu c d ng mà chúng ta ang mô t u có th ư c bi u di n dư i d ng th . Trong ó, m t tr ng thái là m t nh c a th . T p h p S bao g m t t c các tr ng thái chính là t p h p bao g m t t c nh c a th . Vi c bi n i t tr ng thái Ti-1 sang tr ng thái Ti là vi c i t nh i di n cho Ti-1 sang nh i di n cho Ti theo cung n i gi a hai nh này. III.2. Tìm ki m chi u sâu và tìm ki m chi u r ng b n c có th hình dung m t cách c th b n ch t c a thu t gi i Heuristic, chúng ta nh t thi t ph i n m v ng hai chi n lư c tìm ki m cơ b n là tìm ki m theo chi u sâu (Depth First Search) và tìm ki m theo chi u r ng (Breath First Search). S dĩ chúng ta dùng t chi n lư c mà không ph i là phương pháp là b i vì trong th c t , 7 ngư i ta h u như ch ng bao gi v n d ng m t trong hai ki m tìm ki m này m t cách tr c ti p mà không ph i s a i gì. III.2.1. Tìm ki m chi u sâu (Depth-First Search) Trong tìm ki m theo chi u sâu, t i tr ng thái ( nh) hi n hành, ta ch n m t tr ng thái k ti p (trong t p các tr ng thái có th bi n i thành t tr ng thái hi n t i) làm tr ng thái hi n hành cho n lúc tr ng thái hi n hành là tr ng thái ích. Trong trư ng h p t i tr ng thái hi n hành, ta không th bi n i thành tr ng thái k ti p thì ta s quay lui (back-tracking) l i tr ng thái trư c tr ng thái hi n hành (tr ng thái bi n i thành tr ng thái hi n hành) ch n ư ng khác. N u tr ng thái trư c này mà cũng không th bi n i ư c n a thì ta quay lui l i tr ng thái trư c n a và c th . N u ã quay lui n tr ng thái kh i u mà v n th t b i thì k t lu n là không có l i gi i. Hình nh sau minh h a ho t ng c a tìm ki m theo chi u sâu. Hình : Hình nh c a tìm ki m chi u sâu. Nó ch lưu ý "m r ng" tr ng thái ư c ch n mà không "m r ng" các tr ng thái khác (nút màu tr ng trong hình v ). III.2.2. Tìm ki m chi u r ng (Breath-First Search) Ngư c l i v i tìm ki m theo ki u chi u sâu, tìm ki m chi u r ng mang hình nh c a v t d u loang. T tr ng thái ban u, ta xây d ng t p h p S bao g m các tr ng thái k ti p (mà t tr ng thái ban u có th bi n i thành). Sau ó, ng v i m i tr ng thái Tk trong t p S, ta xây d ng t p Sk bao g m các tr ng thái k ti p c a Tk r i l n lư t b sung các Sk vào S. Quá trình này c l p l i cho n lúc S có ch a tr ng thái k t thúc ho c S không thay i sau khi ã b sung t t c Sk. 8 Hình : Hình nh c a tìm ki m chi u r ng. T i m t bư c, m i tr ng thái r ng, không b sót tr ng thái nào. u ư cm Chi u sâu Chi u r ng Tính hi u qu Hi u qu khi l i gi i n m sâu trong cây tìm ki m và có m t phương án ch n hư ng i chính xác. Hi u qu c a chi n lư c ph thu c vào phương án ch n hư ng i. Phương án càng kém hi u qu thì hi u qu c a chi n lư c càng gi m. Thu n l i khi mu n tìm ch m t l i gi i. Hi u qu khi l i gi i n m g n g c c a cây tìm ki m. Hi u qu c a chi n lư c ph thu c vào sâu c a l i gi i. L i gi i càng xa g c thì hi u qu c a chi n lư c càng gi m. Thu n l i khi mu n tìm nhi u l i gi i. Lư ng b nh s d ng lưu tr các tr ng thái Ch lưu l i các tr ng thái chưa xét n. Ph i lưu toàn b các tr ng thái. Trư ng h p x u nh t Vét c n toàn b Vét c n toàn b . Trư ng h p t t nh t Phương án ch n hư ng i tuy t i chính xác. L i gi i ư c xác nh m t cách tr c ti p. Vét c n toàn b . Tìm ki m chi u sâu và tìm ki m chi u r ng u là các phương pháp tìm ki m có h th ng và ch c ch n tìm ra l i gi i. Tuy nhiên, do b n ch t là vét c n nên v i nh ng bài toán có không gian l n thì ta không th dùng hai chi n lư c này ư c. Hơn n a, 9 hai chi n lư c này u có tính ch t "mù quáng" vì chúng không chú ý n nh ng thông tin (tri th c) tr ng thái hi n th i và thông tin v ích c n t t i cùng m i quan h gi a chúng. Các tri th c này vô cùng quan tr ng và r t có ý nghĩa thi t k các thu t gi i hi u qu hơn mà ta s p s a bàn n. III.3. Tìm ki m leo III.3.1. Leo i i ơn gi n Tìm ki m leo i theo úng nghĩa, nói chung, th c ch t ch là m t trư ng h p c bi t c a tìm ki m theo chi u sâu nhưng không th quay lui. Trong tìm ki m leo i, vi c l a ch n tr ng thái ti p theo ư c quy t nh d a trên m t hàm Heuristic. Hàm Heuristic là gì ? Thu t ng "hàm Heuristic" mu n nói lên i u gì? Ch ng có gì ghê g m. B n ã quen v i nó r i! ó ơn gi n ch là m t ư c lư ng v kh năng d n n l i gi i tính t tr ng thái ó (kho ng cách gi a tr ng thái hi n t i và tr ng thái ích). Ta s quy ư c g i hàm này là h trong su t giáo trình này. ôi lúc ta cũng c p n chi phí t i ưu th c s t m t tr ng thái d n n l i gi i. Thông thư ng, giá tr này là không th tính toán ư c (vì tính ư c ng nghĩa là ã bi t con ư ng n l i gi i !) mà ta ch dùng nó như m t cơ s suy lu n v m t lý thuy t mà thôi ! Hàm h, ta quy ư c r ng, luôn tr ra k t qu là m t s không âm. b n c th c s n m ư c ý nghĩa c a hai hàm này, hãy quan sát hình sau trong ó minh h a chi phí t i ưu th c s và chi phí ư c lư ng. Hình Chi phí ư c lư ng h’ = 6 và chi phí t i ưu th c s h = 4+5 = 9 ( i theo ư ng 1-3-7) B n ang trong m t thành ph xa l mà không có b n trong tay và ta mu n i vào khu trung tâm? M t cách suy nghĩ ơn gi n, chúng ta s nh m vào hư ng nh ng tòa cao c c a khu trung tâm! Tư tư ng 1) N u tr ng thái b t u cũng là tr ng thái ích thì thoát và báo là ã tìm ư c l i gi i. Ngư c l i, t tr ng thái hi n hành (Ti) là tr ng thái kh i u (T0) 10 2) L p l i cho n khi t n tr ng thái k t thúc ho c cho n khi không t n t i m t tr ng thái ti p theo h p l (Tk) c a tr ng thái hi n hành : a. b. t Tk là m t tr ng thái ti p theo h p l c a tr ng thái hi n hành Ti. ánh giá tr ng thái Tk m i : b.1. N u là tr ng thái k t thúc thì tr v tr này và thoát. b.2. N u không ph i là tr ng thái k t thúc nhưng t t hơn tr ng thái hi n hành thì c p nh t nó thành tr ng thái hi n hành. b.3. N u nó không t t hơn tr ng thái hi n hành thì ti p t c vòng l p. Mã gi Ti := T0; Stop :=FALSE; WHILE Stop=FALSE DO BEGIN IF Ti  TG THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Better:=FALSE; WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN IF THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Tk := ; IF THEN BEGIN Ti :=Tk; Better:=TRUE; 11 END; END; END; {WHILE} END; {ELSE} END;{WHILE} M nh "h’(Tk) t t hơn h’(Ti)" nghĩa là gì? ây là m t khái ni m chung chung. Khi cài t thu t gi i, ta ph i cung c p m t nh nghĩa tư ng minh v t t hơn. Trong m t s trư ng h p, t t hơn là nh hơn : h’(Tk) < h’(Ti); m t s trư ng h p khác t t hơn là l n hơn h’(Tk) > h’(Ti)...Ch ng h n, i v i bài toán tìm ư ng i ng n nh t gi a hai i m. N u dùng hàm h’ là hàm cho ra kho ng cách theo ư ng chim bay gi a v trí hi n t i (tr ng thái hi n t i) và ích n (tr ng thái ích) thì t t hơn nghĩa là nh hơn. V n c n làm rõ k ti p là th nào là ? M t tr ng thái k ti p h p l là tr ng thái chưa ư c xét n. Gi s h c a tr ng thái hi n t i Ti có giá tr là h(Ti) = 1.23 và t Ti ta có th bi n i sang m t trong 3 tr ng thái k ti p l n lư t là Tk1, Tk2, Tk3 v i giá tr các hàm h tương ng là h(Tk1) = 1.67, h(Tk2) = 2.52, h’(Tk3) = 1.04. u tiên, Tk s ư c gán b ng Tk1, nhưng vì h’(Tk) = h’(Tk1) > h’(Ti) nên Tk không ư c ch n. K ti p là Tk s ư c gán b ng Tk2 và cũng không ư c ch n. Cu i cùng thì Tk3 ư c ch n. Nhưng gi s h’(Tk3) = 1.3 thì c Tk3 cũng không ư c ch n và m nh s có giá tr TRUE. Gi i thích này có v hi n nhiên nhưng có l c n thi t tránh nh m l n cho b n c. th y rõ ho t ng c a thu t gi i leo i. Ta hãy xét m t bài toán minh h a sau. Cho 4 kh i l p phương gi ng nhau A, B, C, D. Trong ó các m t (M1), (M2), (M3), (M4), (M5), (M6) có th ư c tô b ng 1 trong 6 màu (1), (2), (3), (4), (5), (6). Ban u các kh i l p phương ư c x p vào m t hàng. M i m t bư c, ta ch ư c xoay m t kh i l p phương quanh m t tr c (X,Y,Z) 900 theo chi u b t kỳ (nghĩa là ngư c chi u hay thu n chi u kim ng h cũng ư c). Hãy xác nh s bư c quay ít nh t sao cho t t c các m t c a kh i l p phương trên 4 m t c a hàng là có cùng màu như hình v . 12 Hình : Bài toán 4 kh i l p phương gi i quy t v n , trư c h t ta c n nh nghĩa m t hàm G dùng ánh giá m t tình tr ng c th có ph i là l i gi i hay không? B n c có th d dàng ưa ra m t cài t c a hàm G như sau : IF (Gtrái + Gph i + Gtrên + Gdư i + Gtrư c + Gsau) = 16 THEN G:=TRUE ELSE G:=FALSE; Trong ó, Gph i là s lư ng các m t có cùng màu c a m t bên ph i c a hàng. Tương t cho Gtrái, Gtrên, Ggi a, Gtrư c, Gsau. Tuy nhiên, do các kh i l p phương A,B,C,D là hoàn toàn tương t nhau nên tương quan gi a các m t c a m i kh i là gi ng nhau. Do ó, n u có 2 m t không i nhau trên hàng ng màu thì 4 m t còn l i c a hàng cũng ng màu. T ó ta ch c n hàm G ư c nh nghĩa như sau là : IF Gph i + Gdư i = 8 THEN G:=TRUE ELSE G:=FALSE; Hàm h (ư c lư ng kh năng d n như sau : n l i gi i c a m t tr ng thái) s ư c nh nghĩa h = Gtrái + Gph i + Gtrên + Gdư i Bài toán này ơn gi n thu t gi i leo ph i lúc nào ta cũng may m n như th ! n ây, có th chúng ta s làm tr ng thái hi n t i thì t s nhanh chóng d n nl i th c s giúp chúng ta d n xong thu t gi i leo id c i có th ho t ng t t. Tuy nhiên, không n y sinh m t ý tư ng. N u ã ch n tr ng thái t t hơn i sao không ch n tr ng thái t t nh t ? Như v y, có l ta gi i hơn! Ta s bàn lu n v v n : "li u c i ti n này có n l i gi i nhanh hơn hay không?" ngay sau khi trình bày ng. III.3.2. Leo id c ng V cơ b n, leo ng s duy t t các tr ng thái k ti p u tiên t t id c ng cũng gi ng như leo i, ch khác i m là leo id c t c các hư ng i có th và ch n i theo tr ng thái t t nh t trong s ti p có th có (trong khi ó leo i ch ch n i theo tr ng thái k hơn tr ng thái hi n hành mà nó tìm th y). 13 Tư tư ng 1) N u tr ng thái b t u cũng là tr ng thái ích thì thoát và báo là ã tìm ư c l i gi i. Ngư c l i, t tr ng thái hi n hành (Ti) là tr ng thái kh i u (T0) 2) L p l i cho n khi t n tr ng thái k t thúc ho c cho n khi (Ti) không t n t i m t tr ng thái k ti p (Tk) nào t t hơn tr ng thái hi n t i (Ti) a) Ti. t S b ng t p t t c tr ng thái k ti p có th có c a Ti và t t hơn b) Xác nh Tkmax là tr ng thái t t nh t trong t p S t Ti = Tkmax Mã gi Ti := T0; Stop :=FALSE; WHILE Stop=FALSE DO BEGIN IF Ti  TG THEN BEGIN ; STOP :=TRUE; END; ELSE BEGIN Best:=h’(Ti); Tmax := Ti; WHILE DO BEGIN Tk := ; IF THEN BEGIN Best :=h’(Tk); Tmax := Tk; END; 14 END; IF (Best>Ti) THEN Ti := Tmax; ELSE BEGIN ; STOP:=TRUE; END; END; {ELSE IF} END;{WHILE STOP} III.3.3. ánh giá So v i leo i ơn gi n, leo id c ng có ưu i m là luôn luôn ch n hư ng có tri n v ng nh t i. Li u i u này có m b o leo id c ng luôn t t hơn leo i ơn gi n không? Câu tr l i là không. Leo id c ng ch t t hơn leo i ơn gi n trong m t s trư ng h p mà thôi. ch n ra ư c hư ng i t t nh t, leo id c ng ph i duy t qua t t c các hư ng i có th có t i tr ng thái hi n hành. Trong khi ó, leo i ơn gi n ch ch n i theo tr ng thái u tiên t t hơn (so v i tr ng thái hi n hành) mà nó tìm ra ư c. Do ó, th i gian c n thi t leo id c ng ch n ư c m t hư ng i s l n hơn so v i leo i ơn gi n. Tuy v y, do lúc nào cũng ch n hư ng i t t nh t nên leo id c ng thư ng s tìm n l i gi i sau m t s bư c ít hơn so v i leo i ơn gi n. Nói m t cách ng n g n, leo id c ng s t n nhi u th i gian hơn cho m t bư c nhưng l i i ít bư c hơn; còn leo i ơn gi n t n ít th i gian hơn cho m t bư c i nhưng l i ph i i nhi u bư c hơn. ây chính là y u t ư c và m t gi a hai thu t gi i nên ta ph i cân nh c k lư ng khi l a ch n thu t gi i. C hai phương pháp leo núi ơn gi n và leo núi d c ng u có kh năng th t b i trong vi c tìm l i gi i c a bài toán m c dù l i gi i ó th c s hi n h u. C hai gi i thu t u có th k t thúc khi t ư c m t tr ng thái mà không còn tr ng thái nào t t hơn n a có th phát sinh nhưng tr ng thái này không ph i là tr ng thái ích. i u này s x y ra n u chương trình t nm t i mc c i a phương, m t o n ơn i u ngang. i mc c i a phương (a local maximum) : là m t tr ng thái t t hơn t t c lân c n c a nó nhưng không t t hơn m t s tr ng thái khác xa hơn. Nghĩa là t i m t i m c c i a phương, m i tr ng thái trong m t lân c n c a tr ng thái hi n t i ux u hơn tr ng thái hi n t i. Tuy có dáng v c a l i gi i nhưng các c c i a phương không ph i là l i gi i th c s . Trong trư ng h p này, chúng ư c g i là nh ng ng n i th p. o n ơn i u ngang (a plateau) : là m t vùng b ng ph ng c a không gian tìm ki m, trong ó, toàn b các tr ng thái lân c n u có cùng giá tr . 15 Hình : Các tình hu ng khó khăn cho tìm ki m leo èo. i phó v i các các i m này, ngư i ta ã ưa ra m t s gi i pháp. Ta s tìm hi u 2 trong s các gi i pháp này. Nh ng gi i này, không th c s gi i quy t tr n v n v n mà ch là m t phương án c u nguy t m th i mà thôi. Phương án u tiên là k t h p leo i và quay lui. Ta s quay lui l i các tr ng thái trư c ó và th i theo hư ng khác. Thao tác này h p lý n u t i các tr ng thái trư c ó có m t hư ng i t t mà ta ã b qua trư c ó. ây là m t cách khá hay i phó v i các i m c c i a phương. Tuy nhiên, do c i m c a leo i là "bư c sau cao hơn bư c trư c" nên phương án này s th t b i khi ta xu t phát t m t i m quá cao ho c xu t phát t m t nh i mà n ư c l i gi i c n ph i i qua m t "thung lũng" th t sâu như trong hình sau. Hình : M t trư ng h p th t b i c a leo èo k t h p quay lui. Cách th hai là th c hi n m t bư c nh y v t theo hư ng nào ó th nm t vùng m i c a không gian tìm ki m. Nôm na là "bư c" liên t c nhi u "bư c" (ch ng h n 5,7,10, …) mà t m th i "quên" i vi c ki m tra "bư c sau cao hơn bư c trư c". Ti p c n có v hi u qu khi ta g p ph i m t o n ơn i u ngang. Tuy nhiên, nh y v t cũng có nghĩa là ta ã b qua cơ h i ti n n l i gi i th c s . Trong trư ng h p chúng ta ang ng khá g n l i gi i, vi c nh y v t s ưa chúng ta sang m t v trí hoàn toàn xa l , mà t ó, có th s d n chúng ta n m t r c r i ki u khác. Hơn 16 n a, s bư c nh y là bao nhiêu và nh y theo hư ng nào là m t v n nhi u vào c i m không gian tìm ki m c a bài toán. ph thu c r t Hình M t trư ng h p khó khăn cho phương án "nh y v t". Leo núi là m t phương pháp c c b b i vì nó quy t nh s làm gì ti p theo d a vào m t ánh giá v tr ng thái hi n t i và các tr ng thái k ti p có th có (t t hơn tr ng thái hi n t i, tr ng thái t t nh t t t hơn tr ng thái hi n t i) thay vì ph i xem xét m t cách toàn di n trên t t c các tr ng thái ã i qua. Thu n l i c a leo núi là ít g p s bùng n t h p hơn so v i các phương pháp toàn c c. Nhưng nó cũng gi ng như các phương pháp c c b khác ch là không ch c ch n tìm ra l i gi i trong trư ng h p x u nh t. M t l n n a, ta kh ng nh l i vai trò quy t nh c a hàm Heuristic trong quá trình tìm ki m l i gi i. V i cùng m t thu t gi i (như leo i ch ng h n), n u ta có m t hàm Heuristic t t hơn thì k t qu s ư c tìm th y nhanh hơn. Ta hãy xét bài toán v các kh i ư c trình bày hình sau. Ta có hai thao tác bi n i là: + L y m t kh i nh m t c t b t kỳ và t nó lên m t ch tr ng t o thành m t c t m i. Lưu ý là ch có th t o ra t i a 2 c t m i. + L y m t kh i Hãy xác nh m t c t và nh s thao tác ít nh t bi n t nó lên nh m t c t khác i c t ã cho thành c t k t qu . 17 Hình : Tr ng thái kh i Gi s ban u và tr ng thái k t thúc u ta dùng m t hàm Heuristic ơn gi n như sau : H1 : C ng 1 i m cho m i kh i v trí úng so v i tr ng thái ích. Tr cho m i kh i t v trí sai so v i tr ng thái ích. 1 i m Dùng hàm này, tr ng thái k t thúc s có giá tr là 8 vì c 8 kh i u ư c t v trí úng. Tr ng thái kh i u có giá tr là 4 (vì nó có 1 i m c ng cho các kh i C, D, E, F, G, H và 1 i m tr cho các kh i A và B). Ch có th có m t di chuy n t tr ng thái kh i u, ó là d ch chuy n kh i A xu ng t o thành m t c t m i (T1). i u ó sinh ra m t tr ng thái v i s i m là 6 (vì v trí c a kh i A bây gi sinh ra 1 i m c ng hơn là m t i m tr ). Th t c leo núi s ch p nh n s d ch chuy n ó. T n ba tr ng thái Ta, Tb, Tc tr ng thái m i T1, có ba di chuy n có th th c hi n d n ư c minh h a trong hình dư i. Nh ng tr ng thái này có s i m là : h’(Ta)= 4; h’(Tb) = 4 và h’(Tc) = 4 T1 TA TB TC 18