Best-First search

Nguyên lý chung

Chọn hướng đi triển vọng nhất trong số những hướng đi đã biết

Tham khảo: Giải một bài toán trên máy tính thế nào?
Tác giả: GS.TSKH.Hoàng Kiếm

Một số chú ý:
Kết hợp ưu điểm của duyệt theo chiều rộng và chiều sâu: không sa vào các ngõ cụt và không quan tâm đến sự mở rộng của nhánh.
Có 1 điều lưu ý: là Best First Search sẽ không duyệt hết tất cả các đường đi. Nó chỉ duyệt 1 phần mà nó cho là tốt và lưu những trạng thái tốt tiếp theo.
Phân biệt với leo núi dốc đứng: duyệt trạng thái con tốt nhất và không lưu các trạng thái con còn lại.
Nếu gặp hướng đi có vẻ xấu, nó sẽ lấy ra 1 trạng thái tốt tiếp theo nằm trong hàng đợi. Vì vậy nên cài đặt thuật toán dựa trên hàng đợi ưu tiên. Cấu trúc heap là 1 điển hình dễ hiểu nhất.
BFS khá đơn giản, vì vậy thông thường người ta áp dụng 1 phiên bản đặc biệt của BFS là A*.
Một số vấn đề đôi khi còn nhầm lẫn: (Best First Search và A*)

• Bạn đôi khi thấy Best First Search và A* khác và giống nhau. Thực sự A* là cải tiến của Best First Search. Cả 2 đều sử dụng hàm heuristic để đánh giá chi phí về đích
• Cả 2 đều duyệt 1 phần của đồ thị. Nó chỉ chọn con đường có vẻ tốt và có quay lui lại chọn những con đường khác tốt hơn nhưng nó không bao giờ chọn con đường xấu cả. Con đường xấu đôi khi có thể dẫn về đích sớm hơn.