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

0
69
lượt xem
21
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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
  2. (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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
Đồng bộ tài khoản