Best first search là kỹ thuật duyệt quyết định nút nào sẽ được thăm tiếp theo bằng cách kiểm tra nút nào là hứa hẹn nhất và sau đó kiểm tra nó. Để làm điều này, nó sử dụng một hàm đánh giá để quyết định duyệt.
Kỹ thuật duyệt cây best first search này thuộc loại tìm kiếm heuristic hoặc tìm kiếm có thông tin (informed search).
Chi phí của các nút được lưu trữ trong hàng đợi ưu tiên. Điều này làm cho việc triển khai best-first search giống như tìm kiếm theo chiều rộng (BFS). Chúng ta sẽ dùng priority_queue giống như dùng queue cho BFS.
Thuật toán triển khai Best First Search
Bước 1: Tạo priorityQueue pqueue.
Bước 2: Chèn 'start' vào pqueue: pqueue.insert(start)
Bước 3: Xóa tất cả phần tử của pqueue một per một.
Bước 3.1: Nếu phần tử là goal. Thoát.
Bước 3.2: Ngược lại, duyệt các hàng xóm và đánh dấu nút đã kiểm tra.
Bước 4: Kết thúc.
Thuật toán này sẽ duyệt đường đi ngắn nhất trước trong hàng đợi. Trong trường hợp xấu nhất, thuật toán mất O(n*logn) thời gian.