বেস্ট ফার্স্ট সার্চ (ইনফর্মড সার্চ)

বেস্ট ফার্স্ট সার্চ হলো একটি ট্রাভার্সাল টেকনিক যা চেক করে কোন নোড সবচেয়ে প্রমিশিং এবং সেটিকে ভিজিট করে। এজন্য এটি একটি ইভ্যালুয়েশন ফাংশন ব্যবহার করে ট্রাভার্সাল ডিসাইড করে।

ট্রি ট্রাভার্সালের এই বেস্ট ফার্স্ট সার্চ টেকনিক হিউরিস্টিক সার্চ বা ইনফর্মড সার্চ টেকনিকের ক্যাটেগরিতে পড়ে।

নোডের কস্টগুলো প্রায়োরিটি কিউ-তে স্টোর করা হয়। এতে বেস্ট-ফার্স্ট সার্চের বাস্তবায়ন ব্রেডথ ফার্স্ট সার্চের মতো হয়। আমরা প্রায়োরিটি কিউই ব্যবহার করব যেমন BFS-এ কিউ ব্যবহার করি।

বেস্ট ফার্স্ট সার্চ বাস্তবায়নের অ্যালগরিদম

ধাপ ১: একটি প্রায়োরিটি কিউ pqueue তৈরি করুন। 
ধাপ ২: 'start' কে pqueue-তে ইনসার্ট করুন: pqueue.insert(start) 
ধাপ ৩: pqueue-এর সব এলিমেন্ট এক এক করে ডিলিট করুন। 
    ধাপ ৩.১: যদি এলিমেন্টটি গোল হয়। এক্সিট। 
    ধাপ ৩.২: অন্যথায়, নেইবপুর ট্রাভার্স করুন এবং নোড একজামিনড মার্ক করুন। 
ধাপ ৪: শেষ।

এই অ্যালগরিদম কিউ-তে শর্টেস্ট পাথ ফার্স্ট ট্রাভার্স করবে। ওৰস্ট কেস সিনেরিওতে অ্যালগরিদম O(n*logn) টাইম নেবে।