भारित रेखांकन में सबसे छोटे रास्ते खोजने के लिए बुनियादी एल्गोरिदम

निश्चित रूप से गेम डेवलपर्स (या प्रोग्रामिंग के शौकीन लोगों में से कई) इन चार सबसे महत्वपूर्ण एल्गोरिदम को सुनने के लिए इच्छुक होंगे जो सबसे कम रास्तों पर समस्याओं को हल करते हैं।

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

हम मानते हैं कि ग्राफ में n कोने और m किनारे हैं।
आइए सरल से जटिल पर जाएं।

फ्लोयड-वॉर्शेल एल्गोरिथम

आदेश n ^ 3 के संचालन की संख्या के लिए प्रत्येक शीर्ष से प्रत्येक के लिए दूरी प्राप्त करता है। वजन नकारात्मक हो सकता है, लेकिन हमारे पास किनारों के वजन के नकारात्मक योग के साथ चक्र नहीं हो सकते हैं (अन्यथा हम हर बार जितना चाहें उतना कम मात्रा में चल सकते हैं और कम कर सकते हैं, यह दिलचस्प नहीं है)।
I वें वें पुनरावृत्ति में सरणी d [0 ... n - 1] [0 ... n - 1] में, हम प्रतिबंध के साथ मूल समस्या के उत्तर को संचित करेंगे कि हम संख्याओं के साथ कड़ाई से उपयोग करेंगे जो कि मार्ग में "हस्तांतरण बिंदु" से कम है। - 1 (हम खरोंच से कोने की संख्या)। आइ-वें पुनरावृत्ति को जाने दें, और हम सरणी को i + 1 में अपडेट करना चाहते हैं। ऐसा करने के लिए, प्रत्येक जोड़ी के लिए हम केवल इंटरचेंज के रूप में i - 1 वर्टेक्स लेने की कोशिश करेंगे, और यदि यह उत्तर को बेहतर बनाता है, तो इसे छोड़ दें। कुल में, हम n + 1 पुनरावृत्ति करेंगे, इसके पूरा होने के बाद, हम किसी भी "इंटरचेंज" के रूप में उपयोग कर सकते हैं, और सरणी डी उत्तर होगा।
n पुनरावृत्तियों पर n पुनरावृत्तियों पर n पुनरावृत्तियों, क्रम n के कुल 3 ऑपरेशन।
छद्म कोड:

 g // g[0 ... n - 1][0 ... n - 1] - ,     , g[i][j] = 2000000000,    i  j  d = g for i = 1 ... n + 1 for j = 0 ... n - 1 for k = 0 ... n - 1 if d[j][k] > d[j][i - 1] + d[i - 1][k] d[j][k] = d[j][i - 1] + d[i - 1][k]  d 

फोर्ड बेलमैन एल्गोरिथम

आदेश n * m के संचालन की संख्या के लिए अन्य सभी से एक शीर्ष से दूरी (चलो इसे 0 नंबर दें)। पिछले एल्गोरिथ्म के समान, वज़न नकारात्मक हो सकता है, लेकिन हम किनारों के वज़न के नकारात्मक योग के साथ चक्र नहीं रख सकते हैं।
हम एक सरणी d [0 ... n - 1] शुरू करते हैं, जिसमें ith पुनरावृत्ति पर हम प्रतिबंध के साथ मूल समस्या के उत्तर को संग्रहीत करेंगे कि कड़ाई से कम से कम i किनारों को पथ में प्रवेश करना चाहिए। यदि शिखर j के लिए ऐसे मार्ग नहीं हैं, तो d [j] = 2,000,000,000 (यह कुछ अप्राप्य स्थिरांक, "अनन्तता" होना चाहिए)। D की शुरुआत में, 2000000000 भरा हुआ है। i-th पुनरावृत्ति पर सरणी को अपडेट करने के लिए, आपको बस प्रत्येक किनारे पर जाने की जरूरत है और इससे जुड़ने वाले कोने की दूरी को सुधारने का प्रयास करें। सबसे छोटे रास्तों में चक्र नहीं होते हैं, क्योंकि सभी चक्र गैर-नकारात्मक होते हैं, और हम चक्र को पथ से हटा सकते हैं, और पथ की लंबाई नहीं बिगड़ती है (मैं यह भी ध्यान रखना चाहूंगा कि यह कैसे ग्राफ में नकारात्मक चक्रों को खोजने के लिए है: हमें एक और पुनरावृत्ति करने की आवश्यकता है और देखें क्या कुछ शिखर की दूरी में सुधार हुआ है)। इसलिए, सबसे छोटे पथ की लंबाई n - 1 से अधिक नहीं है, जिसका अर्थ है कि nth पुनरावृत्ति के बाद d समस्या का उत्तर होगा।
n पुनरावृत्तियों पर कुल पुनरावृत्तियों, कुल n * m संचालन के क्रम।
छद्म कोड:

  e // e[0 ... m - 1] - ,        (first, second - ,  , value -  ) for i = 0 ... n - 1 d[i] = 2000000000 d[0] = 0 for i = 1 ... n for j = 0 ... m - 1 if d[e[j].second] > d[e[j].first] + e[j].value d[e[j].second] = d[e[j].first] + e[j].value if d[e[j].first] > d[e[j].second] + e[j].value d[e[j].first] = d[e[j].second] + e[j].value  d 

