सबसे छोटा मार्ग एल्गोरिथ्म

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

ग्राफ को समझना

सबसे छोटा मार्ग एल्गोरिदम में गोता लगाने से पहले, ग्राफ को समझना महत्वपूर्ण है। एक ग्राफ शिखरों (या नोड्स) और किनारों से बना होता है, जो निर्देशित या बिना निर्देशित, भारित या बिना भारित हो सकते हैं। सबसे छोटा मार्ग एल्गोरिदम के संदर्भ में, हम आमतौर पर भारित ग्राफ पर ध्यान केंद्रित करते हैं, जहां प्रत्येक किनारे में एक संख्यात्मक मान होता है जो इससे जुड़े शिखरों के बीच यात्रा की लागत या दूरी का प्रतिनिधित्व करता है।

सबसे छोटा मार्ग समस्या

सबसे छोटा मार्ग समस्या दो शिखरों के बीच एक मार्ग खोजने के बारे में है ताकि इसके घटक किनारों के भारों का योग न्यूनतम हो। ग्राफ की प्रकृति और विशिष्ट आवश्यकताओं के आधार पर, सबसे छोटा मार्ग खोजने के लिए विभिन्न तरीके इस्तेमाल किए जाते हैं।

डाइकस्ट्रा का एल्गोरिदम

डाइकस्ट्रा का एल्गोरिदम गैर-नकारात्मक किनारे भार वाले ग्राफ के लिए सबसे छोटा मार्ग समस्या को हल करने के लिए सबसे लोकप्रिय एल्गोरिदम में से एक है। यह एक लालची एल्गोरिदम है जो स्रोत नोड से ग्राफ के अन्य शिखरों तक सबसे छोटा मार्ग वस्तुतः खोजता है।

डाइकस्ट्रा के एल्गोरिदम का कार्य

1. स्रोत नोड की दूरी 0 और सभी अन्य नोड्स की दूरी अनंत निर्दिष्ट करें।
2. स्रोत नोड को वर्तमान नोड के रूप में सेट करें।
3. वर्तमान नोड के लिए, इसके सभी अप्रयुक्त पड़ोसियों पर विचार करें और स्रोत नोड से उनके अस्थायी दूरी की गणना करें।
4. यदि नया गणना की गई दूरी वर्तमान मान से कम है, तो प्रत्येक पड़ोसी की दूरी को अपडेट करें।
5. जब सभी पड़ोसियों को प्रोसेस कर लिया गया हो, तो वर्तमान नोड को विज़िट किया हुआ चिह्नित करें।
6. यदि गंतव्य नोड विज़िट किया गया है या नोड्स के बीच सबसे छोटी अस्थायी दूरी अनंत है, तो प्रक्रिया को रोकें।
7. अन्यथा, सबसे छोटे अस्थायी दूरी के साथ अप्रयुक्त नोड को अगले 'वर्तमान नोड' के रूप में सेट करें और चरण 3 से जारी रखें।

डाइकस्ट्रा के एल्गोरिदम का उदाहरण

सड़कों द्वारा जुड़े शहरों को दर्शाने वाले एक साधारण ग्राफ पर विचार करें, जहां किनारे दूरी के अनुसार भारित होते हैं।

ग्राफ चित्रण:
    A --4--> B
    A --1--> C
    B --2--> D
    C --2--> B
    C --5--> D

आइए डाइकस्ट्रा के एल्गोरिदम का उपयोग करके शहर A से शहर D तक का सबसे छोटा मार्ग खोजें।

प्रारंभिक दूरियाँ इस प्रकार हैं:

- A:0
- B : ∞
- C : ∞
- D : ∞

डाइकस्ट्रा के एल्गोरिदम को लागू करके:

