Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Các chiến lược tìm kiếm kinh nghiệm Trong chương I, chúng ta đã nghiên cứu việc biểu diễn vấn đề trong không gian trạng thái và các kỹ thuật tìm kiếm mù. Các kỹ thuật tìm kiếm mù rất kém hiệu quả và trong nhiều trường hợp không thể áp dụng được | Chương II Các chiến lược tìm kiếm kinh nghiệm Trong chương I chúng ta đã nghiên cứu việc biểu diễn vấn đề trong không gian trạng thái và các kỹ thuật tìm kiếm mù. Các kỹ thuật tìm kiếm mù rất kém hiệu quả và trong nhiều trường hợp không thể áp dụng được. Trong chương này chúng ta sẽ nghiên cứu các phương pháp tìm kiếm kinh nghiệm tìm kiếm heuristic đó là các phương pháp sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm. Hàm đánh giá và tìm kiếm kinh nghiệm Trong nhiều vấn đề ta có thể sử dụng kinh nghiệm tri thức của chúng ta về vấn đề để đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u chúng ta sẽ xác định một giá trị số 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á. Chúng ta sẽ sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm. Trong quá trình tìm kiếm tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái có giá trị hàm đánh giá nhỏ nhất trạng thái này được xem là trạng thái có nhiều hứa hẹn nhất hướng tới đích. 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 1. 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 vấn đề. 2. Xây dựng hàm đánh giá. 3. Thiết kế chiến lược chọn trạng thái để phát triển ở mỗi bước. Hàm đánh giá Trong tìm kiếm kinh nghiệm hàm đánh giá đóng vai trò cực kỳ quan trọng. Chúng ta có xây dựng được hàm đánh giá cho ta sự đánh giá đúng các trạng thái thì tìm kiếm mới hiệu quả. Nếu hàm đánh giá không chính xác nó có thể dẫn ta đi chệch hướng và do đó tìm kiếm kém hiệu quả. Hàm đánh giá được xây dựng tùy thuộc vào vấn đề. Sau đây là một số ví dụ về hàm đánh giá Trong bài toán tìm kiếm đường đi trên bản đồ giao thông ta có thể lấy độ dài của đường chim bay từ một thành phố tới một thành phố đích làm giá trị của hàm đánh giá. Bài toán 8 số. Chúng ta có thể đưa ra hai cách xây dựng hàm đánh giá. Hàm h1 Với mỗi trạng thái u thì
