राज्य अंतरिक्ष खोज

हम Technopark Mail.ru Konstantin Anisimovich - ABBYY में प्रौद्योगिकी विकास के निदेशक के एक भाषण पर आधारित कृत्रिम बुद्धिमत्ता के बारे में पदों की एक श्रृंखला जारी रखते हैं। दूसरा लेख खोज एल्गोरिदम के लिए समर्पित होगा।


ज्ञान को प्रस्तुत करने के किस तरीके पर निर्भर करता है - घोषणा या उत्पादन - हम ज्ञान को लागू करने का तरीका निर्धारित करते हैं। उत्पादन प्रणाली के साथ सब कुछ काफी सरल है: हम सीधे उत्पादों की व्याख्या करते हैं।

यदि हम ज्ञान का एक घोषणात्मक प्रतिनिधित्व चुनते हैं, तो सब कुछ थोड़ा और अधिक जटिल होता है। ऐसा करने के लिए, हमें राज्य स्थान में एक खोज को लागू करने की आवश्यकता है । तथ्य यह है कि ज्ञान के संरचित प्रतिनिधित्व को व्यवस्थित रूप से व्यवस्थित किया जाता है। और यदि हम इनपुट डेटा में एक पदानुक्रमित विवरण लागू करने का प्रयास करते हैं, तो प्रत्येक स्तर पर हमें डेटा की संभावित व्याख्याएं मिलेंगी - परिकल्पना।

प्रभावी ढंग से एक या एक से अधिक सर्वोत्तम परिकल्पनाओं का चयन करने के लिए, एक दहनशील विस्फोट से बचने के लिए, राज्य-स्थान खोज एल्गोरिदम का उपयोग किया जाता है।

राज्य का स्थान तब उत्पन्न होता है जब समस्या का समाधान अलग-अलग चरणों में विभाजित होता है। यहाँ हम प्रारंभिक अवस्था में अंतर करते हैं जब हमने अभी तक एक परिकल्पना को नहीं चुना है, साथ ही अंतिम अवस्था को जब हमने एक परिकल्पना को पाया जो हमारी समस्या का एक स्वीकार्य समाधान है। इस परिकल्पना की खोज की प्रक्रिया में, अगले राज्य में संक्रमण के संचालन होते हैं। यह ध्यान देना मुश्किल नहीं है कि स्थानिक अवस्था में संख्यात्मक चरणों के आधार पर घातीय जटिलता है। यदि कोई पूरे राज्य के अंतरिक्ष में जाना चाहता है, तो घातांक समय की आवश्यकता है।

इस समस्या से बचने के लिए, विभिन्न खोज एल्गोरिदम लागू किए जाते हैं। वे दो प्रकारों में विभाजित हैं - संपूर्ण खोज और अनुमानी खोज। जैसा कि यह पहले से ही स्पष्ट है, अधिकांश मामलों में व्यापक खोज अच्छी नहीं है (जब तक कि हम बहुत छोटी समस्या को हल नहीं करते), लेकिन इसका कुछ शैक्षिक मूल्य है। इसलिए, हम पहले इस पर विचार करेंगे, और आप, यदि आप इससे परिचित हैं, तो तुरंत हेयुरिस्टिक प्रकार पर स्विच कर सकते हैं।

फुल ब्रूट सर्च

निम्न प्रकार की संपूर्ण खोज हैं : चौड़ाई-पहली खोज, गहराई-पहली खोज और पुनरावृत्ति-गहरी खोज।
चौड़ाई-पहली खोज के दौरान, हम प्रारंभिक अवस्था के स्थानिक स्थिति में सभी संभव कदम उठाते हैं और राज्यों का एक नया सेट प्राप्त करते हैं। इस सेट के प्रत्येक राज्य से आगे हम फिर से सभी संभव कदम उठाते हैं, हम राज्यों का अगला सेट प्राप्त करते हैं, और इसी तरह - जब तक हम कोई समाधान नहीं निकालते। रेखीय रूप से, एक चौड़ाई-पहली खोज को राज्य अंतरिक्ष में एक फ्रंट आंदोलन के रूप में दर्शाया जा सकता है।

