সেরা প্রথম অনুসন্ধান (অবহিত অনুসন্ধান)

সর্বোত্তম প্রথম অনুসন্ধান হল একটি ট্রাভার্সাল কৌশল যা পরবর্তীতে কোন নোডটি পরিদর্শন করা হবে তা নির্ধারণ করে কোন নোডটি সবচেয়ে প্রতিশ্রুতিশীল এবং তারপরে এটি পরীক্ষা করে দেখুন৷ এর জন্য এটি একটি মূল্যায়ন ফাংশন ব্যবহার করে ট্রাভার্সাল নির্ধারণ করতে।

ট্রি ট্রাভার্সালের এই সর্বোত্তম প্রথম অনুসন্ধান কৌশলটি হিউরিস্টিক অনুসন্ধান বা তথ্য অনুসন্ধান কৌশলের বিভাগে আসে।

নোডের খরচ একটি অগ্রাধিকার সারিতে সংরক্ষণ করা হয়। এটি সর্বোত্তম-প্রথম অনুসন্ধানের বাস্তবায়নকে ব্রেডথ ফার্স্ট অনুসন্ধানের মতোই করে তোলে। আমরা যেমন BFS-এর জন্য একটি সারি ব্যবহার করি ঠিক তেমনই আমরা অগ্রাধিকার সারি ব্যবহার করব।

সেরা প্রথম অনুসন্ধান বাস্তবায়নের জন্য অ্যালগরিদম

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.

এই অ্যালগরিদমটি সারিতে প্রথমে সবচেয়ে ছোট পথ অতিক্রম করবে। সবচেয়ে খারাপ পরিস্থিতিতে অ্যালগরিদম O(n*logn) নেয় সময়।