नेटवर्कएक्स

Question

द्वारा "बिडरेक्शनल डिजस्ट्रा" बिडरेक्शनल सर्च (this पर) का उपयोग करके मैंने सबसे कम पथों के लिए डिजस्ट्रा के एल्गोरिदम के नेटवर्कएक्स कार्यान्वयन को पढ़ा है। इस विधि का समापन बिंदु क्या है?

Answer 1

मैं नेटवर्कक्स के कार्यान्वयन पर इसका आधार लगाने जा रहा हूं।

बिडरेक्शनल डिजस्ट्रा बंद हो जाता है जब यह दोनों दिशाओं में एक ही नोड से मुकाबला करता है - लेकिन उस बिंदु पर वह जिस पथ पर लौटता है वह उस नोड के माध्यम से नहीं हो सकता है। यह सबसे कम पथ के लिए सर्वश्रेष्ठ उम्मीदवार को ट्रैक करने के लिए अतिरिक्त गणना कर रहा है।

मैं (this answer पर) अपनी टिप्पणी पर मेरी व्याख्या के आधार के लिए जा रहा हूँ

इस सरल ग्राफ पर विचार करें (नोड एक साथ, बी, सी, डी, ई)। इस ग्राफ के किनारों और उनके वजन हैं: "ए-> बी: 1", "ए-> सी: 6", "ए-> डी: 4", "ए-> ई: 10", "डी-> सी: 3 "," सी> ई: 1 "। जब मैं दोनों तरफ इस ग्राफ के लिए डिजस्ट्रा एल्गोरिदम का उपयोग करता हूं: आगे में यह ए के बाद बी और फिर डी को पाता है, पिछड़े में यह ई के बाद सी और फिर डी को पाता है। इस बिंदु में, दोनों सेटों में समान वर्टेक्स और एक चौराहे होती है। क्या यह समाप्ति बिंदु है या यह जारी रखा जाना चाहिए? क्योंकि यह उत्तर (ए-> डी-> सी-> ई) गलत है।

जब मैं counterexample को (अनिर्दिष्ट) नेटवर्क पर networkx के द्विदिश डिज्कस्ट्रा चलाने आप टिप्पणी है कि दावा किया: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1":

संदर्भ के लिए, ग्राफ है यह मुझे देता है: (7, ['A', 'C', 'E']), नहीं A-D-C-E।

समस्या यह है कि यह से पहले की समस्या के गलतफहमी में है, यह बंद हो जाता है। नोड्स खोजने के मामले में यह वही है जो आप उम्मीद कर रहे हैं, लेकिन यह कर रहे हैं कि सबसे कम पथ खोजने के लिए अतिरिक्त प्रसंस्करण हो रहा है। जब तक यह दोनों दिशाओं से D तक पहुंचता है, तब तक यह कुछ अन्य "उम्मीदवार" पथ एकत्र कर चुका है जो कम हो सकते हैं। इसकी कोई गारंटी नहीं है कि सिर्फ इसलिए कि नोड D दोनों दिशाओं से प्राप्त होता है जो सबसे कम पथ का हिस्सा बनता है। इसके बजाय, इस बिंदु पर कि दोनों दिशाओं से एक नोड तक पहुंच गया है, वर्तमान उम्मीदवार सबसे छोटा रास्ता किसी भी उम्मीदवार पथ से छोटा है जो इसे जारी रखेगा।

एल्गोरिथ्म, दो खाली समूहों के साथ शुरू होता प्रत्येक A या E

{}   {} 

के साथ जुड़े हैं और यह प्रत्येक के आसपास "समूहों" का निर्माण होगा। यह पहली बार A

{A:0}   {} 

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

clusters     .....  fringes 

{A:0}   {}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[] 

अब यह जाँच करता है E की 'हाशिये' कहते हैं। E के लिए यह सममित चीज है। अपने क्लस्टर में E रखें। जांचें कि E क्लस्टर में A के आसपास नहीं है।फिर A (वे नहीं हैं) के क्लस्टर में कोई भी देखने के लिए अपने सभी पड़ोसियों की जांच करें। फिर E की फ्रिंज बनाता है।

clusters         fringes 
{A:0}   {E:0}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

अब यह A पर वापस चला जाता है। सूची में B लगता है और इसे A के आसपास क्लस्टर में जोड़ता है। यह जांचता है कि B का कोई पड़ोसी क्लस्टर में E (विचार करने के लिए कोई पड़ोसी नहीं है)। तो हमने:

clusters         fringes 
{A:0, B:1}  {E:0}  .....  A:[(D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

वापस E लिए: हम E की वह मुन्ना C जोड़ने क्लस्टर और जाँच करें कि क्या C के किसी भी पड़ोसी A के क्लस्टर में है। आप क्या जानते हैं, A है। तो हमारे पास उम्मीदवार दूरी 7 के साथ सबसे कम पथ ए-सी-ई है। हम उस पर ध्यान देंगे। हम E (दूरी 4 के साथ, 1 + 3 के बाद) में जोड़ने के लिए D जोड़ते हैं। हम:

clusters         fringes 
{A:0, B:1}  {E:0, C:1}  ..... A:[(D,4), (C,6), (E,10)] 
             E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

वापस A लिए: हम अपने हाशिये, D से अगली बात मिलता है। हम इसे क्लस्टर में A के बारे में जोड़ते हैं, और ध्यान दें कि उसके पड़ोसी C क्लस्टर में E है। तो हमारे पास एक नया उम्मीदवार पथ है, A-D-C-E, लेकिन इसकी लंबाई 7 से अधिक है इसलिए हम इसे छोड़ दें।

clusters         fringes 
{A:0, B:1, D:4}  {E:0, C:1}  ..... A:[(C,6), (E,10)] 
              E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

अब हम E पर वापस जाएं। हम D पर देखते हैं। यह क्लस्टर में A के आसपास है। हम यह सुनिश्चित कर सकते हैं कि हमारे पास आने वाले भविष्य के किसी भी उम्मीदवार के पास कम से कम A-D-C-E पथ जितना बड़ा होगा, हमने अभी पता लगाया है (यह दावा जरूरी नहीं है, लेकिन यह इस दृष्टिकोण की कुंजी है)। तो हम रुक सकते हैं। हम पहले मिले उम्मीदवार पथ वापस करते हैं।