Tìm kiếm đầu tiên tốt nhất là một kỹ thuật duyệt để quyết định nút nào sẽ được truy cập tiếp theo bằng cách kiểm tra xem nút nào là nút hứa hẹn nhất và sau đó kiểm tra nút đó. Đối với điều này, nó sử dụng một chức năng đánh giá để quyết định việc truyền tải.
Kỹ thuật tìm kiếm đầu tiên tốt nhất về duyệt cây này thuộc thể loại tìm kiếm theo kinh nghiệm hoặc kỹ thuật tìm kiếm thông tin.
Chi phí của các nút được lưu trữ trong một hàng đợi ưu tiên. Điều này làm cho việc triển khai tìm kiếm ưu tiên tốt nhất giống như triển khai Tìm kiếm đầu tiên theo chiều rộng. Chúng tôi sẽ sử dụng hàng đợi ưu tiên giống như chúng tôi sử dụng hàng đợi cho BFS.
Thuật toán để triển khai Tìm kiếm đầu tiên tốt nhất
Step 1 : Create a priorityQueue pqueue. Step 2 : insert ‘start’ in pqueue : pqueue.insert(start) Step 3 : delete all elements of pqueue one by one. Step 3.1 : if, the element is goal . Exit. Step 3.2 : else, traverse neighbours and mark the node examined. Step 4 : End.
Thuật toán này sẽ đi qua đường ngắn nhất đầu tiên trong hàng đợi. Trong trường hợp xấu nhất, thuật toán lấy O (n * logn) thời gian.