Bài giảng Trí tuệ nhân tạo - Bài 4: Tìm kiếm kinh nghiệm (heuristic)

Trong bài 4 chúng ta sẽ cùng tìm hiểu về tìm kiếm kinh nghiệm thông qua các nội dung sau đây: Giải quyết bài toán bằng tìm kiếm heuristic, giải thuật Heuristic, phép đo heuristic, tìm kiếm tốt nhất-đầu tiên, giải thuật "Leo đồi",...và một số nội dung khác.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo - Bài 4: Tìm kiếm kinh nghiệm (heuristic) Lec 4Tìm kiếm kinh nghiệm Lec 4-TTNT. p.1Tìm kiếm kinh nghiệ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 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.2 Giải quyết bài toán bằng tìm kiếm heuristic Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử của bài toán Xây dựng hàm đánh giá Thiết kế chiến lược chọn trạng thái để phát triển ở mỗi bước. TTNT. p.3 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: • Tìm kiếm tốt nhất-đầu tiên (best-first search): Tìm kiếm theo chiều rộng + hàm đánh giá • Tìm kiếm leo đồi (hill-climbing): Tìm kiếm theo chiều sâu + hàm đánh giá TTNT. p.4KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng của các trạng thái. TTNT. p.5 Phép đo heuristicHeuristic “Số đường thắng nhiều nhất” áp dụng cho các nút con đầu tiên trong tic-tac-toe. TTNT. p.6 Tìm kiếm tốt nhất-đầu tiênProcedure Best-first search;Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái đầu; 2. Loop do 2.1 If L rỗng then {thông báo thất bại; stop}; 2.2 Loại trạng thái u ở đầu danh sách L; 2.3 If u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4 For mỗi trạng thái v kề u do Chèn v vào danh sách L sao cho L được sắp theo thứ tự tăng dần của hàm đánh giá;End; TTNT. p.7 Ví dụ:tìm kiếm tốt nhất-đầu tiên 20 A 20 A 15 C 15 C E 7 E 7 6 D 6 D10 K 12 F I 8 K 12 10 F I 8 G 5 0 B 3 G 5 H Đồ thị không gian trạng thái 0 B 3 H Cây tìm kiếm tốt nhất-đầu tiên TTNT. p.8 Giải thuật Leo đồ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.Procedure Hill-Climbing_search;Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái đầu; 2. Loop do 2.1 If L rỗng then {thông báo thất bại; stop}; 2.2 Loại trạng thái u ở đầu danh sách L; 2.3 If u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4 For mỗi trạng thái v kề u do đặt v vào L1; 2.5 Sắp xếp L1 theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái tốt nhất ở đầu danh sách L1; 2.6 Chuyển danh sách L1vào đầu danh sách L sao cho L1 ở đầu danh sách L;End; TTNT. p.9 Giải thuật Leo đồi 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.10 Ví dụ: tìm kiếm leo đồi 20 A 20 A 15 C ...