खोज और समस्या-समाधान
खोज और समस्या-समाधान कृत्रिम बुद्धिमत्ता की वह शाखा है जो कार्यों को अवस्थाओं या विन्यासों के अन्वेषण के रूप में तैयार करने और लक्ष्यों तक पहुँचने वाले कार्यों, असाइनमेंट या चालों के अनुक्रमों को खोजने से संबंधित है।
Definition
खोज-आधारित समस्या-समाधान एक कार्य को प्रारंभिक अवस्था, अवस्थाओं को बदलने वाले कार्यों का एक सेट, एक लक्ष्य परीक्षण और एक पथ लागत के रूप में प्रस्तुत करता है, और एक लक्ष्य अवस्था (या उस तक पहुँचने का सबसे कम लागत वाला पथ) मिलने तक व्यवस्थित रूप से पहुँच योग्य अवस्थाओं का अन्वेषण करके इसे हल करता है।
Scope
यह क्षेत्र समस्याओं को अवस्था स्थानों के रूप में तैयार करने और उनका अन्वेषण करने वाले एल्गोरिदम को शामिल करता है: जैसे कि अनभिज्ञ (अंधा) खोज (जैसे कि ब्रेड्थ-फर्स्ट और डेप्थ-फर्स्ट), सूचित (अनुमानी) खोज (जैसे कि A* और ग्रीडी बेस्ट-फर्स्ट), दो-खिलाड़ियों वाले खेलों के लिए प्रतिकूल खोज, और बाधा संतुष्टि। यह बताता है कि समस्याओं को अवस्थाओं, कार्यों और लक्ष्य परीक्षणों के रूप में कैसे मॉडल किया जाता है, और पूर्णता, इष्टतमता, समय और स्थान का विश्लेषण कैसे किया जाता है। इसमें डेटा से खोज अनुमानी या मूल्यांकन कार्यों को सीखना शामिल नहीं है, जो मशीन-लर्निंग के एक अलग उपक्षेत्र से संबंधित है।
Sub-topics
Core questions
- वास्तविक दुनिया के कार्य को अवस्थाओं, कार्यों और एक लक्ष्य परीक्षण के साथ एक अवस्था स्थान के रूप में कैसे तैयार किया जाता है?
- एक खोज एल्गोरिथम कब पूर्ण (यदि कोई समाधान मौजूद है तो उसे खोजने की गारंटी) और इष्टतम (सबसे कम लागत वाला समाधान खोजने की गारंटी) होता है?
- एक अनुमानी कार्य इष्टतमता को बनाए रखते हुए खोज को लक्ष्य की ओर कैसे निर्देशित करता है?
- अवस्था स्थान के संयोजनात्मक विस्फोट को छंटनी या सूचित क्रम से कैसे नियंत्रित किया जा सकता है?
- जब कोई विरोधी कुछ चालें चुन रहा हो तो खोज कैसे बदल जाती है?
Key concepts
- अवस्था स्थान
- खोज वृक्ष और खोज ग्राफ
- अनभिज्ञ (अंधा) खोज
- अनुमानी कार्य
- स्वीकार्यता और संगति
- A* खोज
- ब्रांचिंग फैक्टर और खोज गहराई
- पूर्णता और इष्टतमता
- बाधा संतुष्टि
Key theories
- स्वीकार्य अनुमानी और A* इष्टतमता
- यदि कोई अनुमानी लक्ष्य तक की वास्तविक लागत को कभी भी अधिक अनुमानित नहीं करता है (स्वीकार्य है), तो A* खोज f = g + h के सर्वोत्तम-प्रथम क्रम में नोड्स का विस्तार करती है और एक इष्टतम समाधान वापस करने की गारंटी देती है; संगति अतिरिक्त रूप से यह गारंटी देती है कि कोई नोड फिर से विस्तारित नहीं होता है।
- अनभिज्ञ बनाम सूचित खोज व्यापार-बंद
- अंधे रणनीतियाँ (ब्रेड्थ-फर्स्ट, यूनिफ़ॉर्म-कॉस्ट, डेप्थ-फर्स्ट, इटरेटिव डीपनिंग) केवल नोड ऑर्डरिंग में भिन्न होती हैं और डोमेन ज्ञान के बिना गारंटी प्रदान करती हैं, जबकि शेष लागत के अनुमानी अनुमान अनुमानी के अस्वीकार्य होने पर इष्टतमता खोने के जोखिम पर अन्वेषित स्थान को नाटकीय रूप से कम कर सकते हैं।
- अवस्था-स्थान खोज के रूप में समस्या सूत्रीकरण
- कार्यों से जुड़ी अवस्थाओं पर खोज के रूप में एक बार डाले जाने पर कार्यों की एक विस्तृत श्रृंखला साध्य हो जाती है, जिससे अवस्था प्रतिनिधित्व और ऑपरेटरों का चुनाव एक केंद्रीय डिजाइन निर्णय बन जाता है जो ब्रांचिंग फैक्टर और समाधान गहराई को निर्धारित करता है।
Clinical relevance
खोज व्यावहारिक प्रणालियों की एक विशाल श्रृंखला का आधार है: मार्ग योजना और नेविगेशन (सड़क नेटवर्क पर A*), पहेली और गेम इंजन, स्वचालित विन्यास और शेड्यूलिंग, रोबोट गति योजना, और लॉजिस्टिक्स और संचालन अनुसंधान में उपयोग किए जाने वाले स्वचालित नियोजन और बाधा समाधानकर्ताओं की रीढ़ के रूप में।
History
खोज अपने शुरुआती दिनों से ही AI के केंद्र में थी, जिसमें न्यूवेल और साइमन के जनरल प्रॉब्लम सॉल्वर (1950 के दशक के अंत में) ने बुद्धिमत्ता को समस्या स्थानों के माध्यम से खोज के रूप में प्रस्तुत किया था। A* एल्गोरिथम (हार्ट, निलसन, राफेल, 1968) ने अनुमानी खोज को एक कठोर इष्टतमता आधार दिया, और पर्ल के 1984 के मोनोग्राफ ने अनुमानी खोज सिद्धांत को व्यवस्थित किया। यह ढाँचा AI पाठ्यपुस्तकों में एक मानक संगठनात्मक लेंस बना हुआ है।
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- अनभिज्ञ और सूचित खोज में क्या अंतर है?
- अनभिज्ञ (अंधा) खोज, जैसे कि ब्रेड्थ-फर्स्ट या डेप्थ-फर्स्ट खोज, इस बारे में कोई जानकारी का उपयोग नहीं करती है कि कोई अवस्था लक्ष्य के कितनी करीब है और पूरी तरह से अवस्था स्थान की संरचना द्वारा अन्वेषण करती है। सूचित (अनुमानी) खोज लक्ष्य तक की शेष लागत के अनुमान का उपयोग करती है ताकि यह प्राथमिकता दी जा सके कि किन अवस्थाओं का विस्तार करना है, जो कहीं अधिक कुशल हो सकता है।
- A* का इतना व्यापक रूप से उपयोग क्यों किया जाता है?
- A* शुरुआत से वास्तविक लागत (g) को लक्ष्य तक के अनुमानी अनुमान (h) के साथ जोड़ता है, और जब अनुमानी स्वीकार्य होता है तो यह एक इष्टतम समाधान खोजने की गारंटी देता है जबकि आमतौर पर अनभिज्ञ खोज की तुलना में बहुत कम अवस्थाओं का अन्वेषण करता है। इष्टतमता और दक्षता का यह संतुलन इसे पथ-खोज के लिए एक डिफ़ॉल्ट विकल्प बनाता है।