Bài giảng Các hệ thống thông minh nhân tạo & ứng dụng - Bài toán tìm kiếm I - Bùi Thị Danh

Nội dung text: Bài giảng Các hệ thống thông minh nhân tạo & ứng dụng - Bài toán tìm kiếm I - Bùi Thị Danh

1. CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG Bài toán tìm kiếm I THS. BÙI THỊ DANH BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
2. Nội dung chính Tổng quan bài toán tìm kiếm Cây tìm kiếm Các thuật toán tìm kiếm mù 2
3. Bài toán tìm kiếm Bài toán tìm đường đi ◦ Tìm đường ngắn nhất, ◦ Tìm đường nhanh nhất ◦ Tìm đường có nhiều cảnh đẹp nhất Các hành động: ◦ Đi thẳng ◦ Rẽ trái ◦ Rẽ phải 3
4. Bài toán tìm kiếm Giải bài toán puzzle ◦ Tìm cách đạt đến “cấu hình” xác định Các hành động: ◦ Di chuyển các miếng ghép 4
5. Bài toán tìm kiếm Một bài toán tìm kiếm gồm 5 thành phần: ◦ Không gian trạng thái: S ◦ Tập các hành động: Action(s) ◦ Trạng thái bắt đầu: start ◦ Hàm kiểm tra trạng thái đích: IsGoal(s) ◦ Hàm xác định trạng thái kế tiếp: Successor(s) ◦ Thường đi kèm với hành động và chi phí tương ứng Một lời giải của bài toán tìm kiếm là một chuỗi các hành động để di chuyển từ trạng thái bắt đầu đến trạng thái đích. 5
6. Không gian trạng thái Trạng thái (state) là tập các chi tiết / thông tin cần thiết cho việc ra quyết định. Không gian trạng thái là tập tất cả các trạng thái có thể có. Kích thước của không gian trạng thái, được tính như sau: ◦ Mỗi trạng thái có N chi tiết ◦ Mỗi chi tiết có miền giá trị là 푖 ◦ Kích thước của không gian trạng thái: 푆 = 1 × 2 × ⋯ × 6
7. Bài toán tìm đường đi Trạng thái: (tên địa điểm) S : {tất cả các địa điểm trên bản đồ} Start : điểm xuất phát IsGoal(s): Có phải điểm muốn đến không? Successor(s): các trạng thái có thể đi đến được từ s. Câu hỏi: Kích thước không gian trạng thái là bao nhiêu? 7
8. Bài toán tìm đường đi Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn. ◦ Không được viếng thăm quá 2 thành phố lẻ Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán? ◦ Trạng thái: (thành phố hiện tại, thành phố trước là lẻ?(true/false)) ◦ Actions(s): đi từ thành phố sang thành phố khác ◦ IsGoal(s): s có phải là thành phố n không? ◦ Successor(s): các trạng thái s’(Thành_phố, Là_lẻ). Trong đó, ◦ Thành_phố: chỉ số của thành phố đi đến được, tức ℎà푛ℎ_ ℎố ≥ 푠 ◦ Là_lẻ: true nếu s là thành phố lẻ hoặc chi tiết s.Là_lẻ là true. 8
9. Bài toán tìm đường đi Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn. ◦ Cần viếng thăm ít nhất 3 thành phố lẻ Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán? 9
10. Bài toán tìm đường đi Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn. ◦ Cần viếng thăm số thành phố lẻ nhiều hơn số thành phố chẵn. Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán? 10
11. Bài toán Puzzle Câu hỏi: Cho biết trạng thái gồm các chi tiết gì? Liệt kê các thành phần của bài toán? 11
12. Nội dung chính Tổng quan bài toán tìm kiếm Cây tìm kiếm Các thuật toán tìm kiếm mù 12
13. Đồ thị trạng thái Đồ thị trạng thái (state graph): một cách biểu diễn hình học cho bài toán tìm kiếm. ◦ Mỗi đỉnh đồ thị tương ứng với một trạng thái ◦ Mỗi cạnh đồ thị nối trạng thái với một trạng thái kế của nó. ◦ Hàm kiểm tra trạng thái đích chính là tập các đỉnh tương ứng với trạng thái đích Trong đồ thị trạng thái, mỗi trạng thái chỉ xuất hiện duy nhất một lần Thường không xây dựng đồ thị trạng thái đầy đủ trên bộ nhớ máy tính vì rất lớn. 13
14. Đồ thị trạng thái 14
15. Cây tìm kiếm Cây tìm kiếm (search tree) là cấu trúc cây thể hiện các hành động và kết quả tương ứng của hành động. ◦ Node gốc tương ứng với trạng thái bắt đầu ◦ Các node con tương ứng với trạng thái kế tiếp của node cha. ◦ Node lá tương ứng với trạng thái đích ◦ Mỗi lời giải tương ứng với một đường đi từ gốc đến node lá Mỗi trạng thái có thể xuất hiện nhiều hơn 1 lần. Thường không xây dựng đầy đủ cây tìm kiếm trong bộ nhớ vì rất lớn 15
16. Đồ thị trạng thái vs Cây tìm kiếm 16
17. Câu hỏi Giả sử trạng thái bắt đầu là Faragas, hãy vẽ cây tìm kiếm cho đồ thị trạng thái dưới đây? Eforie Pitesti Vaslui Sibiu Craiova Arad Faragas Lugoj Zerind Oradea 17
18. Cây tìm kiếm Câu hỏi: có bao nhiêu node trên cây tìm kiếm tương ứng với đồ thị trạng thái sau? 18
19. Thuật toán tìm kiếm trên cây Input: problem – các thành phần của bài toán tìm kiếm strategy – chiến lược duyệt Output: solution – nếu tồn tại lời giải; failure – nếu ngược lại Khởi tạo cây tìm kiếm với trạng thái bắt đầu của problem Loop If không còn ứng viên để mở rộng then return “không có lời giải” Chọn một node lá để mở rộng dựa theo strategy If node được chọn là trạng thái đích then return “có lời giải” else mở rộng node và thêm các node kết quả vào cây tìm kiếm End 19
20. Thuật toán tìm kiếm trên cây Mở rộng dần các trạng thái tiềm năng Cần cấu trúc dữ liệu hợp lý để đảm bảo thứ tự các trạng thái được xem xét, tạm gọi là Fringe Cố gắng mở rộng ít trạng thái nhất có thể. 20
21. Các thuộc tính của thuật toán tìm kiếm Đầy đủ (complete): đảm bảo tìm thấy lời giải nếu thực sự tồn tại lời giải? Tối ưu (optimal): Đảm bảo tìm thấy đường đi có chi phí thấp nhất? Độ phức tạp tính toán (time complexity) Độ phức tạp không gian lưu trữ (space complexity) Giả sử: ◦ Số nhánh rẽ ở mỗi node là b ◦ Độ sâu tối đa của cây là m ◦ Các lời giải nằm ở các độ sâu khác nhau Khi đó, số lượng node trên cả cây là: 1 b2 bm O(bm ) 21
22. Nội dung chính Tổng quan bài toán tìm kiếm Cây tìm kiếm Các thuật toán tìm kiếm mù 22
23. Các thuật toán tìm kiếm mù Tìm kiếm theo chiều rộng (Breath-First Search) Tìm kiếm theo chiều sâu (Depth-First Search) Tìm kiếm với lặp sâu dần (Iterative Deepening) Tìm kiếm với chi phí đồng nhất (Uniform Cost Search) 23
24. Tìm kiếm theo chiều rộng (BFS) Chiến lược duyệt: mở rộng ở trạng thái cạn nhất trước Sử dụng hàng đợi để triển khai Tùy chọn: Đánh dấu các trạng thái đã xem xét ◦ Đánh dấu khi trạng thái được bỏ vào hàng đợi 24
25. Ví dụ a Goal b c d e f Start h p q r S = null, Q={Start} 25
26. Ví dụ Goal a b c d e f Start h p q r S = start; Q={d, e, p} 26
27. Ví dụ Goal a b c d e f Start h p q r S = d; Q={e, p, b, c} 27
28. Ví dụ Goal a b c d e f Start h p q r S = e; Q={p, b, c, h, r} 28
29. Ví dụ Goal a b c d e f Start h p q r S = p; Q={b, c, h, r, q} 29
30. Ví dụ Goal a b c d e f Start h p q r S = b; Q={c, h, r, q, a} 30
31. Ví dụ Goal a b c d e f Start h p q r S = c; Q={h, r, q, a} 31
32. Ví dụ Goal a b c d e f Start h p q r S = h; Q={r, q, a} 32
33. Ví dụ Goal a b c d e f Start h p q r S = r; Q={q, a, f} 33
34. Ví dụ Goal a b c d e f Start h p q r S = q; Q={a, f} 34
35. Ví dụ Goal a b c d e f Start h p q r S = a; Q={f} 35
36. Ví dụ Goal a b c d e f Start h p q r S = f; Q={Goal} 36
37. Ví dụ Goal a b c d e f Start h p q r S = Goad; Q={} Tìm thấy 37
38. Ghi nhớ đường đi Việc ghi nhớ đường đi được thực hiện nhờ con trỏ quay lui ◦ Khi mở rộng trạng thái A thu được các trạng thái B, cần ghi nhớ trạng thái trước của B là A. Lịch sử ghi nhớ sẽ được dùng để phát sinh lời giải, cụ thể: ◦ “Tôi đã đến được đích. Tôi thấy mình đã ở f trước đó. Và tôi đã ở r trước khi tới f. Và .” ◦ Con đường lời giải sẽ là “S e r f Goal” a G b c e d f S h p q r 38
39. Ghi nhớ đường đi Previous[a] = b Goal a Previous[Goal] = f Previous[c] = d Previous[b] = d b c Previous[f] = r Previous[d] = start d e f Previous[e] = start Start h Previous[Start] = null p q Previous[h] = e r Previous[p] = start Previous[q] = p Previous[r] = e 39
40. Tìm kiếm theo chiều rộng (BFS) Khởi tạo hàng đợi queue Gán nhãn trạng thái bắt đầu start và đưa vào queue Loop If không còn trạng thái để mở rộng then return “không có lời giải” Chọn trạng thái s đầu hàng đợi để mở rộng If s là trạng thái đích then return “có lời giải” Với mỗi trạng thái s’ mở rộng từ s, successor(s): If s’ chưa được gán nhãn then Gán nhãn s’ Thêm s vào hàng đợi queue Ghi nhớ trạng thái trước của s’ là s. end 40
41. Câu hỏi Giả sử tìm thấy một lời giải, sinh viên hãy viết mã giả cho phép xác định lời giải, tức chuỗi trạng thái từ start end? 41
42. Tìm kiếm theo chiều rộng (BFS) Cách thức mở rộng trạng thái ◦ Xử lý tất cả các trạng thái ở phía trên lời giải “cạn nhất” ◦ Gọi độ sâu của lời giải “cạn nhất” là s, thời gian tìm thấy lời giải là ( 푠) Độ phức tạp không gian lưu trữ ◦ Cần lưu tất cả các node ở tầng cuối cùng, 푠 Tính đầy đủ: ◦ Có vì s là xác định nếu tồn tại lời giải Tối ưu: ◦ Chi khi tất cả các chi phí đều bằng nhau 42
43. Tìm kiếm theo chiều sâu (DFS) Chiến lược duyệt: mở rộng ở trạng thái sâu nhất trước Sử dụng ngăn xếp để triển khai Tùy chọn: đánh dấu các trạng thái đã xem xét ◦ Đánh dấu khi trạng thái được lấy ra khỏi ngăn xếp 43
44. Tìm kiếm theo chiều sâu (DFS) Khởi tạo ngăn xếp stack Đưa trạng thái bắt đầu start vào stack Loop If không còn trạng thái để mở rộng then return “không có lời giải” Chọn trạng thái s đầu ngăn xếp để mở rộng If s là trạng thái đích then return “có lời giải” Gán nhãn cho trạng thái s Với mỗi trạng thái s’ mở rộng từ s, successor(s): If s’ chưa được gán nhãn then Thêm s’ vào ngăn xếp stack Ghi nhớ trạng thái trước của s’ là s. end 44
45. Câu hỏi Cho đồ thị trạng thái như hình vẽ, sinh viên mô tả các bước chạy thuật toán DFS để tìm lời giải từ start đến goal? Goa a l b c d e f Star t h p q r 45
46. Tìm kiếm theo chiều sâu(DFS) Cách thức mở rộng trạng thái: ◦ Từ bên trái nhất của cây tìm kiếm trước ◦ Có thể phải duyệt toàn bộ cây ◦ Nếu độ sâu của cây là m, độ phức tạp tính toán xấu nhất là Độ phức tạp lưu trữ: ◦ Chỉ lưu các trạng thái anh/em của các trạng thái trên đường đi đang xét, ( ) Tính đầy đủ: ◦ Giá trị m có thể không xác định, chỉ đầy đủ nếu ngăn được chu trình Tối ưu: ◦ Không, vì chỉ tìm thấy lời giải ở phía trái nhất, bất chấp độ sâu hay chi phí 46
47. Tìm kiếm với lặp sâu dần (IDS) Ý tưởng: kết hợp ưu điểm về không gian lưu trữ của DFS và độ phức tạp tính toán của BFS Triển khai: Cài đặt hàm chạy thuật toán DFS với độ sâu giới hạn d. Hàm này không xem xét các trạng thái ở độ sâu lớn hơn d. Khởi tạo d = 1. Loop Thực thi hàm DFS với độ sâu là d If tìm thấy lời return “có lời giải” Else d = d + 1 End 47
48. Câu hỏi Cho đồ thị trạng thái như hình vẽ, sinh viên mô tả các bước chạy thuật toán IDS để tìm lời giải từ start đến goal? Goa a l b c d e f Star t h p q r 48
49. Tìm kiếm với chi phí đồng nhất (UCS) Nhắc lại: BFS tìm lời giải có số bước chuyển trạng thái là ít nhất. Trong trường hợp, các chi phí chuyển trạng thái là như nhau thì đây chính là lời giải “tốt nhất”. Trong trường hợp chi phí chuyển trạng thái là không như sau. Làm sao tìm lời giải có “chi phí nhỏ nhất” 49
50. Tìm kiếm với chi phí đồng nhất (UCS) Chiến lược duyệt: Mở rộng trạng thái có chi phí nhỏ nhất trước ◦ Chi phí này là chi phí từ trạng thái bắt đầu đến nó Sử dụng hàng đợi ưu tiên để triển khai Tùy chọn: đánh dấu các trạng thái đã được xem xét ◦ Đánh dấu khi trạng thái được lấy khỏi hàng đợi 50
51. Hàng đợi ưu tiên Hàng đợi ưu tiên là một cấu trúc dữ liệu trong đó có thể thêm vào hoặc lấy ra các cặp (thing, value), với các toán tử sau: Init (PQ) Khởi tạo hàng đợi ưu tiên rỗng IsEmpty (PQ) Kiểm tra hàng đợi rỗng Enqueue (PQ, thing, value) Thêm cặp (thing, value) vào hàng đợi Dequeue (PQ) Trả về cặp (thing, value) có giá trị value thấp nhất, tương ứng với độ ưu tiên cao nhất và loại bỏ nó khỏi hang đợi Hàng đợi ưu tiên được cài đặt sao cho độ phức tạp của toán từ thêm vào (Enqueue) và lấy ra (Dequeue) là (log 푛 ) 51
52. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = null, PQ={(Start,0)} 52
53. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = Start/0 , PQ={(p,1), (d, 3), (e,9)} 53
54. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = p/1 , PQ={ (d, 3), (e,9), (q, 16)} 54
55. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = d/3 , PQ={(b,4),(e,5),(c,11), (q, 16)} 55
56. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = b/4 , PQ={ (e,5),(a,6),(c,11), (q, 16)} 56
57. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = e/5 , PQ={(a,6),(h,6),(c,11), (r,14), (q, 16)} 57
58. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = a/6 , PQ={ (h,6),(c,11), (r,14), (q, 16)} 58
59. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = h/6 , PQ={(q, 10),(c,11), (r,14),} 59
60. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = q/10 , PQ={(c,11), (r,14),} 60
61. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = c/11 , PQ={(r,14),} 61
62. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = r/14, PQ={(f, 19)} 62
63. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = f/19, PQ={(Goal, 24)} 63
64. Ví dụ a Goal 2 2 b 1 8 c 2 5 2 e 3 d f 9 1 Start 9 4 h 5 1 p 15 q 4 r S = Goal/24, PQ={} Tìm thấy 64
65. Tìm kiếm với chi phí đồng nhất (UCS) Khởi tạo hàng đợi ưu tiên pQueue Đưa trạng thái bắt đầu start vào pQueue Loop If không còn trạng thái để mở rộng then return “không có lời giải” Chọn trạng thái s đầu hàng đợi để mở rộng If s là trạng thái đích then return “có lời giải” Gán nhãn cho trạng thái s Với mỗi trạng thái s’ mở rộng từ s, successor(s): If s’ chưa được gán nhãn then 𝑔 푠′ = 𝑔 푠 + (푠, 푠′) If s’ không có trong pQueue then Thêm s’ vào qQueue Ghi nhớ trạng thái trước của s’ là s If s’ có trong pQueue và g(s’) nhỏ hơn giá trị cũ then Cập nhật giá trị của s’ trong qQueue Ghi nhớ trạng thái trước của s’ là s end 65
66. Tìm kiếm với chi phí đồng nhất (UCS) Cách thức mở rộng các node ◦ Xử lý tất cả các trạng thái có chi phí nhỏ hơn lời giải “nhỏ nhất” ◦ Nếu chi phí của lời giải là C* và các cạnh có chi phí nhỏ nhất là ε thì độ sâu ước chừng là C*/ε ◦ Độ phức tạp tính toán là O(bC*/ε) Độ phức tạp không gian lưu trữ ◦ Cần phải lưu tầng xử lý cuối cùng O(bC*/ε) Tính đầy đủ? ◦ Có, nếu lời giải “nhỏ nhất” có chi phí xác định và tât cả các cạnh có chi phí không âm Tối ưu? ◦ Có 66
67. Các điều cần nắm Định nghĩa được bài toán tìm kiếm và liệt kê được ứng dụng thực tế Hiểu được các khái niệm liên quan: trạng thái, đồ thị trạng thái, cây tìm kiếm Hiểu các thuật toán tìm kiếm mù: BFS, DFS, UCS, IDS và các thuộc tính của chúng 67
68. Tài liệu tham khảo Cơ sở Trí tuệ Nhân tạo, Lê Hoài Bắc, Tô Hoài Việt, NXB Khoa học & Kỹ thuật. Slide bài giảng Trí tuệ nhân tạo, GV. Tô Hoài Việt, GV. Lê Ngọc Thành, Khoa CNTT, ĐH. KHTN TP.HCM Artificial Intelligence: A Modern Approach, 3rd Edition, S. Russel and P. Norvig, Pearson Education Inc., 2010 Techniques in Artificial Intelligence (SMA 5504) , MIT OpenCourseWare, Massachusetts Institute of Technology Artificial Intelligence: Principles and Techniques, Stanford courses, Autumn 2015. 68