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

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PDF | Số trang:35

Thêm vào BST

Báo xấu

266
lượt xem 43
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 α-β.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 15
Ví dụ 16
Ví dụ … 17
Ví dụ … 18
Heuristic trong trò chơi ñối kháng Giải thuật minimax Hai ñấu thủ trong trò chơi ñược gọi là MIN và MAX. Mỗi nút lá có giá trị: 1 nếu là MAX thắng, 0 nếu là MIN thắng. Minimax sẽ truyền các giá trị này lên cao dần trên ñồ thị, qua các nút cha mẹ kế tiếp theo các luật sau: Nếu trạng thái cha mẹ là MAX, gán cho nó giá trị lớn nhất có trong các trạng thái con. Nếu trạng thái cha mẹ là MIN, gán cho nó giá trị nhỏ nhất có trong các trạng thái con. 19
Áp dụng GT Minimax vào Trò Chơi NIM 1 MIN 1 1 1 MAX MIN 0 1 0 1 MAX 0 0 1 KẾT QUẢ CỦA MIN 0 1 MAX 0 MAX KẾT QUẢ CỦA MIN 20