ए * मैनहट्टन दूरी

Question

मैंने ए * के एल्गोरिदम/छद्म कोड की खोज की और मैंने इसका अनुसरण किया और इसे कोड किया। मैंने एच (एन) के लिए मैनहट्टन दूरी का उपयोग किया। (च (एन) = जी (एन) + h (एन)) और यह परिणाम है,

यह हमेशा होता है जब कोई रास्ता नहीं अवरुद्ध दीवारें हैं, लेकिन जब मैं एक बहुत डाल दीवारों का, ऐसा लगता है कि यह सबसे छोटा रास्ता ले रहा है। क्या यह सबसे छोटा रास्ता है? मेरा मतलब है कि यह नीचे क्यों नहीं है?

यह भी ए * मैनहट्टन है, और उनके पास एक ही आकार (1 9 x 9 1) है। यह http://qiao.github.com/PathFinding.js/visual/

Answer 1

दोनों पथों में एक ही मैनहट्टन दूरी है। इसलिए, यह कार्यान्वयन निर्भर है कि कौन सा पथ चुना जाता है। यह बताने के लिए कि यह विशिष्ट हिस्सा क्यों चुना गया था, हमें इस विशिष्ट ए * कार्यान्वयन के कोड को देखना होगा।

संकेत: स्रोत से प्रत्येक पथ केवल Von Neumann neighborhood (यानी, तिरछे नहीं चलता) का उपयोग करता है और "गलत" दिशा में कोई कदम नहीं उठाता है (यानी, कभी भी आपके उदाहरण में नहीं चलता या छोड़ दिया जाता है) एक ही मैनहट्टन दूरी है। इसलिए, यदि आप न्यूयॉर्क में हैं, तो इससे कोई फर्क नहीं पड़ता कि मैनहट्टन में एक निश्चित स्थान तक पहुंचने के लिए आप किन किनारे पर जाते हैं :)

Answer 2

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

Answer 3

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

पहली पंक्ति: प्रारंभ ---------> एस + N (से पहले अवरुद्ध बिंदु)

दूसरा/मध्य लाइन/एस: अवरोधित प्वाइंट ------ ----> एस + एन (एक और अवरुद्ध बिंदु से पहले) दोबारा दोहराएं (नई लाइन/सेगमेंट) जब तक कि यह लक्ष्य तक एक रेखा-दृष्टि की दृष्टि न हो।

अंतिम पंक्ति: अवरोधित प्वाइंट -------------> लक्ष्य

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