बेस्ट फर्स्ट सर्च एक ट्रैवर्सल तकनीक है जो यह तय करती है कि कौन सा नोड अगला विज़िट किया जाए, यह जांचकर कि कौन सा नोड सबसे अधिक आशाजनक है और फिर उसे चेक करती है। इसके लिए यह एक मूल्यांकन फंक्शन का उपयोग करती है ताकि ट्रैवर्सल तय किया जा सके।
ट्री ट्रैवर्सल की यह बेस्ट फर्स्ट सर्च तकनीक ह्यूरिस्टिक सर्च या इन्फॉर्म्ड सर्च तकनीक की श्रेणी में आती है।
नोड्स की लागत एक प्रायोरिटी क्यू में स्टोर की जाती है। इससे बेस्ट-फर्स्ट सर्च का कार्यान्वयन ब्रेडथ फर्स्ट सर्च के समान ही हो जाता है। हम प्रायोरिटीक्यू का उपयोग ठीक वैसे ही करेंगे जैसे हम BFS के लिए क्यू का उपयोग करते हैं।
बेस्ट फर्स्ट सर्च लागू करने के लिए एल्गोरिदम
चरण 1: एक प्रायोरिटीक्यू pqueue बनाएं।
चरण 2: pqueue में 'start' इन्सर्ट करें: pqueue.insert(start)
चरण 3: pqueue के सभी एलिमेंट्स को एक-एक करके डिलीट करें।
चरण 3.1: यदि, एलिमेंट लक्ष्य है। बाहर निकलें।
चरण 3.2: अन्यथा, पड़ोसियों को ट्रैवर्स करें और नोड को जांचा गया मार्क करें।
चरण 4: अंत। यह एल्गोरिदम क्यू में सबसे छोटे पथ को पहले ट्रैवर्स करेगा। सबसे खराब स्थिति में एल्गोरिदम O(n*logn) समय लेता है।
