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

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

Thêm vào BST

Báo xấu

101
lượt xem 22
download

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

Nếu chi phí từ trạng thái khác luôn là hằng số thì thuật giải A* trở thành thuật giải tìm kiếm theo chiều rộng . Lý do là vì tât cả nhũng trạng thái cách trạng thái khởi đầu n bước đều có cùng giá trị g và vì thế có cùng f' và giá trị này sẽ nhỏ hơn tất cả

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 5

f’(Fagaras)  g(Fagaras)+ h’(Fagaras)  239+178 417 h’(Oradea)  380 g(Oradea)  g(Sibiu)+cost(Sibiu, Oradea)  140+151  291 f’(Oradea)  g(Oradea)+ h’(Oradea)  291+380  671 h’(R.Vilcea)  193 g(R.Vilcea)  g(Sibiu)+cost(Sibiu, R.Vilcea)  140+80  220 f’(R.Vilcea)  g(R.Vilcea)+ h’(R.Vilcea)  220+193  413 Nút Arad ã có trong CLOSE. Tuy nhiên, do g(Arad) m i ư c t o ra (có giá tr 280) l n hơn g(Arad) lưu trong CLOSE (có giá tr 0) nên ta s không c p nh t l i giá tr g và f’ c a Arad lưu trong CLOSE. 3 nút còn l i : Fagaras, Oradea, Rimnicu u không có trong c OPEN và CLOSE nên ta s ưa 3 nút này vào OPEN, t cha c a chúng là Sibiu. Như v y, n bư c này OPEN ã ch a t ng c ng 5 thành ph . OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu) 29 Sưu t m b i: www.daihoc.com.vn
(Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu)} CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad)} Trong t p OPEN, nút R.Vilcea là nút có giá tr f’ nh nh t. Ta ch n Tmax  R.Vilcea. Chuy n R.Vilcea t OPEN sang CLOSE. T R.Vilcea có th i n ư c 3 thành ph là Craiova, Pitesti và Sibiu. Ta l n lư t tính giá tr f’, g và h’ c a 3 thành ph này. h’(Sibiu)  253 g(Sibiu)  g(R.Vilcea)+ cost(R.Vilcea,Sibiu)  220+80 300 f’(Sibiu)  g(Sibiu)+h’(Sibiu)  300+253  553 h’(Craiova)  160 g(Craiova)  g(R.Vilcea)+ cost(R.Vilcea, Craiova)  220+146 366 f’(Craiova)  g(Fagaras)+h’(Fagaras)  366+160 526 h’(Pitesti)  98 g(Pitesti)  g(R.Vilcea)+ cost(R.Vilcea, Pitesti)  220+97  317 f’(Pitesti)  g(Oradea)+h’(Oradea)  317+98  415 Sibiu ã có trong t p CLOSE. Tuy nhiên, do g’(Sibiu) m i (có giá tr là 553) l n hơn g’(Sibiu) (có giá tr là 393) nên ta s không c p nh t l i các giá tr c a Sibiu ư c lưu trong CLOSE. Còn l i 2 thành ph là Pitesti và Craiova u không có trong c OPEN và CLOSE nên ta s ưa nó vào OPEN và t cha c a chúng là R.Vilcea. 30 Sưu t m b i: www.daihoc.com.vn
OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu) (Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (Craiova,g 366,h’ 160,f’ 526,Cha R.Vilcea) (Pitesti,g 317,h’ 98,f’ 415,Cha R.Vilcea) } CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad) (R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu) } n ây, trong t p OPEN, nút t t nh t là Pitesti, t Pitesti ta có th i n ư c R.Vilcea, Bucharest và Craiova. L y Pitesti ra kh i OPEN và t nó vào CLOSE. Th c hi n ti p theo tương t như trên, ta s không c p nh t giá tr f’, g c a R.Vilcea và Craiova lưu trong CLOSE. Sau khi tính toán f’, g c a Bucharest, ta s ưa Bucharest vào t p OPEN, t Cha(Bucharest)  Pitesti. h’(Bucharest)  0 g(Bucharest)  g(Pitesti)+cost(Pitesti, Bucharest)  317+100 418 f’(Bucharest)  g(Fagaras)+h’(Fagaras)  417+0 417 31 Sưu t m b i: www.daihoc.com.vn
bư c k ti p, ta s ch n ư c Tmax  Bucharest. Và như v y thu t toán k t thúc (th c ra thì t i bư c này, có hai ng c viên là Bucharest và Fagaras vì u cùng có f’ 417 , nhưng vì Bucharest là ích nên ta s ưu tiên ch n hơn). xây d ng l i con ư ng i t Arad n Bucharest ta l n theo giá tr Cha ư c lưu tr kèm v i f’, g và h’ cho n lúc n Arad. Cha(Bucharest)  Pitesti Cha(R.Vilcea)  Sibiu Cha(Sibiu)  Arad V y con ư ng i ng n nh t t Arad n Bucharest là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest. Trong ví d minh h a này, hàm h’ có ch t lư ng khá t t và c u trúc th khá ơn gi n nên ta g n như i th ng n ích mà ít ph i kh o sát các con ư ng khác. ây là m t trư ng h p ơn gi n, trong trư ng h p này, thu t gi i có dáng d p c a tìm ki m chi u sâu. n ây, minh h a m t trư ng h p ph c t p hơn c a thu t gi i. Ta th s a il i c u trúc th và quan sát ho t ng c a thu t gi i. Gi s ta có thêm m t thành ph t m g i là TP và con ư ng gi a Sibiu và TP có chi u dài 100, con ư ng gi a TP và Pitesti có chi u dài 60. Và kho ng cách ư ng chim bay t TP n Bucharest là 174. Như v y rõ ràng, con ư ng t i ưu n Bucharest không còn là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest n a mà là Arad, Sibiu, TP, Pitesti, Bucharest. Trong trư ng h p này, chúng ta v n ti n hành bư c 1 như trên. Sau khi th c hi n hi n bư c 2 (m r ng Sibiu), chúng ta có cây tìm ki m như hình sau. Lưu ý là có thêm nhánh TP. 32 Sưu t m b i: www.daihoc.com.vn
R.Vilcea v n có giá tr f’ th p nh t. Nên ta m r ng R.Vilcea như trư ng h p u tiên. Bư c k ti p c a trư ng h p ơn gi n là m r ng Pitesti có ư c k t qu . Tuy nhiên, trong trư ng h p này, TP có giá tr f’ th p hơn. Do ó, ta ch n m r ng TP. T TP ta ch có 2 hư ng i, m t quay l i Sibiu và m t n Pitesti. nhanh chóng, ta s không tính toán giá tr c a Sibiu vì bi t ch c nó s l n hơn giá tr ư c lưu tr trong CLOSE (vì i ngư c l i). h’(Pitesti)  98 g(Pitesti)  g(TP)+cost(TP, Pitesti)  240+75 315 f’(Pitesti)  g(TP)+h’(Pitesti)  315+98 413 Pistestti ã xu t hi n trong t p OPEN và g’(Pitesti) m i (có giá tr là 315) th p hơn g’(Pitesti) cũ (có giá tr 317) nên ta ph i c p nh t l i giá tr c a f’,g, Cha c a Pitesti lưu trong OPEN. Sau khi c p nh t xong, t p OPEN và CLOSE s như sau : 33 Sưu t m b i: www.daihoc.com.vn
OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu) (Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (Craiova,g 366,h’ 160,f’ 526,Cha R.Vilcea) (Pitesti,g 315,h’ 98,f’ 413,Cha TP) } CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad) (R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu) } n ây ta th y r ng, ban u thu t gi i ch n ư ng i n Pitesti qua R.Vilcea. Tuy nhiên, sau ó, thu t gi i phát hi n ra con ư ng n Pitesti qua TP là t t hơn nên nó s s d ng con ư ng này. ây chính là trư ng h p 2.b.iii.2 trong thu t gi i. Bư c sau, chúng ta s ch n m r ng Pitesti như bình thư ng. Khi l n ngư c theo thu c tính Cha, ta s có con ư ng t i ưu là Arad, Sibiu, TP, Pitesti, Bucharest. III.9. Bàn lu n v A* n ây, có l b n ã hi u ư c thu t gi i này. Ta có m t vài nh n xét khá thú v v A*. u tiên là vai trò c a g trong vi c giúp chúng ta l a ch n ư ng i. Nó cho chúng ta kh năng l a ch n tr ng thái nào m r ng ti p theo, không ch d a trên vi c tr ng thái ó t t như th nào (th hi n b i giá tr h’) mà còn trên cơ s con ư ng t tr ng thái kh i u n tr ng thái hi n t i ó t t ra sao. i u này s r t h u ích n u ta không ch quan tâm vi c tìm ra l i gi i hay không mà còn quan tâm n hi u qu c a con ư ng d n n l i gi i. Ch ng h n như trong bài toán tìm ư ng i ng n nh t gi a hai i m. Bên c nh vi c tìm ra ư ng i gi a hai i m, ta còn ph i tìm ra m t con ư ng ng n nh t. Tuy nhiên, n u ta ch quan tâm n vi c tìm ư c l i gi i (mà không quan tâm n hi u qu c a con ư ng n l i gi i), chúng ta có th t g=0 m i tr ng thái. i u này s giúp ta luôn ch n i theo tr ng thái có v g n nh t v i tr ng thái k t thúc (vì lúc này f’ ch ph thu c vào h’ là hàm ư c lư ng "kho ng cách" g n nh t t i ích). Lúc này thu t gi i có dáng d p c a tìm ki m chi u sâu theo nguyên lý hư ng ích k t h p v i l n ngư c. Ngư c l i, n u ta mu n tìm ra k t qu v i s bư c ít nh t ( t ư c tr ng thái ích v i s tr ng thái trung gian ít nh t), thì ta t giá tr i t m t tr ng thái n các tr ng thái con k ti p c a nó luôn là h ng s , thư ng là 1 Nghĩa t cost(Ti-1, Ti) = 1 (và v n dùng m t hàm ư c lư ng h’ như bình thư ng). Còn ngư c l i, n u mu n tìm chi phí r nh t thì ta ph i t giá tr hàm cost chính xác (ph n ánh úng ghi phí th c s ). 34 Sưu t m b i: www.daihoc.com.vn
n ây, ch c b n c ã có th b t u c m nh n ư c r ng thu t gi i A* không hoàn toàn là m t thu t gi i t i ưu tuy t i. Nói úng hơn, A* ch là m t thu t gi i linh ng và cho chúng ta khá nhi u tùy ch n. Tùy theo bài toán mà ta s có m t b thông s thích h p cho A* thu t gi i ho t ng hi u qu nh t. i m quan tâm th hai là v giá tr h’ – s ư c lư ng kho ng cách (chi phí) t m t tr ng thái n tr ng thái ích. N u h’ chính là h ( ánh giá tuy t i chính xác) thì A* s i m t m ch t tr ng thái u n tr ng thái k t thúc mà không c n ph i th c hi n b t kỳ m t thao tác i hư ng nào!. Dĩ nhiên, trên th c t , h u như ch ng bao gi ta tìm th y m t ánh giá tuy t i chính xác. Tuy nhiên, i u áng quan tâm ây là h’ ư c ư c lư ng càng g n v i h, quá trình tìm ki m càng ít b sai sót, ít b r vào nh ng nhánh c t hơn. Hay nói ng n g n là càng nhanh chóng tìm th y l i gi i hơn. N u h’ luôn b ng 0 m i tr ng thái (tr v thu t gi i AT) thì quá trình tìm ki m s ư c i u khi n hoàn toàn b i giá tr g. Nghĩa là thu t gi i s ch n i theo nh ng hư ng mà s t n ít chi phí/bư c i nh t (chi phí tính t tr ng thái u tiên n tr ng thái hi n ang xét) b t ch p vi c i theo hư ng ó có kh năng d n n l i gi i hay không. ây chính là hình nh c a nguyên lý tham lam (Greedy). N u chi phí t tr ng thái sang tr ng thái khác luôn là h ng s (dĩ nhiên lúc này h’ luôn b ng 0) thì thu t gi i A* tr thành thu t gi i tìm ki m theo chi u r ng! Lý do là vì t t c nh ng tr ng thái cách tr ng thái kh i u n bư c u có cùng giá tr g và vì th u có cùng f’ và giá tr này s nh hơn t t c các tr ng thái cách tr ng thái kh i u n+1 bư c. Và n u g luôn b ng 0 và h’ cũng luôn b ng 0, m i tr ng thái ang xét u tương ương nhau. Ta ch có th ch n b ng tr ng thái k ti p b ng ng u nhiên ! Còn n u như h’ không th tuy t i chính xác (nghĩa là không b ng úng h) và cũng không luôn b ng 0 thì sao? Có i u gì thú v v cách x lý c a quá trình tìm ki m hay không? Câu tr l i là có. N u như b ng m t cách nào ó, ta có th ch c ch n r ng, ư c lư ng h’ luôn nh hơn h ( i v i m i tr ng thái) thì thu t gi i A* s thư ng tìm ra con ư ng t i ưu (xác nh b i g) i n ích, n u ư ng d n ó t n t i và quá trình tìm ki m s ít khi b sa l y vào nh ng con ư ng quá d . Còn n u vì m t lý do nào ó, ư c lư ng h’ l i l n hơn h thì thu t gi i s d dàng b vư ng vào nh ng hư ng tìm ki m vô ích. Th m chí nó l i có khuynh hư ng tìm ki m nh ng hư ng i vô ích trư c! i u này có th th y m t cách d dàng t vài ví d . Xét trư ng h p ư c trình bày trong hình sau. Gi s r ng t t c các cung u có giá tr 1. G là tr ng thái ích. Kh i u, OPEN ch ch a A, sau ó A ư c m r ng nên B, C, D s ư c ưa vào OPEN (hình v mô t tr ng thái 2 bư c sau ó, khi B và E ã ư c m r ng). i v i m i nút, con s u tiên là giá tr h’, con s k ti p là g. Trong ví d này, nút B có f’ th p nh t là 4 = h’+g = 3 + 1 , vì th nó ư c m r ng trư c tiên. Gi s nó ch có m t nút con ti p theo là E và h’(E) = 3, do E các A hai cung nên g(E) = 2 suy ra f’(E) = 5, gi ng như f’(C). Ta ch n m r ng E k ti p. Gi s nó cũng ch có duy nh t m t con k ti p là F và h’(F) cũng b ng 3. Rõ ràng là chúng ta ang di chuy n xu ng và không phát tri n r ng. Nhưng f’(F) = 6 l n hơn f’(D). Do ó, chúng ta s m r ng C ti p theo và t n tr ng thái ích. Như v y, ta th y r ng do ánh giá th p h(B) nên ta ã lãng phí m t s bư c (E,F), nhưng cu i cùng ta cùng phát hi n ra B khác xa v i i u ta mong i và quay l i th m t ư ng d n khác. 35 Sưu t m b i: www.daihoc.com.vn
Hình : h’ ánh giá th p h Bây gi hãy xét trư ng h p hình ti p theo. Chúng ta cũng m r ng B bư c u tiên và E bư c th hai. K ti p là F và cu i cùng G, cho ư ng d n k t thúc có dài là 4. Nhưng gi s có ư ng d n tr c ti p t D n m t l i gi i có dài h th c s là 2 thì chúng ta s không bao gi tìm ư c ư ng d n này (tuy r ng ta có th tìm th y l i gi i). B i vì vi c ánh giá quá cao h’(D), chúng ta s làm cho D trông d n n i mà ta ph i tìm m t ư ng i khác – n m t l i gi i t hơn - mà không bao gi nghĩ n vi c m r ng D. Nói chung, n u h’ ánh giá cao h thì A* s có th không th tìm ra ư ng d n t i ưu n l i gi i (n u như có nhi u ư ng d n nl i gi i). M t câu h i thú v là "Li u có m t nguyên t c chung nào giúp chúng ta ưa ra m t cách ư c lư ng h’ không bao gi ánh giá cao h hay không?". Câu tr l i là "h u như không", b i vì i v i h u h t các v n th c ta u không bi t h. Tuy nhiên, cách duy nh t b o m h’ không bao gi ánh giá cao h là t h’ b ng 0 ! Hình : h’ ánh giá cao h n ây chúng ta ã k t thúc vi c bàn lu n v thu t gi i A*, m t thu t gi i linh ng, t ng quát, trong ó hàm ch a c tìm ki m chi u sâu, tìm ki m chi u r ng và nh ng nguyên lý Heuristic khác. Chính vì th mà ngư i ta thư ng nói, A* chính là thu t gi i tiêu bi u cho Heuristic. 36 Sưu t m b i: www.daihoc.com.vn
A* r t linh ng nhưng v n g p m t khuy t i m cơ b n – gi ng như chi n lư c tìm ki m chi u r ng – ó là t n khá nhi u b nh lưu l i nh ng tr ng thái ã i qua – n u chúng ta mu n nó ch c ch n tìm th y l i gi i t i ưu. V i nh ng không gian tìm ki m l n nh thì ây không ph i là m t i m áng quan tâm. Tuy nhiên, v i nh ng không gian tìm ki m kh ng l (ch ng h n tìm ư ng i trên m t ma tr n kích thư c c 106 x 106) thì không gian lưu tr là c m t v n hóc búa. Các nhà nghiên c u ã ưa ra khá nhi u các hư ng ti p c n lai gi i quy t v n này. Chúng ta s tìm hi u m t s phương án nhưng quan tr ng nh t, ta c n ph i n m rõ v trí c a A* so v i nh ng thu t gi i khác. 37 Sưu t m b i: www.daihoc.com.vn