मेरे पास भूलभुलैया का यह लेआउट है कि मुझे यह सोचने में परेशानी हो रही है कि इसका समाधान कैसे लागू किया जाए:
मुझे पता है कि भूलभुलैया को हल करने के लिए कई संसाधन हैं, उदा। http://www.astrolog.org/labyrnth/algrithm.htm लेकिन मुझे यकीन नहीं है कि कौन सा एल्गोरिथम दिए गए भूलभुलैया के लिए सबसे उपयुक्त है।
"*" लेबल वाले तीन क्षेत्र हैं जो ऐसे स्थान हैं जो मैप के शीर्ष पर प्रवेश द्वार से भूलभुलैया से बाहर निकलने में सक्षम होने से पहले जाने के लिए भूलभुलैयासोलर की आवश्यकता होती है।
मैं हल करने के छद्म कोड की सराहना करता हूंभूलभुलैया द्वीप भाग। मैं एक सरल समाधान की तलाश में रहूंगा और इष्टतम समय वास्तव में एक मुद्दा नहीं है। बात यह है कि भले ही भूलभुलैया का एक दृश्य सॉल्वर को पहले से प्रदान किया गया हो, यह पूरी तरह से सटीक नहीं हो सकता है जब भूलभुलैया सॉल्वर वास्तव में भूलभुलैया करता है, इसलिए यह हाथ से पहले इसे कोड करने या एल्गोरिथ्म का उपयोग करने वाले एल्गोरिथ्म का उपयोग करने की तुलना में थोड़ा अधिक जटिल है चक्रव्यूह और "आधा" मानव / करने के लिए देखने की जरूरत है अगर तुम मुझे क्या मतलब है ...
जबकि रोबोट / रोबोट प्रोग्रामर को प्रत्येक बचाव के लिए खदान के नक्शे के साथ आपूर्ति की जाएगी, नए खनन के कारण या घटना से नुकसान के कारण नक्शा पुराना हो सकता है।
इस एप्लिकेशन के लिए रोबोट को आवश्यक हैसबसे पहले सभी बचाव क्षेत्रों का पता लगाएं और निर्धारित करें कि क्या वे कब्जे में हैं। रोबोट को पूरी तरह से स्वायत्त होना होगा। जब इनकी जांच की गई है तो रोबोट को मनुष्यों के लिए सभी मार्गों की जांच करनी चाहिए।
रोबोट को स्व-नेविगेटिंग भी होना चाहिए। जबकि GPS सिस्टम एक प्राकृतिक विकल्प है, ऐसे में इसका उपयोग किसी भी GPS सिग्नल को रोकने वाली रॉक सीलिंग की मोटाई के कारण नहीं किया जा सकता है, इसलिए आपको रोबोट के लिए नेविगेशन सिस्टम डिज़ाइन करना भी आवश्यक है। इस अंत के लिए, छोटे हार्डवेयर परिवर्तन, जैसे कि अतिरिक्त सेंसर या तैनाती योग्य रेडियो बीकन, को रोबोट में जोड़ा जा सकता है। कृपया ध्यान दें कि आश्रयों में से कम से कम एक "द्वीप" में स्थित है।
उत्तर:
जवाब के लिए 0 № 1यह मानते हुए कि आप भूलभुलैया से बाहर निकलने के लिए सबसे छोटे रास्ते की तलाश नहीं कर रहे हैं - बस किसी भी रास्ते पर, अपने द्वीपों के लिए कुछ क्रम बनाएं: island1,island2,...,islandk.
अब, यह मानते हुए कि आप "नियमित" भूलभुलैया को हल करना जानते हैं, आपको इसके लिए रास्ते तलाशने होंगे:
start->island1, island1->island2, ...., islandk->end
कुछ टिप्पणियां:
- "नियमित" भूलभुलैया का उपयोग करके हल किया जा सकता है BFS, या डीएफएस (हालांकि बाद में इष्टतम नहीं है)।
- यदि आप अधिक कुशल समाधान की तलाश में हैं, तो आप उपयोग कर सकते हैं सब से छोटा रास्ता बजाय कई "नियमित" भूलभुलैया को सुलझाने।
- यदि आप एक छोटे से मार्ग की तलाश कर रहे हैं, तो यह एक बदलाव है यात्रा विक्रेता समस्या। संभावित समाधान पर चर्चा की जाती है यहाँ.
- यदि आप सभी मार्ग से भी गुजरना चाहते हैं, तो आप इसका उपयोग कर सकते हैं डीएफएस जब तक कि सभी नोड्स की खोज नहीं हो जाती है। फिर से, यह "इस तरह का सबसे छोटा रास्ता नहीं होगा, लेकिन सबसे छोटा रास्ता एनपी-हार्ड होने वाला है।
जवाब के लिए 0 № 2
इस समस्या से संबंधित है ट्रैवलिंग सेल्समैन की समस्या समस्या, जो एनपी-हार्ड है, इसलिए मुझे बड़ी संख्या में द्वीपों के लिए किसी भी त्वरित समाधान की उम्मीद नहीं है।
छोटी संख्या में द्वीपों के लिए, आप यह कर सकते हैं: प्रत्येक 2 द्वीपों (आपकी शुरुआती स्थिति सहित) के लिए, उनके बीच सबसे छोटे पथ की गणना करें। चूँकि आप कोने के अपेक्षाकृत कम अंश के बीच की दूरी में दिलचस्पी रखते हैं, इसलिए मैं इसका उपयोग करने की सलाह देता हूँ डिजस्ट्रा के एल्गोरिदम, क्योंकि यह अपेक्षाकृत आसान है और हाथ से किया जा सकता है (यथोचित बड़े ग्राफ के लिए)।
अब आप सभी के बीच सबसे कम दूरी हैरुचि के बिंदु और यह तब है जब आपको उनके बीच हैमिल्टन का इष्टतम मार्ग खोजने की आवश्यकता है। सौभाग्य से, दूरी एक मीट्रिक को संतुष्ट करती है, इसलिए आपके पास 2-सन्निकटन (आसान, हाथ से भी) या 3/2-सन्निकटन (इतना आसान नहीं) एल्गोरिदम हो सकता है, लेकिन कोई बहुपद एल्गोरिथ्म ज्ञात नहीं हैं।
3 द्वीपों के साथ सही समाधान के लिए आपको केवल 6 तरीकों की जांच करनी है कि उन्हें कैसे जाना है (आसान), लेकिन 6 द्वीपों के लिए आप उन्हें 720 तरीकों से देख सकते हैं, और n में n! तो इसके साथ शुभकामनाएँ।