Đề 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
2.1
2.1

Hàm đánh giá
2.2
2.2
2.2
2.2

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 Trạng thái kết thúc
Quân 3 cần ít nhất 2 dịch chuyển
2. Ví dụ về hàm đánh giá (tiếp)
Trạng thái đầu
Trạng thái kết thúc
Quân 8 cần ít nhất 3 dịch chuyển
2. Ví dụ về hàm đánh giá (tiếp)
Trạng thái đầu
Trạng thái kết thúc
Quân 6 cần ít nhất 1 dịch chuyển
2. Ví dụ về hàm đánh giá (tiếp)
Trạng thái đầu
Trạng thái kết thúc
Quân 1 cần ít nhất 3 dịch chuyển
Vậy h2(u) = 2 + 3 + 1 + 3 = 9
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

3. Nếu không tốt hơn thì thì tiếp lần lặp kế.
•
Nhận xét:
– Có sử dụng hàm đánh giá để tích hợp tri thức vào điều khiển.
– Giải thuật trên không đánh giá, so sánh giữa các con của trạng
thái hiện tại.