Bài giảng Trí tuệ nhân tạo - Chương 3: Các kỹ thuật tìm kiếm Heuristics

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham khảo nội dung "Bài giảng Trí tuệ nhân tạo - Chương 3: Các kỹ thuật tìm kiếm Heuristics " dưới đây. Nội dung tài liệu cung cấp cho các bạn những kiến thức về khái niệm Heuristics, 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 α-β.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo - Chương 3: Các kỹ thuật tìm kiếm Heuristics Chương 3: Các kỹ thuật tìm kiếm Heuristics 1 Nội 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 Giới hạn của duyệt 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 1010 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ó 1024 trạng thái]
Cần chiến lược tìm kiếm heuristic 3 Khái niệm: Heuristic
Heuristics: là các phỏng ñoán, ước chừng dựa trên kinh nghiệm, trực giác
Các hệ giải quyết AI sử dụng heuristic trong hai tình huống cơ bản:  Bài toán ñược ñịnh nghĩa chính xác nhưng chi phí tìm lời giải vét cạn là không thể chấp nhận VD: Sự bùng nổ KGTT trong trò chơi cờ vua  Vấn ñề với nhiều sự mơ hồ trong lời phát biểu bài toán hay dữ liệu cũng như tri thức sẵn có VD: Chẩn ñoán trong y học 4 Khái niệm: Giải thuật Heuristics
Một giải thuật heuristic có thể ñược xem gồm 2 phần:  Phép ño heuristic: thể hiện qua hàm ñánh giá heuristic (evaluation function f(n) - EF), dùng ñể ñánh giá các ñặc ñiểm của một trạng thái trong KGTT  Giải thuật tìm kiếm heuristic:
TK tốt nhất (best-first search)
A* search
Giải thuật leo núi (hill-climbing) 5 Ví dụ phép ño Heuristics 6 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 7 Ví dụ phép ño Heuristics (tt) 8 Giải thuật leo ñồi (Hill climbing)
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 OR 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ì thì tiếp lần lặp kế 9 Giải thuật leo ñồi (tt)
Giới hạn  Giải thuật 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  Giải thuật 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 10 Giải thuật leo ñồi (tt)
Bài toán 8 Hậu  Trang thái bắt ñầu: mỗi Hậu trên 1cộ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 11 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, GT 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 GT 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. 12 Tìm kiếm tốt nhất (BFS)
Giải thuật  OPEN = [TT ñầu]  Lặp ñến khi: gặp ñích OR 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ó 13 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! 14 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 ...