Thuật toán và giải thuật - Hoàng Kiếm Part 3

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

86
lượt xem 21
download

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

Đánh giá So với leo đồi đơn giản, leo đồi dố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 đồi dốc đứng luôn tốt hơn leo đồi đơn giản không ? Câu trả lời là không

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 3

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 Sưu t m b i: www.daihoc.com.vn
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 Sưu t m b i: www.daihoc.com.vn
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 Sưu t m b i: www.daihoc.com.vn
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 Sưu t m b i: www.daihoc.com.vn
Hình Các tr ng thái có th t ư ct T1 Th t c leo núi s t m d ng b i vì t t c các tr ng thái này có s i m th p hơn tr ng thái hi n hành. Quá trình tìm ki m ch d ng l i m t tr ng thái c c i a phương mà không ph i là c c i toàn c c. Chúng ta có th l i cho chính gi i thu t leo i vì ã th t b i do không t m nhìn t ng quát tìm ra l i gi i. Nhưng chúng ta cũng có th l i cho hàm Heuristic và c g ng s a i nó. Gi s ta thay hàm ban u b ng hàm Heuristic sau ây : H2 : i v i m i kh i ph tr úng (kh i ph tr là kh i n m bên dư i kh i hi n t i), c ng 1 i m, ngư c l i tr 1 i m. Dùng hàm này, tr ng thái k t thúc có s i m là 28 vì B n m úng v trí và không có kh i ph tr nào, C úng v trí ư c 1 i m c ng v i 1 i m do kh i ph tr B n m úng v trí nên C ư c 2 i m, D ư c 3 i m, ....Tr ng thái kh i u có s i m là – 28. Vi c di chuy n A xu ng t o thành m t c t m i làm sinh ra m t tr ng thái v i s i m là h’(T1) = –21 vì A không còn 7 kh i sai phía dư i nó n a. Ba tr ng thái có th phát sinh ti p theo bây gi có các i m s là : h’(Ta)=–28; h’(Tb)=–16 và h’(Tc) = – 15. Lúc này th t c leo núi d c ng s ch n di chuy n n tr ng thái Tc, ó có m t kh i úng. Qua hàm H2 này ta rút ra m t nguyên t c : t t hơn không ch có nghĩa là có nhi u ưu i m hơn mà còn ph i ít khuy t i m hơn. Hơn n a, khuy t i m không có nghĩa ch là s sai bi t ngay t i m t v trí mà còn là s khác bi t trong tương quan gi a các v trí. Rõ ràng là ng v m t k t qu , cùng m t th t c leo i nhưng hàm H1 b th t b i (do ch bi t ánh giá ưu i m) còn hàm H2 m i này l i ho t ng m t cách hoàn h o (do bi t ánh giá c ưu i m và khuy t i m). áng ti c, không ph i lúc nào chúng ta cũng thi t k ư c m t hàm Heuristic hoàn h o như th . Vì vi c ánh giá ưu i m ã khó, vi c ánh giá khuy t i m càng khó và tinh t hơn. Ch ng h n, xét l i v n mu n i vào khu trung tâm c a m t thành ph xa l . hàm Heuristic hi u qu , ta c n ph i ưa các thông tin v các ư ng m t chi u và các ngõ c t, mà trong trư ng h p m t thành ph hoàn toàn xa l thì ta khó ho c không th bi t ư c nh ng thông tin này. n ây, chúng ta hi u rõ b n ch t c a hai thu t gi i ti p c n theo chi n lư c tìm ki m chi u sâu. Hi u qu c a c hai thu t gi i leo i ơn gi n và leo id c ng ph thu c vào : + Ch t lư ng c a hàm Heuristic. + c i m c a không gian tr ng thái. + Tr ng thái kh i u. Sau ây, chúng ta s tìm hi u m t ti p c n theo m i, k t h p ư c s c m nh c a c tìm ki m chi u sâu và tìm ki m chi u r ng. M t thu t gi i r t linh ng và có th nói là m t thu t gi i kinh i n c a Heuristic. 19 Sưu t m b i: www.daihoc.com.vn
III.4. Tìm ki m ưu tiên t i ưu (best-first search) Ưu i m c a tìm ki m theo chi u sâu là không ph i quan tâm n s m r ng c a t t c các nhánh. Ưu i m c a tìm ki m chi u r ng là không b sa vào các ư ng d n b t c (các nhánh c t). Tìm ki m ưu tiên t i ưu s k t h p 2 phương pháp trên cho phép ta i theo m t con ư ng duy nh t t i m t th i i m, nhưng ng th i v n "quan sát" ư c nh ng hư ng khác. N u con ư ng ang i "có v " không tri n v ng b ng nh ng con ư ng ta ang "quan sát" ta s chuy n sang i theo m t trong s các con ư ng này. ti n l i ta s dùng ch vi t t t BFS thay cho tên g i tìm ki m ưu tiên t i ưu. M t cách c th , t i m i bư c c a tìm ki m BFS, ta ch n i theo tr ng thái có kh năng cao nh t trong s các tr ng thái ã ư c xét cho n th i i m ó. (khác v i leo id c ng là ch ch n tr ng thái có kh năng cao nh t trong s các tr ng thái k ti p có th n ư c t tr ng thái hi n t i). Như v y, v i ti p c n này, ta s ưu tiên i vào nh ng nhánh tìm ki m có kh năng nh t (gi ng tìm ki m leo id c ng), nhưng ta s không b l n qu n trong các nhánh này vì n u càng i sâu vào m t hư ng mà ta phát hi n ra r ng hư ng này càng i thì càng t , n m c nó x u hơn c nh ng hư ng mà ta chưa i, thì ta s không i ti p hư ng hi n t i n a mà ch n i theo m t hư ng t t nh t trong s nh ng hư ng chưa i. ó là tư tư ng ch o c a tìm ki m BFS. hi u ư c tư tư ng này. B n hãy xem ví d sau : Hình Minh h a thu t gi i Best-First Search Kh i u, ch có m t nút (tr ng thái) A nên nó s ư c m r ng t o ra 3 nút m i B,C và D. Các con s dư i nút là giá tr cho bi t t t c a nút. Con s càng nh , nút càng t t. Do D là nút có kh năng nh t nên nó s ư c m r ng ti p sau nút A và sinh ra 2 nút k ti p là E và F. n ây, ta l i th y nút B có v có kh năng nh t (trong các nút B,C,E,F) nên ta s ch n m r ng nút B và t o ra 2 nút G và H. Nhưng l i m t l n n a, hai nút G, H này ư c ánh giá ít kh năng hơn E, vì th s chú ý l i 20 Sưu t m b i: www.daihoc.com.vn
tr v E. E ư c m r ng và các nút ư c sinh ra t E là I và J. bư c k ti p, J s ư c m r ng vì nó có kh năng nh t. Quá trình này ti p t c cho n khi tìm th y m t l i gi i. Lưu ý r ng tìm ki m này r t gi ng v i tìm ki m leo id c ng, v i 2 ngo i l . Trong leo núi, m t tr ng thái ư c ch n và t t c các tr ng thái khác b lo i b , không bao gi chúng ư c xem xét l i. Cách x lý d t khoát này là m t c trưng c a leo i. Trong BFS, t i m t bư c, cũng có m t di chuy n ư c ch n nhưng nh ng cái khác v n ư c gi l i, ta có th tr l i xét sau ó khi tr ng thái hi n t i tr nên kém kh năng hơn nh ng tr ng thái ã ư c lưu tr . Hơn n a, ta ch n tr ng thái t t nh t mà không quan tâm n nó có t t hơn hay không các tr ng thái trư c ó. i u này tương ph n v i leo i vì leo i s d ng n u không có tr ng thái ti p theo nào t t hơn tr ng thái hi n hành. cài t các thu t gi i theo ki u tìm ki m BFS, ngư i ta thư ng c n dùng 2 t p h p sau : OPEN : t p ch a các tr ng thái ã ư c sinh ra nhưng chưa ư c xét n (vì ta ã ch n m t tr ng thái khác). Th c ra, OPEN là m t lo i hàng i ưu tiên (priority queue) mà trong ó, ph n t có ưu tiên cao nh t là ph n t t t nh t. Ngư i ta thư ng cài t hàng i ưu tiên b ng Heap. Các b n có th tham kh o thêm trong các tài li u v C u trúc d li u v lo i d li u này. CLOSE : t p ch a các tr ng thái ã ư c xét n. Chúng ta c n lưu tr nh ng tr ng thái này trong b nh phòng trư ng h p khi m t tr ng thái m i ư c t o ra l i trùng v i m t tr ng thái mà ta ã xét n trư c ó. Trong trư ng h p không gian tìm ki m có d ng cây thì không c n dùng t p này. Thu t gi i BEST-FIRST SEARCH 1. t OPEN ch a tr ng thái kh i u. 2. Cho n khi tìm ư c tr ng thái ích ho c không còn nút nào trong OPEN, th c hi n : 2.a. Ch n tr ng thái t t nh t (Tmax) trong OPEN (và xóa Tmax kh i OPEN) 2.b. N u Tmax là tr ng thái k t thúc thì thoát. 2.c. Ngư c l i, t o ra các tr ng thái k ti p Tk có th có t tr ng thái Tmax. i v i m i tr ng thái k ti p Tk th c hi n : Tính f(Tk); Thêm Tk vào OPEN BFS khá ơn gi n. Tuy v y, trên th c t , cũng như tìm ki m chi u sâu và chi u r ng, hi m khi ta dùng BFS m t cách tr c ti p. Thông thư ng, ngư i ta thư ng dùng các phiên b n c a BFS là AT, AKT và A* 21 Sưu t m b i: www.daihoc.com.vn
Thông tin v quá kh và tương lai Thông thư ng, trong các phương án tìm ki m theo ki u BFS, t t f c a m t tr ng thái ư c tính d a theo 2 hai giá tr mà ta g i là là g và h’. h’ chúng ta ã bi t, ó là m t ư c lư ng v chi phí t tr ng thái hi n hành cho n tr ng thái ích (thông tin tương lai). Còn g là "chi u dài quãng ư ng" ã i t tr ng thái ban u cho n tr ng thái hi n t i (thông tin quá kh ). Lưu ý r ng g là chi phí th c s (không ph i chi phí ư c lư ng). d hi u, b n hãy quan sát hình sau : Hình 6.14 Phân bi t khái ni m g và h’ K t h p g và h’ thành f’ (f’ = g + h’) s th hi n m t ư c lư ng v "t ng chi phí" cho con ư ng t tr ng thái b t u n tr ng thái k t thúc d c theo con ư ng i qua tr ng thái hi n hành. thu n ti n cho thu t gi i, ta quy ư c là g và h’ u không âm và càng nh nghĩa là càng t t. 22 Sưu t m b i: www.daihoc.com.vn