Thuật toán thuật giải

Chia sẻ: 4 4 | Ngày: | Loại File: PDF | Số trang:99

Thêm vào BST

Báo xấu

56
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật ngữ "Công nghệ Thông tin" xuất hiện lần đầu vào năm 1958 trong bài viết xuất bản tại tạp chí Harvard Business Review. Hai tác giả của bài viết, Leavitt và Whisler đã bình luận: "Công nghệ mới chưa thiết lập một tên riêng. Chúng ta sẽ gọi là công nghệ thông tin (Information Technology - IT)." [3]

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán thuật giải

WWW.VIETDOWN.ORG
VietDown Organization 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 – 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. 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 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. 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 m xu t phát cho nn i lý r i ch n i theo con ư ng ng n nh t. 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 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: 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 trên ã gánh ch u. Theo công th c này, s máy càng l n thì sai s càng l n. 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 u ư cm r ng, không b sót tr ng thái nào. Chi u sâu Chi u r ng Tính hi u qu Hi u qu khi l i gi i n m Hi u qu khi l i gi i sâu trong cây tìm ki m và n m g n g c c a cây có m t phương án ch n tìm ki m. Hi u qu hư ng i chính xác. Hi u c a chi n lư c ph qu c a chi n lư c ph thu c vào sâu c a thu c vào phương án ch n l i gi i. L i gi i càng hư ng i. Phương án càng xa g c thì hi u qu kém hi u qu thì hi u qu c a chi n lư c càng c a chi n lư c càng gi m. gi m. Thu n l i khi Thu n l i khi mu n tìm ch mu n tìm nhi u l i m t l i gi i. gi i. Lư ng b nh s Ch lưu l i các tr ng thái Ph i lưu toàn b các d ng lưu tr các chưa xét n. tr ng thái. tr ng thái Trư ng h p x u Vét c n toàn b Vét c n toàn b . nh t Trư ng h p t t nh t Phương án ch n hư ng i Vét c n toàn b . tuy t i chính xác. L i gi i ư c xác nh m t cách tr c ti p. 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 i III.3.1. Leo 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. 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. b. á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 n l i gi i c a m t tr ng thái) s ư c nh nghĩa như sau : h = Gtrái + Gph i + Gtrên + Gdư i Bài toán này ơn gi n thu t gi i leo i có th ho t ng t t. Tuy nhiên, không ph i lúc nào ta cũng may m n như th ! n ây, có th chúng ta s n y sinh m t ý tư ng. N u ã ch n tr ng thái t t hơn làm tr ng thái hi n t i thì t i sao không ch n tr ng thái t t nh t ? Như v y, có l ta s nhanh chóng d n nl i gi i hơn! Ta s bàn lu n v v n : "li u c i ti n này có th c s giúp chúng ta d n n l i gi i nhanh hơn hay không?" ngay sau khi trình bày xong thu t gi i leo id c ng. III.3.2. Leo id c ng V cơ b n, leo id c ng cũng gi ng như leo i, ch khác i m là leo id c ng s duy t t t c các hư ng i có th và ch n i theo tr ng thái t t nh t trong s các tr ng thái k ti p có th có (trong khi ó leo i ch ch n i theo tr ng thái k ti p u tiên t t 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) 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 Ti. 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 ph thu c r t nhi u vào c i m không gian tìm ki m c a bài toán. 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 nh m t c t và t nó lên nh m t c t khác Hãy xác nh s thao tác ít nh t bi n i c t ã cho thành c t k t qu . 17
Hình : Tr ng thái kh i u và tr ng thái k t thúc Gi s ban 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 1 i m cho m i kh i t v trí sai so v i tr ng thái ích. 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 tr ng thái m i T1, có ba di chuy n có th th c hi n d n n ba tr ng thái Ta, Tb, Tc ư 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