चेबिस्हेव दूरी के साथ डिजस्ट्रा एल्गोरिदम

Question

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

हालांकि चेबिसहेव नोड के किसी भी पक्ष में केवल 1 की लागत के साथ स्थानांतरित हो सकता है, लेकिन कुल लागत पर कोई प्रभाव नहीं पड़ता है, लेकिन ग्राफ के अनुसार, लाल सर्कल, पथ खोजने वाली रेखा बिना ज़िगज़ैग को क्यों चलाती है सीधे चल रहा है?

यदि मैं ए * एल्गोरिदम का उपयोग करता हूं तो वही बात दोहराएगी?

Answer 1

आप प्राथमिकता देने के लिए "सीधी रेखाएं" आप खाते में पिछले चरण की दिशा ले जाना चाहिए चाहते हैं। एक संभावित तरीका ग्राफ G'(V', E') बनाना है जहां V' में सभी पड़ोसी जोड़े हैं। उदाहरण के लिए, vertex v = (v_prev, v_cur) पथ में एक चरम परिभाषित करेगा जहां v_cur पथ का अंतिम चरम है और v_prev पिछला वर्टेक्स है। फिर सबसे कम पथ एल्गोरिदम के "दूरी को अपडेट करना" चरण पर आप सबसे अच्छी (गैर-बदलती) दिशा के साथ सबसे अच्छी दूरी चुन सकते हैं।

इसके अलावा हम एक दिशा बदलने की संख्या के बराबर दूरी पर अतिरिक्त संपत्ति जोड़ सकते हैं और कम से कम दिशा परिवर्तन के साथ न्यूनतम दूरी का रास्ता खोज सकते हैं।

Answer 2

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

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

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