›
›

Bài giảng Trí tuệ nhân tạo - Tìm kiếm với thông tin heuristic, A*

pdf 30 trang hapham 1000
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Tìm kiếm với thông tin heuristic, A*", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tri_tue_nhan_tao_tim_kiem_voi_thong_tin_heuristic.pdf

Nội dung text: Bài giảng Trí tuệ nhân tạo - Tìm kiếm với thông tin heuristic, A*

  1. Ref: TRÍ TU NHÂN TO Tìm kim cĩ thơng tin heuristic, A*
  2. Ni dung trình bày 2  Tìm kim cĩ thơng tin heuristic tt nht  Nhng đim khơng thích hp ca tìm kim tt nht  Mo: tính luơn chi phí đi đn trng thái hin ti.  Vic tìm kim kt thúc khi nào?  Heuristic chp nhn đưc  Tìm kim A* là đy đ  Tìm kim A* luơn dng  Khuyt đim ca A*  Tit kim nhiu b nh vi IDA* (Iterative Deepening A*)
  3. Tìm kim vi thơng tin heuristic 3 Các phương pháp tìm kim mù (blind search): thơng tin v trng thái đích khơng đĩng vai trị trong vic tìm kim. S Nên đi đưng nào? a b c G Cĩ th s dng ưc lưng khong cách đn đích gia các trng thái đ tìm đưng đi?
  4. Tìm kim vi thơng tin heuristic (tt) 4 Gi s ngồi vic đc t tìm kim chun ta cũng cĩ mt heuristic . Mt hàm heuristic ánh x mt trng thái thành mt ưc lưng v chi phí đn đích t trng thái đĩ. Bn cĩ th nghĩ ra ví d v heuristics? VD. đi vi bài tốn 8puzzle? VD. đ lp đưng đi trong ma trn? Ký hiu heuristic bng mt hàm h(s)
  5. Heuristic theo Khong cách Euclide 5 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9
  6. Tìm kim vi thơng tin heuristic tt nht (Bestfirst) 6 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9
  7. Tìm kim tt nht (tt) 7 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9 PQ = {(Start,12)}
  8. Tìm kim tt nht (tt) 8 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9 PQ = {(e,4),(d,8),(p,11)}
  9. Tìm kim tt nht (tt) 9 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9 PQ = {(h,6),(r,6),(d,8),(p,11)}
  10. Tìm kim tt nht (tt) 10 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9 PQ = {(r,6),(d,8),(q,9),(p,11)}
  11. Heuristic trong bài tốn 8puzzle 11  Theo s ơ nm sai v trí 1 5 1 2 3 2 6 3 h = 6 4 5 6 7 4 8 7 8
  12. Heuristic trong bài tốn 8puzzle (tt) 12  Theo tng khong cách Manhattan 1 5 1 2 3 2 6 3 h = 9 4 5 6 7 4 8 7 8 d = dx + dy h = 0 + 2 + 1 + 2 + 2 + 1 +0 + 1 = 9
  13. Thut tốn tìm kim tt nht 13 InitPriQueue(PQ) InsertPriQueue(PQ,START,h(START)) while (PQ khác rng và PQ khơng cha trng thái đích) (s , h ) := Popleast(PQ) Vi mi s’ trong succs(s) Nu s’ khơng cĩ trong PQ và s’ chưa đưc ving trưc đĩ bao gi InsertPriQueue(PQ,s’,h(s’)) Thut tốn ð Ti ưu Thi gian Khơng gian BestFS Best First C K LMAX LMAX Search O(min(N,B )) O( min (N,B )) Mt vài ci tin ca thut tốn này cĩ th làm cho mi vic tt đp hơn. Nĩ là th mà chúng ta gi là: A* . * Vic s dng heuristic làm thay đi B
  14. Hãy Xem “tt nht” ng ngn th nào! 14 4 2 11 2 S A B C G h=4 h=3 h=2 h=1 h=0  Tìm kim tt nht rõ ràng khơng đm bo tìm thy đưng đi ti ưu  Câu hi: Chúng ta cĩ th làm gì đ tránh li ng ngn này?
  15. A* Ý tưng Cơ bn 15  Bestfirst: Khi bn m mt node n, ly node con n' và đt nĩ vào PriQueue vi đ ưu tiên h(n' )  A* : Khi bn m mt node n, ly node con n' và đt nĩ vào PriQueue vi đ ưu tiên (Chi phí đi đn n' ) + h(n' ) (1) ðt g(n) = Chi phí đi đn n (2) và đnh nghĩa f(n) = g(n) + h(n) (3)
  16. A* khơng ng ngn! 16 4 2 11 2 S A B C G h=4 h=3 h=2 h=1 h=0
  17. A* dng khi nào? 17 Ý tưng: Ngay khi nĩ phát sinh đưc trng thái đích? Xem ví d sau: 1 1 S h = 3 B 1 h = 7 h = 8 A h = 2 C 7 1 D h = 1 7 G h = 0
  18. Quy tc Dng A* ðúng ðn: 18 A* Dng Ch Khi mt Trng Thái ðích ðưc Ly ra khi Priority Queue 1 1 S h = 3 B 1 h = 7 h = 8 A h = 2 C 7 1 D h = 1 7 G h = 0
  19. Các trng thái quay li A* 19 Mt câu hi khác: ðiu gì xy ra nu A* quay li mt trng thái đã m, và tìm đưc mt đưng ngn hơn? 1 1 S h = 3 B 1 h = 8 A h = 7 C h = 2 1/2 1 D h = 1 Trong ví d này mt trng thái đã m đưc m li. 7 Như th nào và ti sao ? G
  20. Các trng thái quay li A* 20 ðiu gì nu A* thăm mt trng thái đã cĩ trong hàng đi ? h = 8 1 1 S h = 3 B 1 A h = 7 C h = 8 1/2 1 D h = 1 Trong ví d này mt trng thái đã cĩ trong hàng đi và đang đi m 7 lưu ý rng giá tr cĩ đ ưu tiên tăng vt lên. Như G h này đã thay th nào và ti sao? đi so vi trang trưc.
  21. Thut tốn A* 21  Priority queue PQ ban đu rng.  V (= tp các (b ba ( state,f ,backpointer )) đã thăm trưc đĩ bt đu là rng.  ðt S vào PQ và V vi đ ưu tiên f(s) = g(s) + h(s)  PQ rng?  Cĩ? Khơng cĩ li gii.  Khơng? Loi b node vi f(n) thp nht khi queue. Gi nĩ là n.  Nu n là mt đích, dng và báo thành cơng.  “M” n : Vi mi n' trong succs (n)  ðt f’ = g(n' ) + h(n' ) = g(n) + cost (n,n' ) + h(n' )  Nu n' chưa thy trưc đĩ, hay n' đã m vi f(n' )> f’ , hay n' hin trong PQ vi f(n' )> f’  Thì ðt/Cp nht n' trong PQ vi đ ưu tiên f’ và cp nht V đ bao gm ( state =n' , f ’, BackPtr =n).  Ngưc li b qua n'
  22. A* Cĩ Bo đm Tìm thy ðưng đi Ti ưu? 22 1 A 1 h = 6 h = 0 S h = 7 G 3 Khơng. Và ví d sau cho thy ti sao.
  23. Heuristic chp nhn đưc 23  ðt h*( n) = chi phí ti thiu thp nht t n đn đích.  Mt heuristic h là chp nhn đưc nu h(n) <= h*( n) vi mi trng thái n.  Mt heuristic chp nhn đưc đm bo khơng bao gi ưc tính quá chi phí đn đích.  Mt heuristic chp nhn đưc là ti ưu.
  24. Ví d 8Puzzle 24 Trng thái 1 5 Trng thái 1 2 3 đích ví d 2 6 3 4 5 6 7 4 8 7 8 Heuristics nào sau đây là chp nhn đưc? • h(n) = S ơ nm sai v trí trong trng thái n • h(n) = 0 • h(n) = min (2, h*( n)) • h(n) = Tng khong cách • h(n) = h*(n ) Manhattan gia mi ơ so vi v trí • h(n) = max (2, đích h*( n)) • h(n) = 1
  25. A* vi heuristic chp nhn đưc bo đm đưng đi ti ưu 25  Chng minh đơn gin  (Bn cĩ th t chng minh ?)
  26. So sánh Lp Sâu dn vi A* 26 Trong sách ca Russell and Norvig, trang 107, Hình4.8 Vi 8puzzle, s trng thái đưc m trung bình trong 100 bài tốn đưc chn ngu nhiên trong đĩ đưng đi ti ưu dài 4 bưc 8 bưc 12 bưc Lp Sâu dn 112 6,300 3.6 x 10 6 Tìm kim A* dùng “s ơ sai v 13 39 227 trí” làm heuristic A* dùng “Tng khong cách 12 25 73 Manhattan” làm heuristic
  27. A* : Khuyt đim 27  A* cĩ th dùng nhiu b nh. Trên lý thuyt: O(s trng thái)  Vi khơng gian tìm kim thc s ln, A* s dùng ht b nh.
  28. IDA* : Tìm kim Vi B nh Gii hn 28  A* lp vi đ sâu tăng dn. Tht s, rt khác so vi A*. Gi s chi phí là s nguyên. 1. Thc hin lpkhơng dùng DFS, khơng m rng node nào cĩ f(n) > 0. Cĩ tìm thy đích? Nu cĩ, dng. 2. Thc hin lpkhơng dùng DFS, khơng m rng node nào cĩ f(n) > 1. Cĩ tìm thy đích? Nu cĩ, dng. 3. Thc hin lp khơng dùng DFS, khơng m rng node nào cĩ f(n) > 2. Cĩ tìm thy đích? Nu cĩ, dng. 4. Thc hin lpkhơng dùng DFS, khơng m rng node nào cĩ f(n) > 3. Cĩ tìm thy đích? Nu cĩ, dng. lp li điu này, tăng ngưng f(n) lên mt 1 mi ln, cho đn khi dng.  Cái này  ðy đ  Bo đm tìm đưc li gii ti ưu  Nĩi chung tn chi phí nhiu hơn A*.
  29. ðiu cn nm 29  Hiu thu đáo A*.  Cĩ th chy tay các ví d thc thi A* đơn gin.  Hiu đưc “tính chp nhn đưc” ca heuristics. Chng minh tính đy đ, bo đm tính ti ưu ca đưng đi.  Cĩ th nhn xét v các đánh giá.
  30. Thc mc 30