1. A से प्रारंभ करें (खंड A, दूरी = 0)।
2. B 4 दूर है, और C 1 दूर है। संभावित दूरियों को अपडेट करें: B = 4, C = 1।
3. C नजदीक है (दूरी = 1)। अब C को वर्तमान शिखर के रूप में लें।
4. C से, B की दूरी को 1 + 2 = 3 पर अपडेट करें (क्योंकि यह प्रारंभिक 4 से कम है) और D की दूरी को 1 + 5 = 6 पर अपडेट करें।
5. अब, B की संभावित दूरी 3 है और D की 6 है। B को वर्तमान शिखर बनाएं क्योंकि यह छोटा है।
6. B से D की दूरी को 3 + 2 = 5 पर अपडेट करें, जो कि पहले से अनुमानित 6 की तुलना में कम है।
7. अब, A से D का सबसे छोटा मार्ग 5 सेकंड लंबा है। एल्गोरिदम समाप्त होता है।

इस प्रकार सबसे छोटा मार्ग A → C → B → D है जिसकी कुल दूरी 5 है।

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

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

बेलमैन-फोर्ड एल्गोरिदम का कार्य

1. स्रोत नोड की दूरी 0 और सभी अन्य नोड्स की दूरी अनंत है।
2. प्रत्येक किनारे के लिए, इसे आराम दें: यदि इस किनारे के माध्यम से गंतव्य नोड तक की वर्तमान दूरी स्रोत नोड और इस किनारे के भार के योग से अधिक है, तो गंतव्य नोड की दूरी को अपडेट करें।
3. चरण 2 को कुल |V|-1 बार दोहराएं, जहां |V| शिखरों की संख्या है।
4. नकारात्मक भार चक्रीय के लिए जांच करें: प्रत्येक किनारे के लिए, यदि आप एक छोटा रास्ता पा सकते हैं, तो एक नकारात्मक भार चक्रीय मौजूद है। अन्यथा, छोटे रास्ते पा गए हैं।

बेलमैन-फोर्ड एल्गोरिदम का उदाहरण

नकारात्मक किनारे भार वाले ग्राफ पर विचार करें:

ग्राफ चित्रण:
    A --4--> B
    A ---2--> C
    B --3--> C
    B --5--> D
    C --1--> B
    C --6--> D

चलिये Bellman-Ford एल्गोरिदम लागू करते हैं A नोड से B नोड तक सबसे छोटा रास्ता खोजने के लिए:

प्रारंभिक दूरियाँ इस प्रकार हैं:

- A:0
- B : ∞
- C : ∞
- D : ∞

बेलमैन-फोर्ड एल्गोरिदम लागू करके:

1. |V|-1 = 3 बार पुनरावृत्ति के बाद:
• एज AB के लिए: Dist(B) = न्यूनतम(∞, 0 + 4) = 4
• एज AC के लिए: Dist(C) = न्यूनतम(∞, 0 - 2) = -2
• एज BC के लिए: Dist(C) = न्यूनतम(-2, 4 + 3) = -2 (कोई अपडेट नहीं चाहिए)
• एज BD के लिए: Dist(D) = न्यूनतम(∞, 4 + 5) = 9
• एज CB के लिए: Dist(B) = न्यूनतम(4, -2 + 1) = -1
• एज CD के लिए: Dist(D) = न्यूनतम(9, -2 + 6) = 4
2. नई दूरियाँ बनाई गई हैं:

    - A:0
    - B :-1
    - C: -2
    - D:4
    

3. नकारात्मक भार चक्रीय का पता लगाने के लिए एक अतिरिक्त चक्र चलाने से कोई आगे की कमी नहीं दिखती है, इसलिए पाए गए रास्ते इष्टतम हैं।

A* एल्गोरिदम

A* एक खोज एल्गोरिदम है जो दो नोड्स के बीच सबसे छोटा मार्ग पाता है। यह विशेष रूप से कंप्यूटर विज्ञान में पथ ढूँढने और ग्राफ खोज के लिए लोकप्रिय है। A* को अलग क्या बनाता है, यह है उसका हीरिस्टिक का उपयोग जो प्रारंभ नोड से वास्तविक लागत को मानता है और लक्ष्य तक पहुँचने की संभावित लागत का अनुमान लगाता है। A* में डाइकस्ट्रा के एल्गोरिदम और लोभर-से-पहले खोज की विशेषताएँ होती हैं।

A* में प्रमुख अवधारणाएँ

