डिजस्ट्रा का एल्गोरिदम क्यों काम करता है?

Question

मैं समझता हूं कि Dijkstra's algorithm क्या है, लेकिन मुझे समझ में नहीं आता कि यह क्यों काम करता है।

जांच करने के लिए अगली कशेरुक का चयन करते समय, डिजस्ट्रा के एल्गोरिदम छोटे वजन वाले व्यक्ति का चयन क्यों करते हैं? क्यों न सिर्फ एक कशेरुक का चयन करें, क्योंकि एल्गोरिदम किसी भी तरह से सभी शीर्षकों पर जाता है?

Answer 1

आप Djikstra के एल्गोरिदम को पानी भरने वाले एल्गोरिदम के रूप में सोच सकते हैं (यानी एक छिद्रित चौड़ाई-पहली खोज)। प्रत्येक चरण में, लक्ष्य पूरे ग्राफ़ को सबसे कम लागत वाले पथ के साथ कवर करना है। मान लीजिए आप आप जिस क्षेत्र में भर दिया के किनारे पर कोने है, और आप दूरी के संदर्भ में उन्हें सूचीबद्ध:

v0 <= v1 <= v2 <= v3 ... 

वहाँ संभवतः शीर्ष v1 को पाने के लिए एक सस्ता तरीका हो सकता है? यदि ऐसा है, तो पथ v0 के माध्यम से जाना चाहिए, क्योंकि कोई भी अनचाहे वर्टेक्स निकट नहीं हो सकता है। तो आप v0 पर जांच कर सकते हैं कि आप कहां जा सकते हैं, यह जांचने के लिए कि v0 के माध्यम से कोई रास्ता सस्ता है (किसी भी अन्य चरम पर एक कदम दूर)।

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

और आप की आवश्यकता से कहीं अधिक काम किए बिना बंद हो जाते हैं, क्योंकि जब आप अपना गंतव्य कशेरुक "मैं छोटा हूं" v0 स्लॉट पर रोकता है तो आप रुक जाते हैं।

चलिए एक संक्षिप्त उदाहरण देखें। मान लीजिए कि हम गुणा करके 1 से 12 से प्राप्त करने का प्रयास कर रहे हैं, और नोड्स के बीच की लागत वह संख्या है जिसे आप गुणा करना चाहते हैं। (हम 12 को 1 से संख्या के कोने सीमित हो जाएगी।)

हम 1 के साथ शुरू, और हम उस मूल्य से गुणा करके किसी अन्य नोड के लिए मिल सकता है। तो 2 की लागत 2 है, 3 की कीमत 3 है, ... 12 की लागत 12 है यदि आप एक चरण में जाते हैं।

अब, 2 के माध्यम से एक रास्ता (संरचना के बारे में जानने के बिना) के लिए 12 सबसे तेजी से अगर वहाँ 2 से 12 लिए नि: शुल्क जुड़ाव से मिल सकता है। ऐसा नहीं है, लेकिन अगर वहां था, तो यह सबसे तेज़ होगा। तो हम 2 जांचते हैं। और हम पाते हैं कि हम के लिए 4 पर 3 के लिए 4 पर जा सकते हैं, और इसी तरह।इस प्रकार हम यह तो जैसे लागत का एक मेज है:

3 4 5 6 7 8 9 10 11 12 // Vertex 
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far. 

ठीक है, अब शायद हम 123 से करने के लिए मुक्त करने के लिए प्राप्त कर सकते हैं! बेहतर जांच और हम पाते हैं कि 3*2==6 इसलिए 6 की लागत 3 प्लस 2 की लागत है, और 9 प्लस 3 है, और 12 प्लस 4 है।

4 5 6 7 8 9 10 11 12 
4 5 5 7 6 6 7 11 7 

पर्याप्त मेला। अब हम 4 का परीक्षण करते हैं, और हम देखते हैं कि हम अतिरिक्त 2 के लिए 8 पर और के लिए 12 पर जा सकते हैं।

