स्टेट-स्पेस सर्च
स्टेट-स्पेस सर्च उपलब्ध क्रियाओं के माध्यम से प्रारंभिक स्थिति से प्राप्त होने वाली स्थितियों के समूह का व्यवस्थित अन्वेषण है, ताकि एक ऐसी स्थिति का पता लगाया जा सके जो लक्ष्य परीक्षण को संतुष्ट करती है या उस तक पहुँचने वाले मार्ग का पता लगाया जा सके।
Definition
स्टेट-स्पेस सर्च एक समस्या को एक ग्राफ़ के रूप में मानता है जिसके नोड्स स्थितियाँ हैं और जिसके किनारे क्रियाएँ हैं, और एक निश्चित रणनीति के अनुसार एक सीमा से स्थितियों का विस्तार करके आगे बढ़ता है जब तक कि एक लक्ष्य स्थिति नहीं मिल जाती या स्पेस समाप्त नहीं हो जाता।
Scope
यह विषय एक समस्या को स्टेट स्पेस (स्थितियाँ, क्रियाएँ, संक्रमण मॉडल, लक्ष्य परीक्षण, पथ लागत) के रूप में तैयार करने और उन अनभिज्ञ खोज रणनीतियों को शामिल करता है जो डोमेन-विशिष्ट मार्गदर्शन के बिना इसका अन्वेषण करती हैं: ब्रेड्थ-फर्स्ट, यूनिफ़ॉर्म-कॉस्ट, डेप्थ-फर्स्ट, डेप्थ-लिमिटेड और इटरेटिव-डीपनिंग सर्च। इसमें पूर्णता, इष्टतमता, समय जटिलता और स्थान जटिलता द्वारा इन रणनीतियों का विश्लेषण, और दोहराई गई-स्थिति का पता लगाने के साथ ट्री सर्च और ग्राफ़ सर्च के बीच का अंतर शामिल है। ह्यूरिस्टिक मार्गदर्शन को ह्यूरिस्टिक सर्च और A* पर अलग विषय में वर्णित किया गया है।
Core questions
- एक समस्या को स्थितियों, क्रियाओं, एक संक्रमण मॉडल और एक लक्ष्य परीक्षण के रूप में कैसे दर्शाया जाता है?
- ब्रेड्थ-फर्स्ट, डेप्थ-फर्स्ट, यूनिफ़ॉर्म-कॉस्ट और इटरेटिव-डीपनिंग सर्च अपनी सीमा क्रम में कैसे भिन्न होते हैं?
- प्रत्येक अनभिज्ञ रणनीति की पूर्णता, इष्टतमता, समय और स्थान की क्या गारंटी है?
- ग्राफ़ सर्च उन स्थितियों के व्यर्थ पुनरावृत्ति से कैसे बचता है जिनकी ट्री सर्च अनुमति देता है?
Key concepts
- प्रारंभिक स्थिति और लक्ष्य परीक्षण
- संक्रमण मॉडल और उत्तराधिकारी
- सीमा (खुली सूची) और अन्वेषित सेट
- ब्रेड्थ-फर्स्ट सर्च
- डेप्थ-फर्स्ट सर्च
- यूनिफ़ॉर्म-कॉस्ट सर्च
- इटरेटिव डीपनिंग
- ट्री सर्च बनाम ग्राफ़ सर्च
Key theories
- सीमा क्रम रणनीति निर्धारित करता है
- अनभिज्ञ खोज एल्गोरिदम केवल उस क्रम से भिन्न होते हैं जिसमें वे सीमा से स्थितियों को हटाते हैं: एक FIFO कतार ब्रेड्थ-फर्स्ट देती है, एक LIFO स्टैक डेप्थ-फर्स्ट देता है, और पथ लागत पर एक प्राथमिकता कतार यूनिफ़ॉर्म-कॉस्ट सर्च देती है।
- स्थान-कुशल इष्टतम के रूप में इटरेटिव डीपनिंग
- डेप्थ-फर्स्ट इटरेटिव-डीपनिंग सर्च बढ़ती सीमाओं के साथ डेप्थ-लिमिटेड डेप्थ-फर्स्ट सर्च को बार-बार चलाता है, जो डेप्थ-फर्स्ट सर्च के रैखिक स्थान को ब्रेड्थ-फर्स्ट सर्च की पूर्णता और इष्टतमता (इकाई लागतों पर) के साथ जोड़ता है।
Clinical relevance
अनभिज्ञ स्टेट-स्पेस सर्च पाथफाइंडिंग, पहेली सुलझाने, मॉडल चेकिंग में पहुंच योग्यता विश्लेषण के लिए वैचारिक और कार्यान्वयन आधार है, और उस आधार के रूप में जिस पर ह्यूरिस्टिक और एडवर्सरियल सर्च का निर्माण होता है; इसकी जटिलता को समझना यह मार्गदर्शन करता है कि ब्लाइंड सर्च कब संभव है बनाम कब ह्यूरिस्टिक्स की आवश्यकता होती है।
History
व्यवस्थित स्टेट-स्पेस सर्च 1950 के दशक के ग्राफ़-ट्रैवर्सल एल्गोरिदम से उत्पन्न हुआ है, जिसमें मूर और डिज्कस्ट्रा का सबसे छोटा-पथ कार्य शामिल है, और इसे प्रारंभिक AI में समस्या-समाधान के एक मॉडल के रूप में तैयार किया गया था। कोर्फ के 1985 के इटरेटिव-डीपनिंग के विश्लेषण ने रैखिक स्थान के साथ स्वीकार्य ट्री सर्च के बीच इसकी इष्टतमता स्थापित की।
Key figures
- Nils J. Nilsson
- Richard E. Korf
- Edward F. Moore
- Edsger W. Dijkstra
Related topics
Seminal works
- nilsson1971
- russell2020
Frequently asked questions
- ब्रेड्थ-फर्स्ट सर्च कब इष्टतम होता है?
- ब्रेड्थ-फर्स्ट सर्च तब इष्टतम होता है जब प्रत्येक चरण की लागत समान होती है, क्योंकि यह सबसे उथले लक्ष्य को पहले पाता है। जब चरण लागत भिन्न होती है, तो यूनिफ़ॉर्म-कॉस्ट सर्च (जो संचित पथ लागत द्वारा सीमा को क्रमबद्ध करता है) वह अनभिज्ञ रणनीति है जो न्यूनतम-लागत समाधान की गारंटी देती है।
- सादे ब्रेड्थ-फर्स्ट सर्च के बजाय इटरेटिव डीपनिंग का उपयोग क्यों करें?
- ब्रेड्थ-फर्स्ट सर्च पूरी सीमा को संग्रहीत करता है और गहराई में घातीय मेमोरी की आवश्यकता हो सकती है। इटरेटिव डीपनिंग बढ़ती गहराई सीमाओं के साथ बार-बार डेप्थ-फर्स्ट सर्च करता है, केवल रैखिक मेमोरी का उपयोग करता है जबकि अभी भी इकाई-लागत समस्याओं पर पूर्ण और इष्टतम होता है, उथले नोड्स को फिर से विस्तारित करने की लागत पर।