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 II - 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 II - 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 II THS. BÙI THỊ DANH BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
2. Nội dung Heuristic Tìm kiếm tham lam Thuật giải A* Sự nới lỏng 2
3. Heuristic Các thuật toán tìm kiếm mù duyệt trạng thái theo mọi hướng, không sử dụng thông tin của trạng thái đích. Ước lượng chi phí đến trạng thái đích. Liệu có tìm đường nhanh hơn?!? 3
4. Heuristic Heuristic là một hàm ước lượng mức độ gần của một trạng thái so với trạng thái đích ◦ Kí hiệu là h(s), với s là trạng thái. Heuristic được thiết kế cho từng bài toán tìm kiếm cụ thể Một số hàm heuristic phổ biến: ◦ Khoảng cách Euclidean, Mahattan. ◦ 4
5. Ví dụ - Tìm đường đi cho Pacman Hàm h(s) là hàm Euclidean 5
6. Ví dụ - Tìm đường đi trên bản đồ Hàm h(s) là khoảng cách đường chim bay 6
7. Ví dụ - N-Puzzle Hàm h(s): số ô khác biệt giữa 2 puzzle 7
8. Nội dung Heuristic Tìm kiếm tham lam Thuật giải A* Sự nới lỏng 8
9. Tìm kiếm tham lam (greedy search) Chiến lược duyệt: mở rộng trạng thái được ước lượng là gần trạng thái đích nhất ◦ Hàm heuristic tương ứng h(s) có giá trị nhỏ nhất Sử dụng hàng đợi ưu tiên để triển khai, với độ ưu tiên là h(s) 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 9
10. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = null, PQ={(Start,12)} 10
11. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = Start/12, PQ={(e, 4), (d, 8), (p,11)} 11
12. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = e/4, PQ={ (h,6), (r, 6), (d, 8), (p,11),} 12
13. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = h/6, PQ={(r, 6), (d, 8), (q, 9), (p,11),} 13
14. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = r/6, PQ={ (f, 4), (d, 8), (q, 9), (p,11),} 14
15. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = f/4, PQ={ (Goal, 0), (d, 8), (q, 9), (p,11),} 15
16. Ví dụ a Goal h = 0 2 h = 8 2 h = 5 b 1 8 c 2 5 h = 11 2 e 3 d h = 4 f h = 8 9 1 Start 9 h = 4 4 h 5 h = 12 1 p h = 6 15 q 4 r h = 11 h = 9 h = 6 S = Goal/0, PQ={ (d, 8), (q, 9), (p,11),} Đã tìm thấy Goal 16
17. Tìm kiếm tham lam (greedy search) 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 mới s’ mở rộng từ s: If s’ chưa được gán nhãn then Tí푛ℎ ℎ(푠′) If 푠′ không có trong pQueue then Thêm s’ vào pQueue Ghi nhớ trạng thái trước của s’ là s end 17
18. Tìm kiếm tham lam (greedy search) Tính đầy đủ: ◦ Có Tính tối ưu: ◦ Không, vì chỉ dựa vào chi phí ước lượng ◦ Thường đưa agent tới thẳng trạng thái đích, nhưng không phải với chi phí tốt nhất Độ phức tạp tính toán: ◦ O(min N, max ) Độ phức tạp lưu trữ: ◦ O(min N, max ) 18
19. Nội dung Heuristic Tìm kiếm tham lam Thuật giải A* Sự nới lỏng 19
20. Thuật giải A* Ý tưởng: kết hợp thuật toán UCS và tìm kiếm tham lam UCS: chiến lược duyệt dựa theo chi phí từ trạng thái bắt đầu đến trạng thái đang xét, (푠) Tìm kiếm tham lam: chiến lược duyệt dựa theo chi phí ước lượng từ trạng thái đang xét đến trạng thái cuối, ℎ(푠) Thuật giải A*: chiến lược duyệt dựa theo theo giá trị tổng 푠 = 푠 + ℎ(푠) ℎ 푠 ,ước lượng Start s Goal (푠) 20
21. Thuật giải A* 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 mới (s’) mở rộng từ s: If 푠′ không thuộc pQueue và chưa gán nhãn then 푠′ = 푠 + 푠, 푠′ 푠′ = 푠′ + ℎ(푠′) Thêm s’ vào pQueue và ghi nhớ trạng thái trước của s’ là s If 푠′ thuộc pQueue hoặc đã gán nhãn then 푠′ = min{ 푠′ , 푠 + (푠, 푠′) f 푠′ = 푠′ + ℎ(푠) If 푠′ giảm then Ghi nhớ trạng thái trước của s’ là s If 푠′ giảm và s’ đã được gán nhãn then Đưa s’ trở lại hàng đợi end 21
22. Thuật giải A* có tối ưu? Chi phí ước lượng cao hơn chi phí thực thuật toán A* cho kết quả không tối ưu ◦ Chi phí đi từ s đến A là 6, nhưng chi phí thực tế chỉ là 1. 22
23. Heuristic có thể chấp nhận Một heuristic là có thể chấp nhận (admissible) nếu: 0 ≤ ℎ 푠 ≤ ℎ∗ 푠 ◦ Trong đó, ℎ∗(푠) là chi phí thực tế nhỏ nhất để đến đích từ s. Định lý: Nếu ℎ(푠) là heristic có thể chấp nhận, thuật toán A* với cây tìm kiếm có tính tối ưu. 23
24. Heuristic có thể chấp nhận Thông thường, admissible heuristic là các lời giải cho các bài tóan được nới lỏng ràng buộc (relaxation), ở đó có nhiều hành động mới được cho phép. Đôi khi các inadmissible heuristic cũng có ích 24
25. Nội dung Heuristic Tìm kiếm tham lam Thuật giải A* Sự nới lỏng 25
26. Sự nới lỏng (relaxation) Làm sao để có một heuristic tốt? ◦ Lý tưởng thì h(s) = h*(s). Điều này khó như giải quyết bài toán gốc ◦ Thay vì dùng h*(s) của bài toán gốc, chúng ta dùng h*(s) của bài toán dễ hơn ◦ Heuristic tốt liên quan đến mô hình hóa, không phải xây dựng thuật toán 26
27. Sự nới lỏng Giảm chi phí Loại bỏ ràng buộc Lời giải Các bài Tìm kiếm dạng gần toán con dễ hơn đúng độc lập 27
28. Lời giải dạng gần đúng Mục tiêu: di chuyển từ ô hình tam giác đến hình tròn Nới lỏng: bỏ các bức tường đi Bài toán sau khi nới lỏng: ℎ∗(푠) là khoảng cách Mahattan ◦ Sử dụng ℎ∗(푠) này để làm heuristic 28
29. Tìm kiếm dễ hơn Bài toán gốc ◦ Trạng thái bắt đầu: thành phố 1 ◦ Hành động walk: từ s đến s+1 ( chi phí là 1) ◦ Hành động tram: từ s đến 2s (chi phí là 2) ◦ Trạng thái đích: thành phố n ◦ Ràng buộc: số hành động tram không được nhiều hơn walk Trạng thái: (thành_phố, #walk - #tram) ◦ Số trạng thái từ O(n) thành O(n2) 29
30. Tìm kiếm dễ hơn Giữ các thông tin bài toán gốc, nhưng loại bỏ ràng buộc Trạng thái sau nới lỏng: (thành_phố) Bài toán sau khi nới lỏng: tìm đường đi từ thành phố 1 đến thành phố n. ◦ Hàm heuristic là ℎ∗(푠) của bài toán nới lỏng: kết quả của thuật toán UCS tìm đường từ trạng thái s tới trạng thái đích hoặc ngược lại 30
31. Bài toán con độc lập Bài toán gốc: các mảnh ghép không được chồng lên nhau Nới lỏng: Các mảnh ghép có thể chồng lên nhau. Bài toán sau khi nới lỏng: 8 bài toán con độc lập nhau. ◦ Mỗi bài toán con tương ứng với một dạng gần đúng (slide trước). ◦ Hàm heuristic là hàm tổng của các bài toán con. 31
32. Nhắc lại Các bài toán nới lỏng được sử dụng để lấy giá trị cho hàm heuristic h(s) nhằm định hướng tìm kiếm. Các lời giải của bài toán nới lỏng không phải là lời giải của bài toán gốc. 32
33. 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. 33