Xung quanh thuật giải Best First Search

[anbinhtrong]

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*.