परिसंचरण समस्या: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Generalization of network flow problems}} | {{Short description|Generalization of network flow problems}} | ||
'''परिसंचरण समस्या''' और इसके प्रकार [[प्रवाह नेटवर्क]] समस्याओं का | '''परिसंचरण समस्या''' और इसके प्रकार [[प्रवाह नेटवर्क]] समस्याओं का ऐसा सामान्यीकरण हैं, जिसमें किनारे के प्रवाह पर निचली सीमा की अतिरिक्त बाधा होती है, और स्रोत और सिंक के लिए प्रवाह संरक्षण भी आवश्यक होता है (अथार्त कोई विशेष नोड नहीं होते हैं)। समस्या के भिन्न रूप में, नेटवर्क के माध्यम से अनेक वस्तुओं का प्रवाह होता है, और प्रवाह पर व्यय होती है। | ||
== परिभाषा == | == परिभाषा == | ||
दिया गया प्रवाह नेटवर्क <math>G(V,E)</math> साथ: | दिया गया प्रवाह नेटवर्क <math>G(V,E)</math> साथ: | ||
:<math>l(v,w)</math>, नोड <math>v</math> से नोड <math>w</math> तक प्रवाह पर निचली सीमा। | :<math>l(v,w)</math>, नोड <math>v</math> से नोड <math>w</math> तक प्रवाह पर निचली सीमा। | ||
:<math>u(v,w)</math>, नोड <math>v</math> से नोड <math>w</math> तक प्रवाह पर ऊपरी सीमा। | :<math>u(v,w)</math>, नोड <math>v</math> से नोड <math>w</math> तक प्रवाह पर ऊपरी सीमा। | ||
:<math>c(v,w)</math>, प्रवाह की | :<math>c(v,w)</math>, प्रवाह की इकाई की व्यय <math>(v,w)</math> है | ||
और बाधाएँ: | और बाधाएँ: | ||
| Line 17: | Line 17: | ||
समस्या के न्यूनतम निवेश संस्करण में, न्यूनतम करें | समस्या के न्यूनतम निवेश संस्करण में, न्यूनतम करें | ||
: <math>\sum_{(v,w) \in E} c(v,w) \cdot f(v,w).</math> | : <math>\sum_{(v,w) \in E} c(v,w) \cdot f(v,w). | ||
</math> | |||
| Line 28: | Line 30: | ||
| <math>\,f(v,w) = \sum_i f_i(v,w)</math> || The total flow. | | <math>\,f(v,w) = \sum_i f_i(v,w)</math> || The total flow. | ||
|} | |} | ||
वस्तु के प्रत्येक प्रवाह पर | वस्तु के प्रत्येक प्रवाह पर निचली सीमा भी होती है। | ||
:{| | :{| | ||
| Line 39: | Line 41: | ||
== समाधान == | == समाधान == | ||
परिसंचरण समस्या के लिए, | परिसंचरण समस्या के लिए, अनेक बहुपद एल्गोरिदम विकसित किए गए हैं (उदाहरण के लिए, एडमंड्स-कार्प एल्गोरिदम, 1972; टार्जन 1987-1988)। टार्डोस ने पहला दृढ़तापूर्वक बहुपद एल्गोरिथ्म पाया जाता है।<ref name="Ta85">{{cite journal | author = Éva Tardos | title = एक सशक्त बहुपद न्यूनतम लागत संचलन एल्गोरिथ्म| journal = Combinatorica | volume = 5 | pages = 247–255 | doi = 10.1007/BF02579369}}</ref> | ||
एकाधिक वस्तुओं के स्थिति में, समस्या पूर्णांक प्रवाह के लिए एनपी-पूर्ण है।<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = समय सारणी की जटिलता और बहु-वस्तु प्रवाह समस्याओं पर| publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | pages = 691–703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048 | issue = 4 | url-status = dead | archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 | archivedate = 2013-01-12 }}</ref> भिन्नात्मक प्रवाह के लिए, यह बहुपद समय में हल करने योग्य है, क्योंकि कोई समस्या को [[रैखिक प्रोग्रामिंग]] के रूप में तैयार कर सकता है। | एकाधिक वस्तुओं के स्थिति में, समस्या पूर्णांक प्रवाह के लिए एनपी-पूर्ण है।<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = समय सारणी की जटिलता और बहु-वस्तु प्रवाह समस्याओं पर| publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | pages = 691–703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048 | issue = 4 | url-status = dead | archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 | archivedate = 2013-01-12 }}</ref> भिन्नात्मक प्रवाह के लिए, यह बहुपद समय में हल करने योग्य है, क्योंकि कोई समस्या को [[रैखिक प्रोग्रामिंग]] के रूप में तैयार कर सकता है। | ||
| Line 50: | Line 52: | ||
* न्यूनतम निवेश संचलन समस्या - एक ही वस्तु का उपयोग करें | * न्यूनतम निवेश संचलन समस्या - एक ही वस्तु का उपयोग करें | ||
* मल्टी-कमोडिटी सर्कुलेशन - निवेश को अनुकूलित किए बिना हल करें। | * मल्टी-कमोडिटी सर्कुलेशन - निवेश को अनुकूलित किए बिना हल करें। | ||
* सरल परिचालन - बस एक वस्तु का उपयोग करें, और कोई | * सरल परिचालन - बस एक वस्तु का उपयोग करें, और कोई मान नहीं है। | ||
*बहु-वस्तु प्रवाह - यदि <math>K_i(s_i,t_i,d_i)</math> से <math>t_i</math> तक वस्तु <math>i</math> के लिए <math>d_i</math> की मांग को दर्शाता है, तो एक बनाएं किनारा <math>(t_i,s_i)</math> के | *बहु-वस्तु प्रवाह - यदि <math>K_i(s_i,t_i,d_i)</math> से <math>t_i</math> तक वस्तु <math>i</math> के लिए <math>d_i</math> की मांग को दर्शाता है, तो एक बनाएं किनारा <math>(t_i,s_i)</math> के साथ <math>l_i(t_i,s_i) = u(t_i,s_i) = d_i</math> सभी वस्तुओं के लिए <math>i</math> मान लीजिए अन्य सभी किनारों के लिए <math>l_i(u,v)=0</math> है। | ||
* [[न्यूनतम लागत बहु-वस्तु प्रवाह समस्या|न्यूनतम निवेश बहु-वस्तु प्रवाह समस्या]] - जैसा कि ऊपर बताया गया है, किंतु निवेश कम से कम करें। | * [[न्यूनतम लागत बहु-वस्तु प्रवाह समस्या|न्यूनतम निवेश बहु-वस्तु प्रवाह समस्या]] - जैसा कि ऊपर बताया गया है, किंतु निवेश कम से कम करें। | ||
* [[न्यूनतम लागत प्रवाह समस्या|न्यूनतम निवेश प्रवाह समस्या]] - ऊपर के अनुसार, 1 वस्तु के साथ है। | * [[न्यूनतम लागत प्रवाह समस्या|न्यूनतम निवेश प्रवाह समस्या]] - ऊपर के अनुसार, 1 वस्तु के साथ है। | ||
* [[अधिकतम प्रवाह समस्या]] - सभी निवेश को 0 पर सेट करें, और सिंक से एक किनारा <math>t</math> जोड़ें जिससे स्रोत <math>s</math> के लिए | * [[अधिकतम प्रवाह समस्या]] - सभी निवेश को 0 पर सेट करें, और सिंक से एक किनारा <math>t</math> जोड़ें जिससे स्रोत <math>s</math> के लिए <math>l(t,s)=0</math>, <math>u(t,s)=</math>∞ और <math>c(t,s)=-1</math>. साथ है | ||
*न्यूनतम निवेश अधिकतम प्रवाह समस्या - सबसे पहले अधिकतम प्रवाह राशि <math>m</math> ज्ञात करें। फिर <math>l(t,s)=u(t,s)=m</math> और <math>c(t,s)=0</math>. के साथ हल करें। | *न्यूनतम निवेश अधिकतम प्रवाह समस्या - सबसे पहले अधिकतम प्रवाह राशि <math>m</math> ज्ञात करें। फिर <math>l(t,s)=u(t,s)=m</math> और <math>c(t,s)=0</math>. के साथ हल करें। | ||
*एकल-स्रोत सबसे छोटा पथ - मान लीजिए कि ग्राफ़ में सभी किनारों के लिए <math>l(u,v)=0</math> और <math>c(u,v)=1</math> है, और <math>l(t,s)=u(t,s)=1</math> और <math>c(t,s)=0</math> के साथ एक किनारा <math>(t,s)</math> जोड़ें | *एकल-स्रोत सबसे छोटा पथ - मान लीजिए कि ग्राफ़ में सभी किनारों के लिए <math>l(u,v)=0</math> और <math>c(u,v)=1</math> है, और <math>l(t,s)=u(t,s)=1</math> और <math>c(t,s)=0</math> के साथ एक किनारा <math>(t,s)</math> जोड़ें | ||
| Line 61: | Line 63: | ||
== संदर्भ == | == संदर्भ == | ||
<references/> | <references/> | ||
[[Category:Created On 26/07/2023]] | [[Category:Created On 26/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:गणितीय समस्याएं]] | |||
[[Category:नेटवर्क प्रवाह समस्या]] | |||
Latest revision as of 11:27, 14 August 2023
परिसंचरण समस्या और इसके प्रकार प्रवाह नेटवर्क समस्याओं का ऐसा सामान्यीकरण हैं, जिसमें किनारे के प्रवाह पर निचली सीमा की अतिरिक्त बाधा होती है, और स्रोत और सिंक के लिए प्रवाह संरक्षण भी आवश्यक होता है (अथार्त कोई विशेष नोड नहीं होते हैं)। समस्या के भिन्न रूप में, नेटवर्क के माध्यम से अनेक वस्तुओं का प्रवाह होता है, और प्रवाह पर व्यय होती है।
परिभाषा
दिया गया प्रवाह नेटवर्क साथ:
- , नोड से नोड तक प्रवाह पर निचली सीमा।
- , नोड से नोड तक प्रवाह पर ऊपरी सीमा।
- , प्रवाह की इकाई की व्यय है
और बाधाएँ:
- ,
- (प्रवाह नोड्स में प्रकट या विलुप्त नहीं हो सकता है)।
बाधाओं को संतुष्ट करने वाले प्रवाह असाइनमेंट को खोजने से दी गई परिसंचरण समस्या का समाधान मिलता है।
समस्या के न्यूनतम निवेश संस्करण में, न्यूनतम करें
मल्टी-कमोडिटी सर्कुलेशन
बहु-वस्तु परिसंचरण समस्या में, आपको व्यक्तिगत वस्तुओं के प्रवाह पर भी दृष्टि रखने की आवश्यकता है:
The flow of commodity from to . The total flow.
वस्तु के प्रत्येक प्रवाह पर निचली सीमा भी होती है।
वस्तुओं के लिए संरक्षण बाधा को व्यक्तिगत रूप से बनाय रखा जाना चाहिए:
समाधान
परिसंचरण समस्या के लिए, अनेक बहुपद एल्गोरिदम विकसित किए गए हैं (उदाहरण के लिए, एडमंड्स-कार्प एल्गोरिदम, 1972; टार्जन 1987-1988)। टार्डोस ने पहला दृढ़तापूर्वक बहुपद एल्गोरिथ्म पाया जाता है।[1]
एकाधिक वस्तुओं के स्थिति में, समस्या पूर्णांक प्रवाह के लिए एनपी-पूर्ण है।[2] भिन्नात्मक प्रवाह के लिए, यह बहुपद समय में हल करने योग्य है, क्योंकि कोई समस्या को रैखिक प्रोग्रामिंग के रूप में तैयार कर सकता है।
संबंधित समस्याएँ
नीचे कुछ समस्याएं दी गई हैं, और ऊपर दिए गए सामान्य सर्कुलेशन सेटअप के साथ उन्हें कैसे हल किया जाए।
- न्यूनतम निवेश मल्टी-कमोडिटी सर्कुलेशन समस्या - ऊपर दिए गए सभी बाधाओं का उपयोग करना है।
- न्यूनतम निवेश संचलन समस्या - एक ही वस्तु का उपयोग करें
- मल्टी-कमोडिटी सर्कुलेशन - निवेश को अनुकूलित किए बिना हल करें।
- सरल परिचालन - बस एक वस्तु का उपयोग करें, और कोई मान नहीं है।
- बहु-वस्तु प्रवाह - यदि से तक वस्तु के लिए की मांग को दर्शाता है, तो एक बनाएं किनारा के साथ सभी वस्तुओं के लिए मान लीजिए अन्य सभी किनारों के लिए है।
- न्यूनतम निवेश बहु-वस्तु प्रवाह समस्या - जैसा कि ऊपर बताया गया है, किंतु निवेश कम से कम करें।
- न्यूनतम निवेश प्रवाह समस्या - ऊपर के अनुसार, 1 वस्तु के साथ है।
- अधिकतम प्रवाह समस्या - सभी निवेश को 0 पर सेट करें, और सिंक से एक किनारा जोड़ें जिससे स्रोत के लिए , ∞ और . साथ है
- न्यूनतम निवेश अधिकतम प्रवाह समस्या - सबसे पहले अधिकतम प्रवाह राशि ज्ञात करें। फिर और . के साथ हल करें।
- एकल-स्रोत सबसे छोटा पथ - मान लीजिए कि ग्राफ़ में सभी किनारों के लिए और है, और और के साथ एक किनारा जोड़ें
- सभी जोड़े सबसे छोटा पथ - सभी क्षमताओं को असीमित होने दें, और वस्तुओं के लिए 1 का प्रवाह खोजें, प्रत्येक जोड़ी नोड्स के लिए एक है ।
संदर्भ
- ↑ Éva Tardos. "एक सशक्त बहुपद न्यूनतम लागत संचलन एल्गोरिथ्म". Combinatorica. 5: 247–255. doi:10.1007/BF02579369.
- ↑ S. Even and A. Itai and A. Shamir (1976). "समय सारणी की जटिलता और बहु-वस्तु प्रवाह समस्याओं पर". SIAM Journal on Computing. SIAM. 5 (4): 691–703. doi:10.1137/0205048. Archived from the original on 2013-01-12.
