dynamic-programming
गतिशील प्रोग्रामिंग का उपयोग करके ग्राफ की समस्याओं को हल करना
खोज…
फ्लोयड-वारशॉल एल्गोरिथम
फ्लोयड-वारशॉ का एल्गोरिथ्म सकारात्मक या नकारात्मक बढ़त भार के साथ एक भारित ग्राफ में सबसे छोटा रास्ता खोजने के लिए है। एल्गोरिथ्म के एक एकल निष्पादन में सभी जोड़े कोने के बीच सबसे छोटे रास्तों की लंबाई (सममित भार) मिलेगी। थोड़े बदलाव के साथ, यह सबसे छोटे रास्ते को प्रिंट कर सकता है और एक ग्राफ में नकारात्मक चक्रों का पता लगा सकता है। फ्लॉयड-वारशॉल एक डायनेमिक-प्रोग्रामिंग एल्गोरिथम है।
आइए एक उदाहरण देखें। हम इस ग्राफ पर फ्लोयड-वारशॉ का एल्गोरिथ्म लागू करने जा रहे हैं:
पहली बात हम करते हैं, हम दो 2D मैट्रीस लेते हैं। ये आसन्न मैट्रिक्स हैं । मेट्रिसेस का आकार कुल संख्याओं का होने वाला है। हमारे ग्राफ के लिए, हम 4 * 4 मैट्रिसेस लेंगे। डिस्टेंस मैट्रिक्स दो वर्टिकल के बीच अब तक मिली न्यूनतम दूरी को स्टोर करने वाला है। : सबसे पहले, किनारों के लिए, अगर वहाँ यूवी और दूरी / वजन डब्ल्यू, हम संग्रहीत करेंगे है के बीच एक बढ़त है distance[u][v] = w
। सभी किनारों के लिए जो मौजूद नहीं है, हम अनंत डाल रहे हैं। पाथ मैट्रिक्स दो कोने के बीच न्यूनतम दूरी पथ को पुनर्जीवित करने के लिए है। इसलिए शुरू में, अगर u और v के बीच कोई रास्ता है, तो हम path[u][v] = u
। इसका मतलब है कि वर्टेक्स-यू से वर्टेक्स- वी में आने का सबसे अच्छा तरीका उस किनारे का उपयोग करना है जो वी को यू से जोड़ता है। यदि दो चक्करों के बीच कोई रास्ता नहीं है, तो हम N को वहां पर रखने जा रहे हैं, जिससे यह संकेत मिलता है कि अब कोई रास्ता उपलब्ध नहीं है। हमारे ग्राफ के लिए दो तालिकाओं की तरह दिखेगा:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 6 | 15 | | 1 | N | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | inf | 0 | -2 | inf | | 2 | N | N | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | inf | inf | 0 | 2 | | 3 | N | N | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | inf | inf | 0 | | 4 | 4 | N | N | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
चूंकि कोई लूप नहीं है, विकर्णों को एन सेट किया जाता है । और स्वयं शीर्ष से दूरी 0 है ।
फ्लोयड-वार्शाल एल्गोरिथ्म को लागू करने के लिए, हम एक मध्य शीर्ष k का चयन करने जा रहे हैं। फिर प्रत्येक वर्टेक्स i के लिए , हम यह जाँचने जा रहे हैं कि क्या हम i से k और फिर k से j तक जा सकते हैं, जहाँ j एक और शीर्ष है और i से j तक जाने की लागत को कम करता है। यदि वर्तमान दूरी [i] [j] दूरी की तुलना में अधिक है [i] [k] + दूरी [k] [j] , हम दूरी डालने जा रहे हैं [i] [j] उन दो दूरी के योग के बराबर है । और पथ [i] [j] को पथ [k] [j] पर सेट किया जाएगा, क्योंकि i से k तक जाना बेहतर है, और फिर k से j तक । सभी कोने को k के रूप में चुना जाएगा। हमारे पास 3 नेस्टेड लूप होंगे: k के लिए 1 से 4 तक, मैं 1 से 4 तक जा रहा हूं और j से 1 से 4. तक जा रहा हूं ।
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
तो क्या हम मूल रूप से जाँच कर रहे हैं, हर जोड़ी के लिए, क्या हम किसी अन्य शीर्ष से होकर गुजरते हैं? हमारे ग्राफ के लिए संचालन की कुल संख्या 4 * 4 * 4 = 64 होगी । इसका मतलब है कि हम 64 बार यह जाँच करने जा रहे हैं। आइए उनमें से कुछ को देखें:
जब k = 1 , i = 2 और j = 3 , दूरी [i] [j] -2 है , जो दूरी [i] [k] + दूरी [k] [j] = -2 + 0 = से अधिक नहीं है -2 तो यह अपरिवर्तित रहेगा। फिर, जब k = 1 , i = 4 और j = 2 , दूरी [i] [j] = अनंत , जो दूरी से अधिक है [i] [k] + दूरी [k] [j] = 1 + 3 = 4 । इसलिए हमने दूरी [i] [j] = ४ रखी है, और हमने पथ [i] [j] = पथ [k] [j] = १ रख दिया है। इसका मतलब क्या है, वर्टेक्स -4 से वर्टेक्स -2 तक जाने के लिए , रास्ता 4-> 1-> 2 मौजूदा मार्ग से छोटा है। इस तरह हम दोनों मैट्रिसेस को पॉप्युलेट करते हैं। प्रत्येक चरण के लिए गणना यहां दिखाई गई है । आवश्यक परिवर्तन करने के बाद, हमारे मैट्रीस जैसे दिखेंगे:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 1 | 3 | | 1 | N | 1 | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | 1 | 0 | -2 | 0 | | 2 | 4 | N | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | 3 | 6 | 0 | 2 | | 3 | 4 | 1 | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | 4 | 2 | 0 | | 4 | 4 | 1 | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
यह हमारी सबसे छोटी दूरी की मैट्रिक्स है। उदाहरण के लिए, 1 से 4 तक की सबसे छोटी दूरी 3 है और 4 से 3 के बीच की सबसे छोटी दूरी 2 है । हमारा छद्म कोड होगा:
Procedure Floyd-Warshall(Graph):
for k from 1 to V // V denotes the number of vertex
for i from 1 to V
for j from 1 to V
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
end for
end for
end for
पथ मुद्रण:
पथ मुद्रित करने के लिए, हम पथ मैट्रिक्स की जाँच करेंगे। U से v तक का मार्ग प्रिंट करने के लिए , हम पथ से शुरू करेंगे [u] [v] । हम बदलते रहेंगे v = path [u] [v] जब तक हम रास्ता नहीं ढूंढते [u] [v] = u और एक स्टैक में पथ के प्रत्येक मूल्यों [u] [v] को धक्का देते हैं। यू खोजने के बाद, हम यू प्रिंट करेंगे और स्टैक से आइटम पॉपिंग शुरू करेंगे और उन्हें प्रिंट करेंगे। यह काम करता है क्योंकि पथ मैट्रिक्स वर्टेक्स के मूल्य को संग्रहीत करता है जो किसी अन्य नोड से वी के लिए सबसे छोटा रास्ता साझा करता है। छद्म कोड होगा:
Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
S.push(Path[source][destination])
destination := Path[source][destination]
end while
print -> source
while S is not empty
print -> S.pop
end while
नकारात्मक बढ़त चक्र ढूँढना:
यह पता लगाने के लिए कि क्या कोई नकारात्मक बढ़त चक्र है, हमें दूरी मैट्रिक्स के मुख्य विकर्ण की जांच करने की आवश्यकता होगी। यदि विकर्ण पर कोई मान ऋणात्मक है, तो इसका मतलब है कि ग्राफ में एक नकारात्मक चक्र है।
जटिलता:
फ्लोयड-वारशॉ एल्गोरिथ्म की जटिलता हे (V and) और अंतरिक्ष जटिलता है: O (V²) ।
न्यूनतम वर्टेक्स कवर
मिनिमम वर्टेक्स कवर एक क्लासिक ग्राफ समस्या है। मान लीजिए, एक शहर में हमारे पास कुछ बिंदुओं को जोड़ने वाली कुछ सड़कें हैं। आइए किनारों का उपयोग करके सड़कों का प्रतिनिधित्व करते हैं और नोड्स का उपयोग करके बिंदु। आइए दो उदाहरण ग्राफ लेते हैं:
हम कुछ बिंदुओं पर चौकीदार लगाना चाहते हैं। एक चौकीदार बिंदु से जुड़ी सभी सड़कों की रखवाली कर सकता है। समस्या यह है कि सभी सड़कों को कवर करने के लिए चौकीदारों की न्यूनतम संख्या क्या है? यदि हम वॉचमैन को नोड ए , बी , एच , आई और जे पर सेट करते हैं , तो हम सभी सड़कों को कवर कर सकते हैं।
यह हमारा इष्टतम समाधान है। हमें पूरे शहर की सुरक्षा के लिए कम से कम 5 चौकीदार चाहिए। यह कैसे निर्धारित करें?
सबसे पहले, हमें यह समझने की जरूरत है कि यह एक एनपी-हार्ड समस्या है, अर्थात समस्या का कोई बहुपद समय समाधान नहीं है। लेकिन यदि ग्राफ़ एक ट्री था, तो इसका मतलब है कि अगर उसमें (n-1) नोड्स थे जहां n किनारों की संख्या है और ग्राफ़ में कोई चक्र नहीं है, तो हम इसे गतिशील प्रोग्रामिंग का उपयोग करके हल कर सकते हैं।
DP समाधान बनाने के लिए, हमें दो रणनीतियों का पालन करना होगा:
- यदि किसी नोड में कोई चौकीदार नहीं है, तो इससे जुड़े सभी नोड्स में एक चौकीदार होना चाहिए, या सभी सड़कों को कवर नहीं किया जाएगा। यू और वी जुड़े हुए हैं और यू किसी भी चौकीदार नहीं है, तो वी एक चौकीदार होना आवश्यक है।
- यदि नोड में एक चौकीदार है, तो इससे जुड़ा एक अलग नोड वॉचमैन हो सकता है या नहीं। इसका मतलब है कि चौकीदार होना जरूरी नहीं है, लेकिन यह फायदेमंद हो सकता है। यदि u और v जुड़े हुए हैं और u के पास एक चौकीदार है, तो हम जांच करेंगे और पाएंगे कि कौन सा हमारे लिए फायदेमंद है:
- चौकीदार को वी में सेट करना।
- चौकीदार की स्थापना v में नहीं।
चलिए एक पुनरावर्ती कार्य को परिभाषित करते हैं जिसमें यह बताया गया है कि वर्तमान नोड हम हैं या नहीं, इसमें एक चौकीदार है या नहीं। यहाँ:
F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.
फ़ंक्शन शेष नोड्स में चौकीदार की संख्या वापस कर देगा।
आइए एक उदाहरण पेड़ लें:
हम आसानी से कह सकते हैं कि अगर हम वॉचमैन को नोड- A पर नहीं रखते हैं, तो हमें वॉचमैन को नोड- B , C और D पर रखना होगा। हम कटौती कर सकते हैं:
F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0
यदि हमें चौकीदार को नोड- ए में नहीं रखा जाता है, तो इसके लिए हमें चौकीदार की संख्या की आवश्यकता होती है। हमने अंत में 0 जोड़ दिया है क्योंकि हमने अपने वर्तमान नोड में किसी भी चौकीदार को सेट नहीं किया है।
अब F(A,1)
अर्थ है, हम वॉचमैन को नोड- A में सेट करते हैं। उसके लिए, हम या तो सभी जुड़े नोड्स में चौकीदार सेट कर सकते हैं या हम नहीं करते हैं। हम वही लेंगे जो हमें कम से कम चौकीदार प्रदान करता है।
F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1
हम प्रत्येक नोड पर वॉचमैन की स्थापना और सेटिंग करके और इष्टतम मान लेकर जांच करते हैं।
एक बात हमें सावधान रहनी चाहिए, एक बार जब हम बच्चे के नोड पर जाते हैं, तो हम कभी भी पैरेंट नोड से पीछे नहीं हटेंगे। ऊपर के उदाहरण से, हम ए से बी पर गए, इसलिए माता-पिता [बी] = ए । तो हम B से A पर वापस नहीं जाएंगे।
आधार मामले का निर्धारण करने के लिए, हम देख सकते हैं कि, यदि एक नोड से, हम किसी अन्य नए नोड में नहीं जा सकते हैं, तो हम 1 वापस करेंगे यदि हमारे वर्तमान नोड में एक चौकीदार है, 0 अगर हमारे वर्तमान में कोई चौकीदार नहीं है नोड।
हमारे पेड़ के लिए आसन्न सूची होना बेहतर है। सूची को किनारे से चिह्नित करें। हम एक सरणी डी पी [n] [2] है, जहां n नोड्स गणना मान संग्रहीत और -1 के साथ यह प्रारंभ करने की संख्या को दर्शाता है जाएगा। माता-पिता और बच्चे के बीच संबंध को निरूपित करने के लिए हमारे पास एक माता-पिता [n] सरणी होगी। हमारे छद्म कोड की तरह दिखेगा:
Procedure f(u, isGuarded):
if edge[u].size is equal to 0 //node doesn't have any new edge
Return isGuarded
else if dp[u][isGuarded] is not equal to -1 //already calculated
Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
v := edge[u][i]
if v is not equal to parent[u] //not a parent
parent[v] := u
if isGuarded equals to 0 //not guarded, must set a watchman
sum := sum + f(v,1)
else //guarded, check both
sum := sum + min(f(v,1), f(v,0)
end if
end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]
यदि हम नोड- ए को रूट के रूप में दर्शाते हैं, तो हम फंक्शन को कॉल करेंगे: min(f(A,1), f(A,0))
। इसका मतलब है कि हम यह भी जांच करेंगे कि यह वॉचमैन को रूट नोड में सेट करने के लिए इष्टतम है या नहीं। यह हमारा डीपी समाधान है। यह समस्या अधिकतम मिलान एल्गोरिथ्म या अधिकतम-प्रवाह का उपयोग करके भी हल की जा सकती है।