अनुमानी खोज और A*

अनुमानी खोज लक्ष्य तक पहुंचने के लिए शेष लागत के समस्या-विशिष्ट अनुमान का उपयोग करती है ताकि यह मार्गदर्शन किया जा सके कि किन अवस्थाओं का पहले अन्वेषण किया जाए; A* इसका प्रामाणिक एल्गोरिथम है, जो अब तक की लागत और शेष लागत के अनुमान के योग के क्रम में अवस्थाओं का विस्तार करता है।

Definition

अनुमानी खोज एक सूचित खोज है जो ज्ञात लागत को प्रारंभ से शेष लागत के अनुमानी अनुमान के साथ जोड़कर एक मूल्यांकन फ़ंक्शन का उपयोग करके सीमा को व्यवस्थित करती है; A* f(n) = g(n) + h(n) का उपयोग करता है और जब h स्वीकार्य होता है तो इष्टतम होता है।

Scope

यह विषय सूचित (अनुमानी) खोज रणनीतियों को शामिल करता है, जो सर्वोत्तम-प्रथम खोज और A* एल्गोरिथम पर केंद्रित है, जिसमें अनुमानी कार्यों (स्वीकार्यता, संगति/एकदिष्टता) का डिज़ाइन और गुण, ये गुण प्रदान करने वाली इष्टतमता और दक्षता की गारंटी, और पुनरावृत्ति-गहनता A* (IDA*) जैसे स्मृति-बाधित प्रकार शामिल हैं। यह बताता है कि अनुमान कैसे निर्मित होते हैं (शिथिल समस्याएं, पैटर्न डेटाबेस) और वे सटीकता को गणना के साथ कैसे व्यापार करते हैं। डेटा से अनुमान सीखना मशीन-लर्निंग उपक्षेत्र से संबंधित है।

Core questions

• एक अनुमान को स्वीकार्य क्या बनाता है, और स्वीकार्यता A* इष्टतमता की गारंटी क्यों देती है?
• संगति (एकदिष्टता) गारंटी को कैसे मजबूत करती है और नोड के पुनर्वितरण को कैसे रोकती है?
• अच्छे अनुमान कैसे डिज़ाइन किए जाते हैं, उदाहरण के लिए समस्या के शिथिल संस्करणों से?
• IDA* जैसे स्मृति-बाधित प्रकार सीमित स्थान के साथ इष्टतमता को कैसे बनाए रखते हैं?

Key concepts

• मूल्यांकन फ़ंक्शन f = g + h
• स्वीकार्य अनुमान
• सुसंगत (एकदिष्ट) अनुमान
• लालची सर्वोत्तम-प्रथम खोज
• A* खोज
• पुनरावृत्ति-गहनता A* (IDA*)
• अनुमानी प्रभुत्व
• शिथिल समस्या और पैटर्न डेटाबेस

Key theories

स्वीकार्य अनुमानों के तहत A* इष्टतमता

जब अनुमान h कभी भी वास्तविक शेष लागत का अधिक अनुमान नहीं लगाता है, तो A* f = g + h को बढ़ाकर नोड्स का विस्तार करता है और सबसे कम लागत वाला पथ वापस करने की गारंटी देता है; समान अनुमानी जानकारी का उपयोग करने वाले एल्गोरिदम में, A* इष्टतम रूप से कुशल है।

शिथिलीकरण के माध्यम से अनुमानी डिज़ाइन

स्वीकार्य अनुमानों को समस्या के एक शिथिल संस्करण (कार्यों पर कम प्रतिबंधों के साथ) को हल करके व्यवस्थित रूप से प्राप्त किया जा सकता है, क्योंकि एक आसान समस्या की सटीक लागत मूल पर एक निचली सीमा है; प्रभावी (अधिक सूचित) अनुमान कम नोड्स का विस्तार करते हैं।

स्मृति-बाधित अनुमानी खोज

पुनरावृत्ति-गहनता A* बढ़ती f-लागत सीमा से बंधे क्रमिक गहराई-प्रथम खोज करता है, जो समाधान की गहराई में रैखिक स्मृति के साथ A*-जैसी इष्टतमता प्राप्त करता है।

Clinical relevance

अनुमानी खोज मानचित्रों और खेलों में मार्ग खोजने, रोबोटिक्स में गति नियोजन, और स्वचालित योजनाकारों और पहेली हल करने वालों के अंदर खोज इंजनों को शक्ति प्रदान करती है; अनुमानी डिज़ाइन की व्यावहारिक कला सीधे यह निर्धारित करती है कि बड़ी समस्याएं स्वीकार्य समय में हल करने योग्य हैं या नहीं।

History

A* एल्गोरिथम को हार्ट, नील्सन और राफेल (1968) द्वारा प्रस्तुत किया गया था, जिसने अनुमानी खोज को एक औपचारिक इष्टतमता आधार दिया। पर्ल के 1984 के मोनोग्राफ 'हेयुरिस्टिक्स' ने निश्चित सैद्धांतिक उपचार प्रदान किया, और कोर्फ के 1985 के IDA* ने A* की स्मृति लागत को संबोधित किया। ये परिणाम AI शिक्षा में मुख्य सामग्री बने हुए हैं।

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

एक स्वीकार्य अनुमान क्या है?

एक अनुमान स्वीकार्य होता है यदि वह किसी भी अवस्था से लक्ष्य तक पहुंचने की वास्तविक लागत का कभी भी अधिक अनुमान नहीं लगाता है। स्वीकार्यता वह शर्त है जिसके तहत A* को एक इष्टतम (सबसे कम लागत वाला) समाधान खोजने की गारंटी दी जाती है।

लालची सर्वोत्तम-प्रथम खोज और A* में क्या अंतर है?

लालची सर्वोत्तम-प्रथम खोज उस अवस्था का विस्तार करती है जो केवल अनुमान (h) के अनुसार लक्ष्य के सबसे करीब दिखाई देती है, जो तेज़ है लेकिन इष्टतम से बहुत दूर हो सकती है। A* अब तक हुई वास्तविक लागत (g) को जोड़ता है, f = g + h द्वारा विस्तार करता है, जो अनुमान स्वीकार्य होने पर इष्टतमता को बनाए रखता है।