A* एल्गोरिदम एक भारित ग्राफ और एक हीरिस्टिक फ़ंक्शन का उपयोग करके किसी भी नोड x से लक्ष्य तक पहुँचने की लागत का अनुमान लगाता है, जिसे h(x) के रूप में दर्शाया जाता है।

नोड n के लिए कुल अनुमानित लागत दी जाती है:

f(n) = g(n) + h(n)

- g(n) शुरुआती नोड से n तक के मार्ग की लागत है। - h(n) एक हीरिस्टिक फ़ंक्शन है जो n से लक्ष्य तक की लागत का अनुमान लगाता है।

A* एल्गोरिदम का उदाहरण

ऐसा ग्रिड पर विचार करें जिसमें नोड एक भूलभुलैया का प्रतिनिधित्व करते हैं जहाँ गति की लागत विभिन्न होती है।

लक्ष्य से नोड्स की अनुमानित दूरी h(n) है, और क्षैतिज/ऊर्ध्वाधर चाल की लागत 1 है, जबकि विकर्ण चाल की लागत 1.4 है।

START ○○○○ GOAL
       
       
       

न्यूनतम पथ लागत का उपयोग करके लक्ष्य तक पहुँचने के लिए A* को निष्पादित करें।

1. ओपन सेट = {स्टार्ट}
2. क्लोस्ड सेट = {}

3. जब तक openset खाली ना हो
    a. वर्तमान = openset में सबसे कम f(node) वाला नोड
    b. अगर वर्तमान लक्ष्य है:
        वापस current पहुँचने का पथ बनाएं
        
    c. वर्तमान को ओपनसेट से हटाएं
    d. वर्तमान को क्लोस्ड सेट में जोड़ें
    
    E. स्ट्रीम के प्रत्येक पड़ोसी के लिए:
        i. अगर पड़ोसी क्लोस्ड सेट में है:
            अगले पड़ोसी पर जारी रखें
        
        ii. temp_g = g(वर्तमान) + d(वर्तमान, पड़ोसी)
        
        iii. यदि पड़ोसी openSet में नहीं है:
            पड़ोसी को openSet में जोड़ें
        iv. अन्यथा अगर tentative_g > = g(पड़ोसी):
            जारी रखें
        
        v. came_from[पड़ोसी] = वर्तमान
        vi. g(पड़ोसी) = temp_g
        vii. f(पड़ोसी) = g(पड़ोसी) + h(पड़ोसी)

पथ की लागत और हीरिस्टिक्स को संतुलित करके, A* कुशलता से सबसे छोटा मार्ग पाता है।

निष्कर्ष

सबसे छोटा मार्ग एल्गोरिदम कंप्यूटर विज्ञान और अनुकूलन में अपरिहार्य उपकरण हैं। डाइकस्ट्रा, बेलमैन-फोर्ड और A* जैसे एल्गोरिदम सरल नेविगेशन से लेकर नेटवर्क्स में जटिल मार्ग योजना तक विभिन्न प्रकार की समस्याओं को हल करते हैं। इन एल्गोरिदम को समझना उनके तंत्रिका, विशेषताओं, सीमाओं और अनुप्रयोग क्षेत्रों को समझने में सुधार लाता है।

इन एल्गोरिदम को लागू करके, जटिल नेटवर्क को कुशलतापूर्वक प्रबंधित किया जा सकता है, लॉजिस्टिक्स का अनुकूलन किया जा सकता है, और वास्तविक दुनिया की समस्याओं को हल किया जा सकता है, जो संपूर्ण गणित के व्यापक क्षेत्र में ग्राफ सिद्धांत की महत्वपूर्ण उपयोगिता को दर्शाता है।

प्रत्येक एल्गोरिदम ग्राफ खोज तकनीकों में अद्वितीय अंतर्दृष्टियाँ प्रदान करता है, यह सुनिश्चित करते हुए कि कोई भी विविध चुनौतियों के लिए कंप्यूटेशनल क्षेत्रों में तैयार होता है। इन एल्गोरिदम का अधिग्रहण मूलभूत ज्ञान को मजबूत करता है, नेटवर्क अनुकूलन रणनीतियों में उन्नत अनुसंधान और नवीनताओं को बढ़ावा देता है।

टिप्पणियाँ