ग्रिड में सर्वश्रेष्ठ पथ

Question

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

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

यदि आपके पास कोई समस्या है कि इस समस्या या अन्य एल्गोरिदम से कैसे संपर्क किया जाए जो अधिक उपयुक्त होगा तो मैं सहायता की सराहना करता हूं। धन्यवाद।

Answer 1

में यदि आप अभी भी इस समस्या पर फंस गए हैं, क्योंकि अन्य उत्तरों/टिप्पणियां केवल आपको आंशिक उत्तर देती हैं - यहां समस्या स्थान पर एक दरार है।

आप वास्तव में एक (ज्यादातर) अनॉर्डर एम पॉइंट पथ को कैप्चर करने के लिए कुछ संशोधनों के साथ ए * का उपयोग कर सकते हैं। केवल उन्हीं चीजों को बदलने की जरूरत है जो ह्युरिस्टिक और समाप्ति मानदंड हैं।

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

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

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

अब, एक बार आपके पास एम पॉइंट पथ हैं जो बाधाओं के बिना सबसे तेज़ होंगे, आप उस पथ के प्रत्येक बिंदु और आपकी वर्तमान स्थिति को ह्युरिस्टिक के रूप में यूक्लिडियन दूरी का उपयोग कर सकते हैं। यह एक लालची आंदोलन अनुमान है, इसलिए यह हमेशा स्वीकार्य है (आप अनुमानित लागत को हरा नहीं सकते हैं) और यह सुसंगत है क्योंकि आप अगले लालची इष्टतम बिंदु से दूर नहीं जा सकते हैं और अपनी लागत कम कर सकते हैं क्योंकि वर्तमान टाइल से अलग लालची बिंदु चुनना स्वीकार्य नहीं होगा।

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

Answer 2

जब आप गहराई X की परत पर हैं, तो आप अपने ग्राफ में परत जोड़ सकते हैं -> आपने कम से कम X अंक एकत्र किए हैं। ऊपरी परत से अपने ग्राफ पर उपयुक्त किनारों को +N पर ले जाएं जहां N वर्तमान टाइल पर बिंदुओं की संख्या है।

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

आपको स्तर >M पर खत्म करना चाहिए।

आप कुछ स्पष्टीकरण की जरूरत है, पूछने =)

संपादित

रूप @Pyrce कहा कि तुम भी Consisten अनुमानी प्रदान करना चाहिए अगर आप का उपयोग करने के लिए एक योजना बना रहे हैं * http://en.wikipedia.org/wiki/Consistent_heuristic