सर्वोत्तम-प्रथम खोज
बेस्ट-फर्स्ट सर्च खोज एल्गोरिदम का एक वर्ग है, जो एक निर्दिष्ट नियम के अनुसार चुने गए सबसे आशाजनक नोड का विस्तार करके एक ग्राफ (डेटा संरचना) का पता लगाता है।
जुडिया पर्ल ने अनुमानी मूल्यांकन फ़ंक्शन द्वारा नोड एन के वादे का अनुमान लगाने के रूप में सबसे अच्छी पहली खोज का वर्णन किया जो, सामान्य तौर पर, n के विवरण, लक्ष्य के विवरण, उस बिंदु तक खोज द्वारा एकत्र की गई जानकारी और सबसे महत्वपूर्ण बात, समस्या डोमेन के बारे में किसी भी अतिरिक्त ज्ञान पर निर्भर हो सकता है।[1][2] कुछ लेखकों ने विशेष रूप से अनुमानी कार्य के साथ एक खोज को संदर्भित करने के लिए सर्वोत्तम-पहली खोज का उपयोग किया है जो यह अनुमान लगाने का प्रयास करता है कि पथ का अंत समाधान (या, लक्ष्य) के कितना करीब है, ताकि जिन पथों को समाधान (या, लक्ष्य) के करीब माना जाता है उन्हें पहले बढ़ाया जाए। इस विशिष्ट प्रकार की खोज को लालची एल्गोरिथम सर्वोत्तम-प्रथम खोज कहा जाता है[2]या शुद्ध अनुमानी खोज।[3] विस्तार के लिए वर्तमान सर्वोत्तम उम्मीदवार का कुशल चयन आमतौर पर प्राथमिकता कतार का उपयोग करके कार्यान्वित किया जाता है।
ए* खोज एल्गोरिदम बी* की तरह सर्वोत्तम-प्रथम खोज एल्गोरिदम का एक उदाहरण है। बेस्ट-फर्स्ट एल्गोरिदम का उपयोग अक्सर संयुक्त खोज में पथ खोजने के लिए किया जाता है। न तो ए* और न ही बी* एक लालची सर्वोत्तम-पहली खोज है, क्योंकि वे लक्ष्य की अनुमानित दूरी के अलावा शुरुआत से दूरी को भी शामिल करते हैं।
लालची बीएफएस
एक लालची एल्गोरिदम का उपयोग करके, माता-पिता के पहले उत्तराधिकारी का विस्तार करें। उत्तराधिकारी उत्पन्न होने के बाद:[4]
- यदि उत्तराधिकारी का अनुमान उसके माता-पिता से बेहतर है, तो उत्तराधिकारी को कतार के सामने सेट किया जाता है (पैरेंट को सीधे उसके पीछे डाला जाता है), और लूप पुनरारंभ होता है।
- अन्यथा, उत्तराधिकारी को कतार में डाला जाता है (उसके अनुमानी मूल्य द्वारा निर्धारित स्थान पर)। प्रक्रिया माता-पिता के शेष उत्तराधिकारियों (यदि कोई हो) का मूल्यांकन करेगी।
नीचे इस एल्गोरिदम का एक छद्मकोड उदाहरण है, जहां कतार एक प्राथमिकता कतार का प्रतिनिधित्व करती है जो लक्ष्य से उनकी अनुमानी दूरी के आधार पर नोड्स का आदेश देती है। यह कार्यान्वयन विज़िट किए गए नोड्स का ट्रैक रखता है, और इसलिए इसका उपयोग ग्राफ़ (अलग गणित)#अप्रत्यक्ष ग्राफ़ के लिए किया जा सकता है। पथ को पुनः प्राप्त करने के लिए इसे संशोधित किया जा सकता है।
प्रक्रिया जीबीएस (प्रारंभ, लक्ष्य) है:
प्रारंभ को विज़िट के रूप में चिह्नित करें
कतार में प्रारंभ जोड़ें
जबकि कतार खाली नहीं है, यह करें:
current_node ← लक्ष्य से न्यूनतम दूरी के साथ कतार का शीर्ष
कतार से current_node हटाएँ
current_node के foreach पड़ोसी n करें:
यदि n विज़िट में नहीं है तो:
यदि n लक्ष्य है:
वापसी एन
अन्य:
n को विज़िट के रूप में चिह्नित करें
कतार में n जोड़ें
वापसी विफलता
यह भी देखें
- बीम खोज
- ए* खोज एल्गोरिदम
- डिज्क्स्ट्रा का एल्गोरिदम
संदर्भ
- ↑ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
- ↑ 2.0 2.1 Russell, Stuart J.; Norvig, Peter. (2021). Artificial Intelligence: A Modern Approach (4th ed.). Hoboken: Pearson. pp. 73–74. ISBN 9780134610993. LCCN 20190474.
- ↑ Korf, Richard E. (1999). "कृत्रिम बुद्धिमत्ता खोज एल्गोरिदम". In Atallah, Mikhail J. (ed.). Handbook of Algorithms and Theory of Computation. CRC Press. ISBN 0849326494.
- ↑ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon