Tài liệu Báo cáo tiểu luận môn trí tuệ nhân tạo tìm kiếm heuristic.ppt

Đề tài: TÌM KIẾM HEURISTIC Giáo viên hướng dẫn: Nguyễn Thị Thủy Nhóm sinh viên: Nguyễn Thị Diệp Phạm Thị Định Nguyễn Thị Gấm Nguyễn Thị Nụ Lớp: THC_52 • Các kỹ thuật tìm kiếm sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm được gọi chung là các kỹ thuật tìm kiếm kinh nghiệm (heuristic search). • Các giai đoạn cơ bản để giải quyết vấn đề bằng tìm kiếm kinh nghiệm như sau: 2.1 2.1 Hàm đánh giá 2.2 2.2 Tìm kiếm Beam 2.3 2.3 Tìm kiếm leo đồi 2.4 2.4 Tìm kiếm tốt nhất 1. Định nghĩa hàm đánh giá Với mỗi trạng thái u chúng ta sẽ xác định một giá trị h(u), số này đánh giá “sự gần đích “ của trạng thái u. Hàm h(u) được gọi là hàm đánh giá. 2. Ví dụ vềề hàm đánh giá Ví dụ bài toán 8 sốố Trạng thái đầều Trạng thái kềốt thúc Chúng ta có thể đưa ra hai cách xầy dựng hàm đánh giá h1, h2. 2. Ví dụ về hàm đánh giá (tiếp) Trạng thái đầều Trạng thái kềốt thúc - Hàm h1: h1(u) là số quân ở trạng thái đầu không nằm đúng vị trí so với trạng thái kết thúc. Ta có các quân: 3, 8, 6, 1 không nằm đúng vị trí => h1(u) = 4 2. Ví dụ về hàm đánh giá (tiếp) - Hàm h2: h2(u) là tổng khoảng cách giữa vị trí các quân trong trạng thái đầu và vị trí của nó trong trạng thái đích. Ở đây khoảng cách là số ít nhất các dịch chuyển theo hàng hoặc theo cột để đưa một quân tới vị trí của nó trong trạng thái đích. 2. Ví dụ về hàm đánh giá (tiếp) Trạng thái đầều Quần 3 cầền ít nhầốt 2 dịch chuyển Trạng thái kềốt thúc 2. Ví dụ về hàm đánh giá (tiếp) Trạng thái đầều Quần 8 cầền ít nhầốt 3 dịch chuyển Trạng thái kềốt thúc 2. Ví dụ về hàm đánh giá (tiếp) Trạng thái đầều Quần 6 cầền ít nhầốt 1 dịch chuyển Trạng thái kềốt thúc 2. Ví dụ về hàm đánh giá (tiếp) Trạng thái đầều Quần 1 cầền ít nhầốt 3 dịch chuyển Vậy h2(u) = 2 + 3 + 1 + 3 = 9 Trạng thái kềốt thúc 1.Ý tưởng thuật toán Đầu tiên chọn trạng thái ban đầu, sau đó phát triển k đỉnh tốt nhất ở một mức rồi phát triển k đỉnh tốt nhất ở mức tiếp theo (k được xác định bởi hàm đánh giá). 2. Ví dụ về tìm kiếm beam Chọn k = 2 A: là trạng thái đầều B: là trạng thái kềốt thúc Các sốố bền cạnh các đỉnh là giá trị của hàm đánh giá 2. Ví dụ về tìm kiếm beam Từ trạng thái ban đầu A chọn 2 đỉnh (D, E) có chi phí nhỏ nhất kề với A để phát triển tiếp