1
KỸ THUẬT TÌM KIẾM
HEURISTIC
2
NỘI DUNG
• Sinh ra và Kiểm thử (Generate-and-Test)
• Leo đồi (Hill Climbing)
– Leo đồi đơn giản (Simple Hill Climbing)
– Leo đồi dốc đứng (Steepest-Ascent Hill Climbing)
–Mô phỏng luyện kim (Simulated Annealing)
• Tìm kiếm tốt nhất đầu tiên
– Đồ thị OR & Thuật toán tìm kiếm tốt nhất đầu tiên
– Thuật toán A*
•Suy giảm vấn đề
– Đồ thị AND-OR
– Thuật toán AO*
• Thỏa mãn ràng buộc (Constraint satisfaction)
•Phân tích Means-Ends
3
SINH RA VÀ KIỂM THỬ
Generate-and-Test
•Algo Genarate-and-Test
1. Sinh ra: một « lời giải tiềm năng » có thể
▪Sinh ra một nút / Sinh ra một đường đi xuất phát từ trạng thái khởiđầu
2. Kiểm thử: « lời giải tiềm năng » được sinh ra là một lời giải?
▪So sánh nút được sinh ra/ đầu mút cuối của đường đi được sinh ra với các trạngthái
đích
3. Nếu tìm thấy một lời giải « thông báo và thoát » nếu không quay lại
bước 1.
•
–
–
–
–
• Nếu quá trình « sinh ra » là có hệ thống, thủ tục « có thể » tìm thấy một
lời giải nếu nó tồn tại nhưng « có thể » rất lâu!
Thuật toán « Sinh ra và Kiểm thử » là thuật toán tìm kiếm sâu.
Nếu « sinh ra » có hệ thống (tìm kiếm vét cạn)
Nếu « sinh ra » ngẫu nhiên, không chắc tìm thấy lời giải dù nó tồn tại (thuật
toán bảo tàng Anh – British Museum)
« Sinh ra » có hệ thống, bỏ qua một số « lời giải tiềm năng » thiếu hứa hẹn là
một giải pháp dung hòa hai thái cực trên (Sinh ra và kiểm thử heuristic)
« Sinh ra và kiểm thử » kết hợp với « Lập kế hoạch »
4
LEO ĐỒI – HILL CLIMBING (1)
•Leo đồi là một biến thể của sinh ra và kiểm thử, trong đó
thông tin phản hồi từ thủ tục kiểm thử hỗ trợ «bộ sinh »
quyết định hướng di chuyển
– Trong « Sinh ra và kiểm thử », hàm kiểm thử là hàm Yes-No
– Nếu hàm kiểm thử là một hàm heuristic, cung cấp một ước
lượng « tính gần » của trạng thái đã cho so với đích, « bộ sinh »
sẽ khai thác « thông tin » này để quyết định hướng « khai thác »
• Leo đồi thường được sử dụng khi có sẵn một hàm
heuristic tốt và thiếu thông tin hữu dụng khác
5
LEO ĐỒI – HILL CLIMBING (2)
LEO ĐỒI ĐƠN GiẢN
•Algo Simple Hill Climbing
1. Đánh giá trạng thái khởi đầu.Nếu nó là một trạng thái đích, « thông
báo kết quả »và thoát, nếu không lấy trạng thái khởi đầu làm trạng
thái hiện hành.
2. Lặp lại đến tận khi tìm thấy một lời giải hoặc không còn toán tử nào
có thể áp dụng vào trạng thái hiện hành:
a) Chọn một toán tử có thể áp dụng vào trạng thái hiện hành nhưng chưa
được áp dụng vào trạng thái hiện hành.Áp dụng nó vào trạng thái hiện
hành để sinh ra trạng thái mới
b) Đánh giá trạng thái mới.
iii.
i. Nếu nó là một trạng thái đích, « thông báo kết quả » và thoát
ii. Nếu nó không là một trạng thái đích nhưng « tốt hơn » trạng thái hiện hành, lấy
nó làm trạng thái hiện hành
Nếu nó không là một trạng thái đích và không « tốt hơn » trạng thái hiện hành,
tiếp tục vòng lặp
•
•Hàm đánh giá « tốt hơn » là phương tiện để đưa « tri thức lĩnh
vực » vào quá trình điều khiển.
Phương pháp tìm kiếm sử dụng « tri thức lĩnh vực » được gọi là
phương pháp tìm kiếm heuristic.