Trí tuệ nhân tạo - Chương 4

Tìm kiếm heuristiclà 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:
Nội dung trích xuất từ tài liệu:
Trí tuệ nhân tạo - Chương 4 Chương 4 – Tìm kiếm heuristic là các phỏng đoán, ước chừng dựa Heuristics: 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 bằng TK 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. TTNT. p.63C 4 – Tìm kiếm Heuristic Giải Thuật Heuristic 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), 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: • Giải thuật leo núi (hill-climbing) • TK tốt nhất (best-first search) TTNT. p.64 C 4 – Tìm kiếm HeuristicKGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng của các trạng thái. TTNT. p.65C 4 – Tìm kiếm Heuristic Phép đo heuristic (2)Heuristic “Số đường thắng nhiều nhất” áp dụng cho các nút con đầu tien trong tic-tac-toe. TTNT. p.66C 4 – Tìm kiếm HeuristicKGTT càng thu nhỏ khi áp dụng heuristic TTNT. p.67C 4 – Tìm kiếm Heuristic Giải thuật Leo Núi Giải thuật: – Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó bằng hàm đánh giá heuristic. – Con “tốt nhất” sẽ được chọn để đi tiếp. 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. TTNT. p.68C 4 – Tìm kiếm Heuristic Giải thuật TK Tốt Nhất open = [A5]; closed = []1. Đánh giá A5; open = [B4,C4,D6];2. closed = [A5] Đánh giá B4;3. open = [C4,E5,F5,D6]; closed = [B4,A5] Đánh giá C4;4. open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5] Đánh giá H3;5. open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5] Đánh giá O2;6. open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] Đánh giá P3; tìm được lời giải!7. TTNT. p.69 C 4 – Tìm kiếm Heuristic Cài Đặt Hàm Đánh Giá (Evaluation Function) Xét trò chơi 8-puzzle. Cho 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 start mục tiêu. 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 3h(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 TTNT. p.70 C 4 – Tìm kiếm HeuristicKhó khăn trong thiết kế hàm heuristic Ba heuristic áp dụng vào 3 trạng thái của trò chơi ô đố 8 số TTNT. p.71C 4 – Tìm kiếm HeuristicHeuristic 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 bố, mẹ là MIN, gán cho nó giá trị nhỏ nhất có trong các trạng thái con. TTNT. p.72C 4 – Tìm kiếm Heuristic Hãy áp dụng GT Minimax vào Trò Chơi NIM TTNT. p.73C 4 – Tìm kiếm Heuristic Minimax với độ sâu lớp cố định Minimax đối với một KGTT giả định. nút lá được gán các giá trị heuristic Các Còn giá tr ...