डीजकस्ट्रा का एल्गोरिथम

आदेश n ^ 2 के संचालन की संख्या के लिए अन्य सभी से एक शीर्ष से दूरी प्राप्त करें (चलो इसे 0 नंबर दें)। सभी वजन गैर-नकारात्मक हैं।
प्रत्येक पुनरावृत्ति पर, कुछ कोने चिह्नित होंगे, और कुछ नहीं। हम दो सरणियाँ शुरू करेंगे: निशान [0 ... n - 1] - सच है, यदि शीर्ष को चिह्नित किया गया है, तो गलत, अन्यथा, घ [0 ... n - 1] - प्रत्येक शीर्ष के लिए केवल "लंबित अंक" के साथ चिह्नित शीर्षकों के साथ गुजरने वाले सबसे छोटे पथ की लंबाई संग्रहीत की जाएगी। । समर्थित भी अपरिवर्तनीय है जो लेबल किए गए लंबों के लिए डी में इंगित लंबाई का उत्तर है। सबसे पहले, केवल शीर्ष 0 को चिह्नित किया गया है, और जी [i] एक्स के बराबर है यदि 0 और मैं वजन एक्स के किनारे से जुड़े हुए हैं, 2,000,000,000 के बराबर हैं यदि वे एक किनारे से नहीं जुड़े हैं, और 0 के बराबर है अगर I = 0।
प्रत्येक पुनरावृत्ति पर, हम असंबद्ध लोगों के बीच घ में सबसे छोटे मूल्य के साथ शीर्ष को पाते हैं, इसे शीर्ष v बता दें। तब d [v] का मान v का उत्तर है। हम साबित करते हैं। मान लीजिए कि 0 से v तक का सबसे छोटा रास्ता न केवल चिह्नित स्थान के साथ "स्थानांतरण बिंदु" के रूप में जाता है, और साथ ही यह d [v] से छोटा है। इस पथ पर पहला अचिह्नित शिखर लें, इसे यू कहें। पथ के यात्रा वाले हिस्से की लंबाई (0 से u तक) d [u] है। len> = d [u], जहां len 0 से v तक सबसे छोटी पथ की लंबाई है (क्योंकि कोई नकारात्मक किनारे नहीं हैं), लेकिन हमारी धारणा से len d [v] से कम है। इसलिए, डी [वी]> लेन> = डी [यू]। लेकिन तब v इसके विवरण में फिट नहीं होता है - इसमें सबसे छोटा मान नहीं है d [v] जो कि अनलेबेलड लोगों के बीच है। विरोधाभास।
अब साहसपूर्वक वर्टेक्स v और पुनर्गणना d को चिह्नित करें। हम ऐसा तब तक करते हैं जब तक सभी कोने चिह्नित नहीं हो जाते हैं और समस्या का उत्तर बन जाता है।
n पुनरावृत्तियों पर एन पुनरावृत्तियों (शीर्ष v के लिए खोज करने के लिए), n ^ 2 संचालन के क्रम को कुल।
छद्म कोड:

  g // g[0 ... n - 1][0 ... n - 1] - ,     , g[i][j] = 2000000000,    i  j  d = g d[0] = 0 mark[0] = True for i = 1 ... n - 1 mark[i] = False for i = 1 ... n - 1 v = -1 for i = 0 ... n - 1 if (not mark[i]) and ((v == -1) or (d[v] > d[i])) v = i mark[v] = True for i = 0 ... n - 1 if d[i] > d[v] + g[v][i] d[i] = d[v] + g[v][i]  d 