5 6 7 8 9 10 11 12 
5 5 7 6 8 7 11 7 

अब हम अब तक 5 और 6 --no सुधार की कोशिश: एक बार फिर, लागत 12 को पाने के लिए इस प्रकार 4 से अधिक नहीं + 3 = 7 है। यह हमें

7 8 9 10 11 12 
7 6 8 7 11 7 

साथ छोड़ देता है अब, पहली बार के लिए, हम देखते हैं कि 8 के लिए हो रही की लागत 7 के लिए हो रही की लागत से कम है, इसलिए हम बेहतर की जांच की थी वहाँ नहीं है कि कुछ 8 से 12 पर जाने का निःशुल्क तरीका। वहाँ नहीं है - पूर्णांक के साथ बिल्कुल पाने का कोई तरीका नहीं है - इसलिए हम इसे फेंक देते हैं।

7 9 10 11 12 
7 8 7 11 7 

और अब हम देखते हैं कि 12 किसी भी पथ छोड़ दिया के रूप में के रूप में सस्ता है, इसलिए लागत 12 तक पहुँचने के लिए 7 होना चाहिए। अगर हम अब तक के सबसे सस्ता रास्ते का ट्रैक रखेंगे (केवल तभी पथ को बदलना जब यह सख्ती से बेहतर हो), हम पाएंगे कि 3*412 को हिट करने का पहला सबसे सस्ता तरीका है।

Answer 2

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

किसी भी अन्य कशेरुक का दौरा करना, इसलिए, यदि यह अधिक महंगा है (जो काफी संभव है) न केवल उस अन्य कशेरुक का दौरा करने की आवश्यकता होगी, बल्कि कम से कम पथ लागत वाला भी होगा, इसलिए आपको और अधिक जाना होगा सबसे छोटा रास्ता खोजने से पहले शिखर। वास्तव में, यदि आप ऐसा करते हैं तो आप Bellman-Ford algorithm के साथ समाप्त हो जाएंगे।

मुझे यह भी जोड़ना चाहिए कि कशेरुक का वजन नहीं है, यह वह किनारा है जिस पर वजन होता है। किसी दिए गए कशेरुक के लिए कुंजी स्रोत वर्टेक्स से उस कशेरुक तक अब तक के सबसे कम पथ की लागत है।

Answer 3

इसे लालची रणनीति पसंद है। मेरी अंग्रेजी अच्छी नहीं है। यह Google द्वारा अनुवाद करता है। अगर आप समझ में नहीं आते हैं, तो मुझे बहुत खेद है।

डीजस्ट्रा एल्गोरिदम, एस से एक जी सबसे छोटी पथ लंबाई के सभी शीर्षकों तक। हम मानते हैं कि जी में वी के प्रत्येक चरम को ध्वज एल (वी) दिया गया है, यह या तो एक संख्या है, या तो ∞। मान लीजिए पी जी के शिखर का सेट है, पी में एस है, संतुष्ट करने के लिए:

ए) यदि वी पी है, तो एल (वी) वीएस से सबसे कम पथ की लंबाई तक, और ऐसे वी के अस्तित्व से एस सबसे कम पथ पर:

बी) यदि वी पी से संबंधित नहीं है, तो एस से वी से एल (वी) सबसे कम पथ की लंबाई पर निम्नलिखित प्रतिबंधों को पूरा करता है: वी है एकमात्र पथ पी कशेरुक से संबंधित नहीं है।

हम संग्रह की उपरोक्त परिभाषा के साथ लाइन में साबित करने के लिए पी डिज्कस्ट्रा एल्गोरिथ्म प्रेरण का उपयोग कर सकते हैं:

1) पी = 1 में तत्वों की संख्या, पी एल्गोरिथ्म, पी में पहला कदम से मेल खाती है जब = (एस), स्पष्ट रूप से संतुष्ट है।

