›

Bài giảng Trí Tuệ Nhân Tạo - Chương 3: Các chiến lược tìm kiếm Heuristics - Nguyễn Văn Hòa

pdf 43 trang huongle 2070
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 - Chương 3: Các chiến lược tìm kiếm Heuristics - Nguyễn Văn Hò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_chuong_3_cac_chien_luoc_tim_kiem.pdf

Nội dung text: Bài giảng Trí Tuệ Nhân Tạo - Chương 3: Các chiến lược tìm kiếm Heuristics - Nguyễn Văn Hòa

  1. Ch ươ ng 3: Các chi n l ư c tìm ki m Heuristics 1
  2. Ni dung  Khái ni ệm  Tìm ki ếm t ốt nh ất tr ướ c  Ph ươ ng pháp leo đồ i  Cài đặ t hàm đánh giá  Thu gi ảm ràng bu ộc  Gi ải thu ật c ắt t ỉa α-β 2
  3. Gi i h n không gian h th ng  8-puzzle  Lời gi ải c ần trung bình 22 cấp (depth)  Độ r ộng c ủa b ướ c ~ 3  Tìm ki ếm vét c ạn cho 22 c ấp c ần  3.1 x 10 10 states  Nếu ch ỉ gi ới h ạn ở d=12, c ần trung bình 3.6 tri ệu tr ạng thái [24 puzzle có 10 24 tr ạng thái]  ⇒ Cần chi ến l ượ c tìm ki ếm heuristic 3
  4. Tìm ki m Heuristics  Any estimate of how close a state is to a goal  Designed for a particular search problem  Examples: Manhattan distance, Euclidean distance 10 5 11.2
  5. Tìm ki m Heuristic (tt)  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. 5
  6. Tìm ki m Heuristic (tt)  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: 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, giúp 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.  Gi ải thu ật tìm ki ếm heuristic:  Gi ải thu ật leo núi (hill-climbing)  Greedy, TK t ốt nh ất (best-first search)  A* search, 6
  7. Ví d phép đo Heuristics 7
  8. Ví d phép đo Heuristics (tt) Heuristic “Số đườ ng th ắng nhi ều nh ất” ( theo các đườ ng chéo trên bàn c ờ) áp d ụng cho các con c ờ đầ u tên đặ t vào bàn c ờ trong bàn c ờ tic-tac-toe 8
  9. Ví d phép đo Heuristics (tt) 9
  10. Tìm ki m leo đ i – Hill Climbing Search (Pearl, 1984)  Ch ọn m ột tr ạng thái t ốt h ơn tr ạng thái đang kh ảo sát để phát tri ển. N ếu không có thu ật tóan ph ải dừng.  Nếu ch ỉ ch ọn m ột tr ạng thái t ốt h ơn: leo đồ i đơ n gi ản, tr ạng thái t ốt nh ất: leo đồ i d ốc đứ ng.  Sử d ụng hàm H để bi ết tr ạng thái nào t ốt h ơn.  Khác v ới tìm ki ếm sâu, leo đồ i không l ưu t ất c ả các con mà ch ỉ l ưu đúng m ột tr ạng thái đượ c ch ọn nếu có. 10
  11. Tìm ki m leo đ i (tt)  Gi ải thu ật  Xét tr ạng thái b ắt đầ u  Nếu là đích ⇒ dừng  Ng ượ c l ại: thi ết l ập kh ởi đầ u nh ư TT hi ện t ại  Lặp đế n khi: g ặp đích ho ặc không còn lu ật nào ch ưa đượ c áp d ụng vào TT hi ện t ại  Lựa m ột lu ật để áp d ụng vào TT hi ện t ại để sinh ra m ột TT m ới  Xem xét TT m ới này  Nếu là đích ⇒ dừng  Nếu không là đích, nh ưng t ốt h ơn TT hi ện t ại ⇒ thi ết lập TT m ới là TT hi ện t ại  Nếu không t ốt h ơn thì l ặp ti ếp t ục 11
  12. Tìm ki m leo đ i (tt)  Hi ệu qu ả n ếu có đượ c hàm (H) đánh giá t ốt  Gi ới h ạn  Có khuynh h ướ ng b ị sa l ầy ở nh ững c ực đạ i c ục b ộ  Lời gi ải tìm đượ c không t ối ưu  Không tìm đượ c l ời gi ải m ặc dù có t ồn t ại l ời gi ải  Có th ể g ặp vòng l ặp vô h ạn do không l ưu gi ữ thông tin về các tr ạng thái đã duy ệt 12
  13. Tìm ki m leo đ i (tt)  Bài toán 8 H ậu  Tr ạng thái b ắt đầ u: m ỗi H ậu trên 1 c ột  Tr ạng thái đích: các H ậu không th ể t ấn công nhau  Phép đo Heuristic h(n) : s ố l ượ ng các c ập h ậu đố i kháng nhau H(n) = 17 h(n) = 1 13
  14. Tìm ki m t t nh t (BFS)  Là ph ươ ng pháp dung hoà c ủa BrFS và DFS  Có s ử d ụng để đánh giá ưu th ế c ủa m ỗi tr ạng thái, có th ể là ướ c l ượ ng t ừ nó đế n TT đích  Tại m ỗi b ướ c, gi ải thu ật s ẽ ch ọn tr ạng thái mà nó cho rằng là có ưu th ế nh ất trong s ố các tr ạng thái đã sinh ra đượ c đế n th ời điểm đó  Khác v ới gi ải thu ật leo đồ i có c ải ti ến ở ch ổ: có l ưu t ất c ả nh ững TT đã phát sinh đế n th ời điểm ch ọn TT để xét ti ếp  Dùng hai danh sách:  OPEN: ch ứa các TT s ẽ đượ c xét.  CLOSED: ch ứa các TT đã xét qua. 14
  15. Tìm ki m t t nh t (BFS)  Gi ải thu ật  OPEN = [TT đầ u]  Lặp đế n khi: g ặp đích ho ặc OPEN r ỗng  Lấy TT t ốt nh ất t ừ OPEN  Phát sinh các con c ủa nó  Với m ỗi con:  Nếu nó ch ưa đượ c phát sinh: gán nó tr ị đánh giá, đư a vào OPEN, ghi nh ận TT cha c ủa nó  Nếu đã đượ c phát sinh tr ướ c: N ếu đạ t đế n b ởi đườ ng khác t ốt h ơn ⇒ ghi nh ận l ại TT cha c ủa nó, c ập nh ật l ại tr ị đánh giá c ủa nó và của các con c ủa nó 15
  16. Tìm ki m t t nh t (BFS) Open là queue, x p theo 1. open = [A5]; closed = [ ] Heuristic t ăng d n 2. Đánh giá A5; open = [B4,C4,D6]; closed = [A5] 3. Đánh giá B4; open = [C4,E5,F5,D6]; closed = [B4,A5] 4. Đánh giá C4; open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5] 5. Đánh giá H3; open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5] 6. Đánh giá O2; open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] 7. Đánh giá P3; tìm đượ c l ời gi ải! 16
  17. Cài đ t hàm đánh giá (EF)  Xét trò ch ơi 8-ô, m ỗi tr ạng thái n, m ột giá tr ị f(n): f(n) = g(n) + h(n)  g(n) = kho ảng cách th ực s ự t ừ n đế n tr ạng thái b ắt đầ u  h(n) = hàm heuristic đánh giá kho ảng cách t ừ tr ạng thái n đế n m ục tiêu. start 2 8 3 1 2 3 g(n) = 0 1 6 4 8 4 7 5 7 6 5 goal 2 8 3 2 8 3 2 8 3 h(n): s ố l ượ ng các v ị trí còn sai; g(n) = 1 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 f(n) = 6 4 6 17
  18. Ví d 18
  19. Ví d 19
  20. Ví d 20
  21. Gi i thu t A*  A* là gi ải thu ật t ổng quát h ơn BestFS, nó tìm ki ếm trên KGTT là đồ th ị.  Vì là đồ th ị nên phát sinh nhi ều v ấn đề khi tìm đườ ng đi t ối ưu.  Để ý r ằng nghi ệm là đườ ng đi nên ta ph ải l ưu l ại vết c ủa đườ ng đi này.  Trong các gi ải thu ật tr ướ c, để t ập trung cho t ư tưở ng chính c ủa các gi ải thu ật đó chúng ta b ỏ qua chi ti ết này, nh ưng trong gi ải thu ật này chi ti ết này đượ c đề c ập vì nó liên quan đế n nghi ệm m ột cách tr ực ti ếp. 21
  22. Thông tin m i nút  Mỗi tr ạng thái u tùy ý s ẽ g ồm b ốn y ếu t ố (g(n), h(n), f(n), cha(n)). Trong đó:  G(n), h(n), f(n) đã bi ết  Cha(n) là nút cha c ủa nút đang xét n 22
  23. A* Search Progress source: wikipedia page for A* Algorithm; by Subh83
  24. Mô t ho t đ ng c a A* 24
  25. Lưu các tr ng thái Bướ c Open closed 1 A(0,7,0,-) 2 B(3,3,6,A), D(1,6,7,A), C(5,4,9,A) A(0,7,0,-) 3 D(1,6,7,A), C(4,4,8,B) B(3,3,6,A) 4 B(2,3,5,D), C(4,4,8,B) D(1,6,7,A) 5 C(3,4,7,B) B(2,3,5,D) 6 G(5,0,5,C) C(3,4,7,B) Gi ải thu ật d ừng ở b ướ c 6 và đườ ng đi thu đượ c độ dài 5 nh ư sau A-D-B-C-G. 25
  26. Chi ti t các b ư c  Ở b ướ c 2, m ọi vi ệc x ảy ra bình th ườ ng  Ở b ướ c 3, tìm đượ c đườ ng đi đế n C qua B ng ắn h ơn nên các giá tr ị c ủa C trong open ph ải đượ c s ửa đổ i.  Ở b ướ c 4, m ặc dù B đã n ằm trong closed, t ức đã xét xong nh ưng đườ ng đi m ới qua D đế n B ng ắn h ơn nên B ph ải đượ c l ấy kh ỏi closed chuy ển qua open ch ờ xét lại v ới giá tr ị m ới.  Ở b ướ c 5, l ại x ảy ra vi ệc ch ỉnh s ửa các giá tr ị c ủa C nh ư ở b ướ c 3.  Gi ải thu ật d ừng ở b ướ c 6 và đườ ng đi thu đượ c độ dài 5 nh ư sau A-D-B-C-G. 26
  27. Mã gi gi i thu t A* g(n o)=0; f(n o)=h(n o); open:=[n o]; closed:=[]; while open<>[] do lo ại n bên trái c ủa open và d ưa n vào closed; if (n là m ột đích) then thành công, thoát else Sinh các con m c ủa n; For m thu ộc con(n) do g(m):=g(n)+c[n,m]; If m không thu ộc open hay closed f(m):=g(m)+h(m); cha(m):=n; B ỏ m vào open; If m thu ộc open (t ồn t ại m’ thu ộc open, sao cho m=m’) If g(m)<g(m’) then g(m’):=g(m); f(m’):=g(m’)+h(m’); Cha(m’):=n; If m thu ộc closed (t ồn t ại m’ thu ộc closed, sao cho m=m’) If g(m)<g(m’) then f(m):=g(m)+h(m); cha(m):=n; Đư a n vào open; Lo ại n’ kh ỏi closed; Xếp open để t.thái t ốt nh ất n ằm bên trái; 27
  28. Đánh giá gi i thu t A*  Một hàm đánh giá h(n) đượ c g ọi là ch ấp nh ận đượ c hay là hàm đánh giá th ấp n ếu nh ư h(n)<=h*(n) v ới m ọi n, ở đây h*(n) là đườ ng đi ng ắn nh ất t ừ n đế n đích.  Nếu hàm đánh giá h(n) là ch ấp nh ận đượ c thì thu ật toán A* là t ối ưu.  A* là thu ật tóan hi ệu qu ả nh ất trong các thu ật toán đầ y đủ và t ối ưu. 29
  29. Chi n l ư c tìm ki m có đ i th  Đặ c điểm  Hai ng ườ i thay phiên đi (xen k ẽ)  Hai ng ườ i bi ết thông tin đầ y đủ v ề nhau  Mỗi ng ườ i tìm ki ếm n ướ c đi  Nướ c đi t ốt nh ất là n ướ c đi d ẫn đế n ph ần th ắng.  Bi ểu di ễn KGTT b ằng cây: cây trò ch ơi.  Gi ải thu ật tiêu bi ểu: MiniMax 30
  30. Th t c Minimax c ơ b n  Ví d ụ: trò ch ơi Nim  Có n (n>2) đồ ng xu.  Mỗi n ướ c đi, ng ườ i ch ơi chia các đồ ng xu này thành hai đố ng nh ỏ có s ố l ượ ng m ỗi đố ng khác nhau.  Ng ườ i thua s ẽ là ng ườ i cu ối cùng không chia đượ c theo yêu c ầu c ủa bài toán.  Phân tích  Tính toán ph ản ứng c ủa đố i th ủ là khó kh ăn ch ủ y ếu của bài toán này  Cách gi ải quy ết là gi ả thi ết đố i th ủ c ũng s ử d ụng ki ến th ức v ề không gian tr ạng thái 31
  31. Trò Ch ơi NIM: giá tr t i các nút 1 MIN 1 MAX 1 1 MIN 0 1 0 1 MAX 0 1 0 KT QU C A MIN 0 1 MAX MAX 0 KT QU C A MIN 32
  32. Trò Ch ơi NIM  Hai đấ u th ủ: MIN và MAX.  Trong đó MAX luôn tìm cách t ối đa ưu th ế c ủa mình và MIN tìm m ọi cách để đư a MAX vào th ế khó kh ăn nh ất.  Mỗi m ức trên KGTT ứng v ới m ột đấ u th ủ.  Để ch ỉ d ẫn đượ c cách đi, chúng ta s ẽ gán cho các nút lá là 1 n ếu MAX th ắng, là 0 n ếu MIN th ắng.  Gán giá tr ị cho các nút  Truy ền ng ượ c các tr ị t ừ các nút lá v ề g ốc theo qui t ắc:  Nếu đỉ nh ở m ức MAX, gán tr ị cho đỉ nh này b ằng giá tr ị lớn nh ất trong các giá tr ị c ủa các con c ủa nó  Nếu đỉ nh ở m ức MIN, gán tr ị cho đỉ nh này b ằng giá tr ị bé nh ất trong các tr ị c ủa các con c ủa nó. 33
  33. Minimax v i đ sâu l p c đ nh  Minimax đố i v ới m ột KGTT gi ả đị nh 3 là giá tr max ca các nút con 2 là giá tr min ca các nút con Các nút lá đượ c gán các giá tr ị heuristic nào đó Còn giá tr ị t ại các nút trong là các giá tr ị nh ận đượ c d ựa trên (min hay max cua các nút con) gi ải thu ật Minimax 34
  34. Heuristic trong trò ch ơi tic-tac-toe Hàm Heuristic : E(n) = M(n) – O(n) Trong đó: M(n) là tổng s ố đườ ng th ẳng có th ể c ủa tôi O(n) là tổng s ố đườ ng th ẳng có th ể c ủa đố i th ủ E(n) là tr ị s ố đánh giá t ổng c ộng cho tr ạng thái n 35
  35. Gi i thu t c t nhánh alpha-beta  Hạn ch ế v ới s ố m ức d đi n ữa thì s ố tr ạng thái đã rất l ớn.  Cờ vua: nhân t ố nhánh b=35; d=3 có 35*35*35=42.785 tr ạng thái  Gi ảm b ớt các tr ạng thái c ần kh ảo sát mà v ẫn không ảnh h ưở ng gì đế n vi ệc gi ải quy ết bài toán.  Cắt b ỏ các nhánh không c ần kh ảo sát. 36
  36. Gi i thu t c t nhánh alpha-beta  Tìm ki ếm theo ki ểu depth-first.  Nút MAX có 1 giá tr ị α (luôn t ăng)  Nút MIN có 1 giá tr ị β (luôn gi ảm)  Tìm ki ếm có th ể k ết thúc d ướ i b ất k ỳ:  Nút MIN nào có βββ≤≤≤ ααα của b ất k ỳ nút cha MAX nào.  Nút MAX nào có ααα ≥≥≥ βββ của b ất k ỳ nút cha MIN nào.  Gi ải thu ật c ắt t ỉa α-β th ể hi ện mối quan h ệ gi ữa các nút ở l ớp n và n+2 , mà t ại đó toàn b ộ cây có gốc t ại l ớp n+1 có th ể c ắt b ỏ. 37
  37. Ct nhánh α (v trí MAX) ααα MAX S Có giá tr >= Có giá A Có giá tr giá tr B Điu ki n 3: X, Y, , Z v trí Max B nh ng cây con có g c là X,Y, , Z 38
  38. Ct nhánh β (v trí Min) MIN S Có giá tr = k βββ - cut Có MIN B giá tr X Y . Z = k Điu ki n 1: Ch c n bi t giá tr t i A và B Điu ki n 2: Giá tr A < giá tr B Điu ki n 3: X, Y, , Z v trí Min B nh ng cây con có g c là X,Y, , Z 39
  39. Ct nhánh α-β: ví d 40
  40. Bài t p: bài 1 ( trò đ 8 ô nh ư) Start Goal 1 2 3 1 2 3 6 7 8 4 8 5 4 7 6 5 Dùng các hàm l ượ ng giá heuristic sau  h1 = s ố l ượ ng các v ị trí sai khác so v ới tr ạng thái goal.  h2 = t ổng s ố độ d ời ng ắn nh ất c ủa các ô v ề v ị trí đúng (kho ảng cách Manhattan) Hãy tri ển khai không gian tr ạng thái c ủa bài toán đế n m ức 5 (n ếu ch ưa tìm đượ c goal): a) Theo gi ải thu ật leo núi b) Theo gi ải thu ật tìm ki ếm r ộng c) Theo gi ải thu ật tìm ki ếm sâu d) Theo gi ải thu ật tìm ki ếm t ốt nh ất đầ u tiên 41
  41. Bài t p: bài 2 (duy t đ th ) Trong cây tìm ki ếm d ướ i đây, m ỗi nút có 2 giá tr ị đi kèm: giá tr ị bên trái c ủa nút (in nghiêng) th ể hi ện giá tr ị heuristic c ủa nút, và giá tr ị bên ph ải nút th ể hi ện th ứ t ự nút đượ c duy ệt qua. V ới m ỗi chi ến l ượ c tìm ki ếm d ướ i đây, hãy vi ết danh sách th ứ t ự các nút đượ c duy ệt, so sánh và cho bi ết ta đã dùng gi ải thu ật tìm ki ếm nào trên cây : a) Tìm ki ếm r ộng BrFS b) Tìm ki ếm sâu DFS c) Tìm ki ếm t ốt nh ất đầ u tiên BFS d) Tìm ki ếm leo núi f) A* 42
  42. Bài t p: bài 3 (minimax) Li ệt kê danh sách các nút đượ c duy ệt theo tìm ki ếm DFS.  Th ực hi ện gi ải thu ật Minimax trên cây.  Sẽ có gì khác bi ệt nếu nh ư ta dùng gi ải thu ật cắt tỉa alpha – beta để đị nh tr ị nút gốc cho cây? 43