विरल रेखांकन के लिए डीजकस्ट्रा का एल्गोरिदम

यह दीजकस्ट्रा एल्गोरिथ्म के समान है, लेकिन एम * लॉग (एन) के क्रम के संचालन की संख्या के लिए। यह ध्यान दिया जाना चाहिए कि मीटर n ^ 2 के क्रम का हो सकता है, अर्थात, दिज्क्स्ट्रा के एल्गोरिथ्म का यह भिन्नता हमेशा शास्त्रीय एक से तेज नहीं है, बल्कि केवल छोटे मीटर के लिए है।
हमें दिक्स्ट्रा के एल्गोरिथ्म में क्या चाहिए? हमें d के मान से न्यूनतम शीर्ष ज्ञात करने में सक्षम होना चाहिए और कुछ शीर्ष पर d के मान को अद्यतन करने में सक्षम होना चाहिए। क्लासिक कार्यान्वयन में, हम एक सरल सरणी का उपयोग करते हैं, हम n संचालन के क्रम में घ में न्यूनतम शीर्ष शीर्ष पा सकते हैं, और 1 ऑपरेशन में अपडेट कर सकते हैं। हम बाइनरी हीप का उपयोग करेंगे (कई ऑब्जेक्ट-ओरिएंटेड भाषाओं में यह अंतर्निहित है)। हीप संचालन का समर्थन करता है: हीप में एक तत्व जोड़ें (लॉग (एन) संचालन के लिए), न्यूनतम तत्व खोजें (1 ऑपरेशन के लिए), न्यूनतम तत्व को हटाएं (लॉग (एन) संचालन के लिए), जहां एन हीप में तत्वों की संख्या है।
एक सरणी बनाएँ d [0 ... n - 1] (इसका मान पहले जैसा है) और q का एक गुच्छा। ढेर पर हम शीर्ष संख्या v और d [v] से जोड़े को संग्रहीत करेंगे (जोड़े को d [v] में तुलना की जानी चाहिए)। ढेर में डमी तत्व भी हो सकते हैं। ऐसा इसलिए होता है क्योंकि d [v] का मान अद्यतन है, लेकिन हम इसे ढेर पर नहीं बदल सकते। इसलिए, एक ही शीर्ष संख्या के साथ ढेर में कई तत्व हो सकते हैं, लेकिन एक अलग डी मूल्य के साथ (लेकिन ढेर में एम कोने से अधिक नहीं होगा, मैं इसकी गारंटी देता हूं)। जब हम ढेर पर न्यूनतम मूल्य लेते हैं, तो हमें यह जांचना होगा कि क्या यह तत्व डमी है। ऐसा करने के लिए, यह ढेर के मूल्य और इसके वास्तविक मूल्य की तुलना करने के लिए पर्याप्त है। और एक ग्राफ लिखने के लिए, एक बाइनरी सरणी के बजाय, हम सूचियों की एक सरणी का उपयोग करते हैं।
m बार हम ढेर में एक तत्व जोड़ते हैं, हमें m * log (n) संचालन का क्रम मिलता है।
छद्म कोड:

  g // g[0 ... n - 1] -  ,  i-   : first - ,   i-  , second -    d[0] = 0 for i = 0 ... n - 1 d[i] = 2000000000 for i in g[0] // python style d[i.first] = i.second q.add(pair(i.second, i.first)) for i = 1 ... n - 1 v = -1 while (v = -1) or (d[v] != val) v = q.top.second val = q.top.first q.removeTop mark[v] = true for i in g[v] if d[i.first] > d[v] + i.second d[i.first] = d[v] + i.second q.add(pair(d[i.first], i.first))  d