2) मान लीजिए पी कश्मीर, तत्वों की संख्या है, पी उपरोक्त परिभाषा को पूरा करना, में तीसरे चरण

3) पी और पता लगाने के लिए पहले नीचे एल्गोरिथ्म को देखने के न्यूनतम शिखर के साथ चिह्नित नहीं किया गया है यू, जिसे एल (यू) के रूप में चिह्नित किया गया है, एस को यू से यू के सबसे छोटे रास्ते के बाहर साबित किया जा सकता है, पी के अलावा तत्वों में शामिल नहीं है।

क्योंकि यदि यू को छोड़कर अन्य कोष्ठकों के बाहर है, तो एस, पी 1, पी 2 ... पीएन, क्यू 1, क्यू 2 ... क्यूएन, यू (पी 1, पी 2 ... पीएन पी है; क्यू 1, क्यू 2, ... क्यूएन पी से संबंधित नहीं है) बी की प्रकृति से) सबसे छोटी पथ लंबाई एल (क्यू 1) + पथ (क्यू 1, यू)> एल (यू)।

जो एस, पी 1, पी 2 से अधिक है ... पीएन, चैनल लंबाई एल (यू) का यू, सबसे छोटा रास्ता नहीं है। इसलिए, एस से यू के यू को सबसे कम पथ के बाहर, पी के अलावा तत्वों में एस से यू से संबंधित नहीं है जो एल (यू) से सबसे कम पथ की लंबाई तक है।

यू को पी के रूप में पी में जोड़ा गया है, स्पष्ट रूप से पी 'ए की प्रकृति को पूरा करने के लिए)।

ले लो वी से संबंधित नहीं है, जाहिर है वीपी से संबंधित नहीं है, फिर सबसे कम पथ को छोड़कर एस से वी तक और पथ में वी के बाहर सभी शीर्षकों को पूरा करने के लिए पथ में दो संभावनाएं हैं, i) यू, ii) यू

शामिल नहीं है मैं पर) एस, P1, P2 ... Pn, यू, वी = एल (यू) + W (यू, वी)

ii) एस, पी 1 , पी 2 ... पीएन, वी = एल (वी)

स्पष्ट रूप से दोनों को न्यूनतम एक्सेस को पूरा करने के लिए एस से सबसे छोटे वी में दिया जाता है और सभी शीर्षकों के बाहर बाहरी वीपी 'लंबाई में होते हैं।

पी 'के +1 तत्वों के साथ पी में दिए गए एल्गोरिदम का तीसरा चरण और ए से मिलना), बी)।

प्रेरण प्रस्ताव द्वारा अनुमति दे सकती है।

यहां the source है।

Answer 4

कारण है कि Dijsktra एल्गोरिथ्म काम करता है जिस तरह से यह करता है हिस्सा में है, क्योंकि यह तथ्य यह है कि नोड u और w बीच कम से कम पथ उस बिंदु v शामिल भी u से v करने और v से करने के लिए कम से कम पथ है कारनामे w। यदि आपके पास वी के बीच कुछ छोटा था, तो यह सबसे छोटा रास्ता नहीं होगा।

वास्तव में समझने के लिए कि डिजस्ट्रा का एल्गोरिदम क्यों काम करता है, dynamic programming की मूल बातें देखें, कठिन लगता है लेकिन सिद्धांतों को समझना वास्तव में बहुत आसान है।

Answer 5

यह सबसे कम वजन वाला पथ जांचता है क्योंकि यह जांच की गई पथों की संख्या को कम करने के लिए सबसे अधिक संभावना है (अतिरिक्त जानकारी के बिना)। उदाहरण के लिए:

 
a->b->c->e 

क्योंकि हम जानते हैं कि यह कम से कम 20 है, इसलिए हम जानते हैं कि यह क्या है:

 
a->b->c  cost is 20 
a->b->d  cost is 10 
a->b->d->e cost is 12 

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

Answer 6

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