मैं एक स्रोत वर्टेक्स (एस) से एक गंतव्य वर्टेक्स (डी) तक एक लूपलेस पथ (अधिमानतः सबसे छोटा पथ, लेकिन जरूरी नहीं) खोजने का एक तरीका ढूंढ रहा हूं जो ग्राफ़ में कहीं किसी अन्य विशिष्ट वर्टेक्स (एक्स) से गुज़रता है।

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

मैंने जो कोशिश की वह येन के के सबसे छोटे पथ एल्गोरिदम के परिणामों में ऐसे पथों की तलाश करने का एक बेवकूफ प्रयास था। लेकिन मुझे उम्मीद है कि ऐसा करने का एक और अधिक कुशल और निश्चित तरीका है।

फिर, केवल इसे इंगित करने के लिए, मैं जरूरी नहीं कि एस से डी के माध्यम से एक्स के लिए सबसे छोटा रास्ता ढूंढ रहा हूं, लेकिन बस कोई लूपलेस पथ, हालांकि सबसे छोटा रास्ता बेहतर होगा।

0
Akshay Madan 17 जिंदा 2020, 02:12

1 उत्तर

सबसे बढ़िया उत्तर

मूल अवधारणा काफी सरल है; फिर आप उन मामलों के लिए अनुकूल हो जाते हैं जो अपने सबसे छोटे शेष पथों पर X में और बाहर लूप करते हैं।

  • ग्राफ़ से D को हटा दें।
  • P1, S से X तक का सबसे छोटा रास्ता खोजें।
  • D को ग्राफ़ पर पुनर्स्थापित करें।
  • P1 में सभी नोड्स हटा दें।
  • P2, X से D तक का सबसे छोटा रास्ता खोजें।
  • वापसी P1 + P2

यही समाधान का सार है।

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

जब आपको पहली बार P1 मिले, तो जांच लें कि आप जिस नोड का उपयोग करने वाले हैं, वह यात्रा के दूसरे चरण में X को D से अलग नहीं करेगा। यह आपको बहुत तेज़ खोज एल्गोरिथम देगा।

क्या यह एक शुरुआत के लिए पर्याप्त है?


अनुकूलन की आवश्यकता इस तरह के एक मामले से आती है - ग्राफ पर विचार करें

src  dst
 S    1, 2
 1    X, D
 2    D
 X    1

आपके आंशिक पथ हैं

S -> 1 -> X
S -> 2 -> 3 -> X
X -> 1 -> D
and, incidentally,
S -> 1 -> D

जब आप अपनी सबसे छोटी-पथ खोज चलाते हैं, तो आपको पथ S 1 X 1 D मिलता है, जो लूप के कारण अस्वीकृत हो जाता है। जब आप मेरा पहला संशोधन लागू करते हैं - पथ X to D खोजने का प्रयास करते समय नोड 1 हटा दें, कोई शेष पथ नहीं है।

एल्गोरिथम को X 2 3 D खोजने के लिए पथ X 1 D को अस्वीकार करते हुए बैकअप लेने की क्षमता की आवश्यकता होती है। वह कोडिंग है जो विवरण से तुरंत स्पष्ट नहीं होती है।

यहां आपके लिए एक मानसिक व्यायाम है: क्या ऐसा ग्राफ बनाना संभव है जिसमें प्रत्येक सबसे छोटा पथ (S to X और X to D) दूसरे टर्मिनल नोड को X से अलग करता है ? ऊपर दिए गए मेरे उदाहरण में, आप बस प्रक्रिया को बदल सकते हैं: जब S to X पथ D को अलग करता है, तो फिर से शुरू करें: पहले X to D ढूंढें, नोड निकालें 1, और फिर शेष ग्राफ़ में S to X ढूंढें। क्या आप कोई ऐसा ग्राफ ढूंढ सकते हैं जहां यह स्विच काम न करे?

यदि नहीं, तो आपके पास तत्काल समाधान है। यदि हां, तो आपके पास संभालने के लिए एक अधिक जटिल मामला है।

3
Prune 17 जिंदा 2020, 17:16