एक गहरी खोज का मतलब है कि हम प्रारंभिक अवस्था से एक कदम उठाते हैं, फिर हम नए राज्य आदि से एक और कदम उठाते हैं, जब तक कि हम अंतिम अवस्था या उस अवस्था तक नहीं पहुंच जाते हैं जहां से कोई कदम नहीं उठाया जा सकता है। इस मामले में, हम पुनरावर्ती रूप से वापस जाते हैं और फिर से उस अवस्था से कदम उठाते हैं, जब तक हम कोई हल नहीं निकालते।
यह देखना आसान है कि इस तरह की चौड़ाई पहली खोज में समय और स्मृति दोनों में घातीय जटिलता है। और गहरी खोज में घातीय समय जटिलता है। बेशक, हम भाग्यशाली हो सकते हैं, और एक समाधान तुरंत मिल जाएगा, लेकिन व्यवहार में यह संभावना नहीं है।

एक पुनरावृत्त गहरी खोज गहराई और चौड़ाई खोज का अनुकूलन है, जो घातीय जटिलता से बचने के लिए, प्रारंभिक अवस्था के निकटतम समाधान खोजने की गारंटी है। यह एल्गोरिथ्म कैसे लागू किया गया है? हम निरंतर एन की गहराई सीमा के साथ गहराई में देख रहे हैं। एक समाधान मिला - अच्छा। नहीं मिला - निरंतर एन + 1 के साथ गहराई की खोज को दोहराएं और जब तक यह नहीं मिलता है। यह एल्गोरिदम, हालांकि लागू करने के लिए सरल है, केवल सबसे सरल कार्यों के लिए उपयुक्त है।

हेयुरिस्टिक सर्च

सबसे अधिक बार, व्यावहारिक कार्यों को ह्यूरिस्टिक खोज का उपयोग करके हल किया जाता है। हेयुरिस्टिक खोज एक राज्य मूल्यांकन समारोह पर आधारित है। संपूर्ण खोज एल्गोरिदम के विपरीत, हेयुरिस्टिक खोज उनके "संभावना" के आधार पर स्थानिक राज्यों की रैंकिंग करने की अनुमति देती है। संपूर्ण खोज एल्गोरिदम की तुलना में राज्य के स्थान में अनुमानी खोज अधिक उद्देश्यपूर्ण तरीके से खोज करता है। यह महत्वपूर्ण है कि कई समस्याओं में राज्य मूल्यांकन प्रारंभिक अवस्था से इस राज्य को प्राप्त करने के तरीके का सबसे अच्छा अनुमान है। यदि हमारी समस्या में ऐसा मूल्यांकन संभव है, तो हेयुरिस्टिक सर्च एल्गोरिदम को बहुत सरल किया जाता है।

सर्वश्रेष्ठ खोज एल्गोरिदम के मुख्य वर्ग को सर्वोत्तम स्थिति से खोजा जाता है। इसमें तीन मुख्य एल्गोरिदम शामिल हैं: यह लालची खोज, किरण खोज और ए * है। उनका सामान्य विचार एक चरण एक या कई सर्वश्रेष्ठ राज्यों की खोज और चुनने की प्रक्रिया में प्राप्त राज्यों के एक सेट को बनाए रखने पर आधारित है।

उनमें से सबसे सरल एक लालची खोज है । यदि एक ग्राफ में सबसे अच्छा रास्ता खोजने के कार्य पर लागू किया जाता है, तो यह प्रसिद्ध दिक्जस्ट्रा एल्गोरिथ्म का उत्पादन करेगा। लालची खोज, उस राज्य को चुनना जिसमें से खोज जारी रहेगी, राज्य के लिए शुरुआती से पथ के सर्वोत्तम अनुमान के साथ खोज करता है। इसलिए, इसे "लालची" कहा जाता है - क्योंकि यह इस समय सबसे अच्छी स्थिति को "पकड़ लेता है", परिणामों के बारे में नहीं सोच रहा है। स्वाभाविक रूप से, कई लालची एल्गोरिदम की तरह, ऐसी रणनीति से इष्टतम समाधान नहीं होता है। अंतिम अवस्थाएं अक्सर बहुत लंबी, गैर-इष्टतम तरीके से पहुंच जाती हैं। इसके अलावा, लालची खोज को लगातार सभी प्राप्त राज्यों के सेट का समर्थन करना चाहिए, जो बहुत अधिक हो सकता है, यही वजह है कि स्मृति अत्यधिक खर्च होती है।

किरण खोज एल्गोरिथ्म और ए * एल्गोरिथ्म लालची खोज के व्यवहार को सुधारने और इसमें निहित इन दो समस्याओं को ठीक करने का प्रयास करते हैं। रे खोज निम्नानुसार काम करती है: प्रत्येक चरण पर हम कुछ सबसे अच्छे राज्यों का समर्थन करते हैं। इसके बाद, इनमें से प्रत्येक राज्य से हम सभी संभव कदम उठाते हैं और अगली पीढ़ी के कई राज्यों को प्राप्त करते हैं। इस सेट में, हम डुप्लिकेट को हटाते हैं, अर्थात, समान स्थिति। हम शेष लोगों का मूल्यांकन करते हैं और उन्हें बिगड़ने के क्रम में क्रमबद्ध करते हैं। इसके बाद, हम N को सबसे अच्छे से चुनते हैं, और इसी तरह से, जब तक हम हमारे लिए ब्याज की अंतिम स्थिति नहीं पाते हैं।

रे खोज के अपने फायदे और नुकसान हैं। इसका मुख्य नुकसान यह है कि, लालची एक के विपरीत, किरण खोज सर्वोत्तम गुणवत्ता के साथ अंतिम स्थिति को खोजने की गारंटी नहीं देती है, क्योंकि सामने की ओर बढ़ने की प्रक्रिया में, सर्वश्रेष्ठ राज्य इससे बाहर गिर सकता है। व्यवहार में, आप सामने वाले की चौड़ाई को समायोजित करके इससे निपट सकते हैं। सामने वाला जितना संकरा होता है, उतनी ही तेजी से एल्गोरिथ्म काम करता है, लेकिन जितनी बार यह गलत होता है। व्यापक मोर्चा, बेहतर एल्गोरिथ्म, लेकिन लंबे समय तक। यह इसके महत्वपूर्ण लाभों में से एक है - गति और गुणवत्ता के बीच आसानी से संतुलन बनाने की क्षमता। विशेषकर चीनी वैज्ञानिकों के बीच शैक्षणिक वातावरण में रे खोज बहुत लोकप्रिय है। इसे लागू करना आसान है और बहुत अच्छी तरह से काम करता है।

ए * एल्गोरिदम का विचार यह है कि प्रत्येक चरण में हम सबसे अच्छा नहीं चुनते हैं, लेकिन इस समय सबसे अधिक आशाजनक स्थिति है। जिस राज्य से होकर गुजरने की संभावना है, वह एक बेहतर अंतिम स्थिति से गुजरता है।

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

एल्गोरिथ्म ए * का नुकसान ह्यूरिस्टिक्स के साथ आने की आवश्यकता है। निष्पक्षता में, यह कहा जाना चाहिए कि कई समस्याओं में यह अनुमानी काफी आसान और स्वाभाविक है। ऐसे कार्यों में, ए * का उपयोग करने की सिफारिश की जाती है। यदि हेयुरेटिक्स का आविष्कार नहीं किया जा सकता है, तो किरण खोज बचाव में आती है।

इस श्रृंखला की तीसरी पोस्ट में, हम आर्टिफिशियल इंटेलिजेंस बनाने के लिए उपयोग किए जाने वाले ज्ञान को प्राप्त करने के तरीकों पर ध्यान केंद्रित करेंगे, साथ ही मशीन लर्निंग पर - विशेष रूप से, उन तरीकों पर जो फाइनरडर में उपयोग किए जाते हैं।