नेटवर्क में अधिकतम प्रवाह को खोजने के लिए एल्गोरिथ्म को लागू करने के तरीके

परिचय

अधिकतम प्रवाह की समस्या शास्त्रीय है और इसमें कई अनुप्रयोग हैं। मैं आपको समस्या कथन याद दिलाता हूं। गैर-नकारात्मक भार (थ्रूपुट) के साथ एक भारित निर्देशित ग्राफ दिया गया है। दो कोने प्रतिष्ठित हैं: स्रोत S और सिंक T ऐसा है कि कोई भी अन्य शीर्ष S से T के मार्ग पर स्थित है । इस तरह के गुणों के साथ एक प्रवाह एक फ़ंक्शन F: V x V है

1. बैंडविड्थ की सीमा। एक किनारे के साथ प्रवाह इसके (किनारे) थ्रूपुट से अधिक नहीं हो सकता है।
2. Antisymmetry। प्रत्येक किनारे के लिए (यू, वी): एफ (यू, वी) =-एफ (वी, यू)।
3. बचत की धारा। प्रत्येक शीर्ष के लिए ( एस और टी को छोड़कर), आने वाली धारा (नकारात्मक) की मात्रा आउटगोइंग स्ट्रीम (सकारात्मक) की संख्या के बराबर है। अर्थात्, प्रत्येक शीर्ष के लिए प्रवाह की बीजगणितीय राशि ( एस और टी को छोड़कर) शून्य है।

इस पोस्ट में आप समस्या के कार्यान्वयन से खुद को परिचित कर सकते हैं।



हम सीधे विशिष्ट कार्यों के लिए आगे बढ़ते हैं, जो नेटवर्क में अधिकतम प्रवाह को खोजने के लिए एक एल्गोरिथ्म में कम हो जाते हैं। ऐसे कार्यों में प्रवाह की पहचान करना अक्सर आसान नहीं होता है।

कार्य

1. अधिकतम मिलान की समस्या। प्रवेश द्वार पर एन दिया जाता है - लड़कों की संख्या, एम - लड़कियों की संख्या और किस लड़के के साथ लड़कियों में से कौन नृत्य करना चाहता है (कई हो सकते हैं)। एक साथ नृत्य करने वाले जोड़ों की अधिकतम संख्या निर्धारित करना आवश्यक है।
   
   
   
   
   
   

   निर्णय

   
   
   इस समस्या को हल करने के लिए, आप कुह्न एल्गोरिथ्म का उपयोग कर सकते हैं, लेकिन जब से हमने एक धारा में सब कुछ कम करना शुरू किया है - चलो इसे करते हैं। इसके लिए, पर्याप्त स्रोत और नाली नहीं है। चलो उन्हें जोड़ें! "बाईं ओर" हम एक काल्पनिक शीर्ष जोड़ते हैं और वजन करने वाले सभी लड़कों को पसलियों को आकर्षित करते हैं। 1. लड़कों से लेकर लड़कियों तक की पसलियां होती हैं और उन्हें एक ही कीमत मिलती है। और लड़कियों की पसलियों से लेकर नाली तक की भी कीमत होती है। समस्या का जवाब स्रोत और नाली के बीच अधिकतम प्रवाह है ।
2. क्षतिग्रस्त लकड़ी की छत। NxM फर्श पर, कुछ कोशिकाएं क्षतिग्रस्त हो सकती हैं। उन्हें नई टाइलों से ढंकना चाहिए। टाइलें A की कीमत पर 2x1 आकार में हैं (आप घुमा सकते हैं, लेकिन काट नहीं सकते हैं) और B.x की कीमत पर 1x1 है। सवाल यह है कि खराब लकड़ी की छत बिछाने के लिए आपको न्यूनतम राशि खर्च करने की क्या आवश्यकता है। स्वाभाविक रूप से, नई टाइल्स को किसी अन्य टाइल को ओवरलैप नहीं करना चाहिए।
   
   
   
   

   निर्णय

   
   
   सबसे पहले, सुनिश्चित करें कि 2 * बी> ए। अन्यथा, यह केवल 1x1 टाइल के लिए अधिक लाभदायक है और विचार करने के लिए अधिक कुछ नहीं है। अगला, हमारा कार्य ए की कीमत पर टाइल्स की संख्या को अधिकतम करना है।
   
   एक चेसबोर्ड के सिद्धांत पर हमारे लकड़ी की छत को रंग दें। जाहिर है, तब 2x1 टाइल का एक छोर काले पिंजरे पर, दूसरा सफेद पर होगा। तो, हम एक द्विदलीय ग्राफ का निर्माण करेंगे, जिसमें से एक हिस्सा में सफेद कोशिकाएं होंगी, दूसरे - काले वाले। हम आसन्न कोशिकाओं के बीच 1 पसलियों का वजन करते हैं। अनन्तता (एक काफी सामान्य चाल) पर सफेद चोटियों के किनारों के साथ एक स्रोत जोड़ें और अनंत में भी वजन वाले काले कोशिकाओं के किनारों के साथ एक नाली। स्रोत और नाली के बीच पाए जाने वाले अधिकतम प्रवाह का मान होने दें। यही है, हमने टाइलों की संख्या 2x1 पाई। समस्या का उत्तर f * A + (Kf) * B है, जहाँ K क्षतिग्रस्त कोशिकाओं की कुल संख्या है।
   
   स्रोत: खार्कोव विंटर प्रोग्रामिंग स्कूल, 2009, दिन 3
   
   
3. पेंटिंग का काम। काले या सफेद रंग की कोशिकाओं के साथ एक एन * एम मैट्रिक्स दिया। डब्ल्यू सफेद में एक काले वर्ग को दोहराने की कीमत है, बी - काले में सफेद। पुनरावृत्ति के बाद, विभिन्न रंगों के सभी आसन्न वर्गों के बीच, आपको जी की कीमत पर एक ग्रे लाइन खींचनी होगी। न्यूनतम राशि खर्च करने के लिए आपको मैट्रिक्स को इतनी तेजी से (या कुछ भी नहीं) करने की आवश्यकता है।
   
   
   
   
   
   

   निर्णय

   
   
   चरम स्थिति: यदि मैट्रिक्स समान रंग का है - उत्तर 0 है।
   
   एक डमी स्रोत और स्टॉक जोड़ें। स्रोत से सभी सफेद चोटियों तक हम बी में वजन वाले किनारों को आकर्षित करते हैं (काले रंग के लिए पुनरावृत्ति की कीमत)। काली चोटियों से लेकर नाले तक डब्ल्यू में वजन करने वाली पसलियां (सफेद रंग को दोहराते हुए)। और सभी पड़ोसी कोने के बीच (चाहे वे एक ही या अलग-अलग रंगों के हों) - हम जी (ग्रे लाइन) में एक वजन रखते हैं। अधिकतम प्रवाह की भयावहता समस्या का जवाब होगी।
   
   स्रोत: ऑल-यूक्रेनी स्कूल ओलंपियाड इन इन्फोर्मेटिक्स, 2007, दिन 1
   
   
4. कंधे पर कसना के साथ समस्या। मान लें कि आपको अधिकतम प्रवाह खोजने की आवश्यकता है और चोटियों ने एक सीमा लगा दी कि वे कितना याद कर सकते हैं।
   
   
   
   

   निर्णय

   
   
   हम सभी को प्रत्येक शीर्ष को दो भागों में विभाजित करने की आवश्यकता है, और उनके बीच एक धार डालें, इस शीर्ष की बैंडविड्थ सीमा में वजन करें
5. न्यूनतम कटौती। दान गणना। कितने कोने हटाए जाने चाहिए ताकि A से B तक कोई रास्ता न हो?
   
   
   
   

   निर्णय

   
   
   शास्त्रीय न्यूनतम कट समस्या में, किनारों को हटा दिया जाना चाहिए। कोई बात नहीं! हम कोने को 2 में विभाजित करते हैं, और उनके बीच एक किनारा लगाते हैं, वजन 1. तब समस्या का उत्तर ग्राफ में न्यूनतम कटौती (जो अधिकतम प्रवाह है) को खोजना है।
   
   स्रोत: खार्कोव विंटर प्रोग्रामिंग स्कूल, 2009, दिन 3
   
   
6. छंद का लेखक। एक प्रारंभिक राज्य ए और एक अंतिम बी के साथ एक नियतात्मक परिमित राज्य मशीन है । प्रत्येक संक्रमण को संख्याओं के एक (i, j, k) द्वारा परिभाषित किया जाता है, राज्य i से राज्य j के किनारे k के साथ एक संक्रमण।
   
   किनारे के किनारे से i से j तक ऑटोमेटन से गुजरने के बाद, किनारे k के साथ i से सभी संक्रमण मिट जाते हैं, साथ ही किनारे k के साथ j करने के लिए सभी संक्रमण। ऐसे ऑटोमेटन द्वारा ए से बी तक के रास्तों की संख्या में कटौती करना आवश्यक है।
   
   
   
   

   निर्णय

   
   
   कार्य अधिकतम पथ खोजने के लिए है, और एक ही रंग के एक से अधिक किनारे एक शीर्ष से बाहर नहीं जाते हैं। हम अधिकतम प्रवाह को खोजने के लिए समस्या को कम करते हैं। प्रत्येक वर्टेक्स के लिए, पुनर्निर्माण नेटवर्क में k + 1 वर्टेक्स बनाएं। पहला शीर्ष इनपुट होगा, शेष कोने रंगों का प्रतिनिधित्व करेंगे। प्रवेश द्वार के ऊपर से, रंग के अनुरूप कश्मीर के प्रत्येक कोने में 1 के थ्रूपुट के साथ एक किनारे खींचें। रंग i के अनुरूप शीर्ष से, हम किनारों के छोरों के इनपुट के लिए रंग I के सभी किनारों को आकर्षित करते हैं। इस तरह के नेटवर्क में अधिकतम प्रवाह प्राप्त करने के बाद, हम आवश्यक संपत्ति को संतुष्ट करने वाले अधिकतम पथ प्राप्त करते हैं।
   
   स्रोत: खार्कोव विंटर प्रोग्रामिंग स्कूल, 2009, दिन 4
   
   
7. सिक्का जमा करना। एन कलेक्टर और एम प्रकार के सिक्के हैं। क्लब में शामिल होने के लिए, आपके पास प्रत्येक प्रकार का कम से कम एक सिक्का होना चाहिए। आप (आपके पास नंबर 1 है) कलेक्टरों के साथ उपलब्ध सिक्कों का आदान-प्रदान कर सकता है। कोई भी कलेक्टर आपके सिक्के b के लिए अपने सिक्के का आदान-प्रदान करेगा यदि उसके पास एक प्रकार का एक से अधिक सिक्का है और उसके पास टाइप b का एक भी सिक्का नहीं है। आप, बदले में, इस नियम का उल्लंघन कर सकते हैं। आपको सभी कलेक्टरों की ज्ञात स्थिति से यथासंभव कई प्रकार के सिक्के एकत्र करने की आवश्यकता है।
   
   
   
   

   निर्णय

   
   
   एक नेटवर्क बनाएँ। प्रत्येक प्रकार के सिक्के के लिए, एक शीर्ष बनाएं। ये टॉप आपके सिक्कों से मैच करेगा। संभव के रूप में कई अनूठे सिक्के एकत्र करना आवश्यक है, इसलिए प्रत्येक ऐसे शीर्ष से नाली में एक बैंडविड्थ किनारे 1 को ड्रा करें। आपके पास शुरू में मौजूद सिक्कों के अनुरूप कोने में, एक किनारे खींचिए जिसका थ्रूपुट आपके पास मौजूद ऐसे सिक्कों की संख्या के बराबर है।
   
   क्लब के प्रत्येक सदस्य के लिए (1 को छोड़कर, वह है, आप), हमारे पास एक शीर्ष होगा। यह शीर्ष एक से अधिक सिक्के नहीं ले सकता है, जो इसके पास नहीं है और न ही दे
   
   k-1 के सिक्कों से अधिक नहीं, जिनमें से k (k> 1) है। स्वाभाविक रूप से, क्लब का एक सदस्य एक प्राप्त के बदले में एक सिक्का देता है।
   
   इस प्रकार, इस तरह के प्रत्येक शीर्ष पर, आपको सिक्कों के अनुरूप एक बैंडविड्थ किनारे 1 को खींचना होगा जो इस क्लब के सदस्य के पास नहीं है। और इन छोरों से, सिक्कों की तुलना में कश्मीर _i - 1 के शीर्ष पर किनारों के साथ किनारों को खींचना आवश्यक है, जो कि क्लब के सदस्य के पास एक से अधिक हैं।
   
   निर्मित नेटवर्क क्लब में विनिमय प्रक्रियाओं को दर्शाता है। इस तरह के नेटवर्क में अधिकतम प्रवाह आपके द्वारा एकत्र किए जाने वाले सिक्कों की अधिकतम संख्या के बराबर होगा।
   
   स्रोत: खार्कोव विंटर प्रोग्रामिंग स्कूल, 2009, दिन 4
   
   
8. सर्कुलेशन। रिएक्टर कूलिंग सिस्टम नोड्स को जोड़ने वाले पाइप का एक सेट है। तरल पाइप के माध्यम से बहती है, और प्रत्येक पाइप के लिए, जिस दिशा में इसे प्रवाह करना चाहिए, वह कड़ाई से परिभाषित किया गया है। शीतलन प्रणाली के नोड्स को 1 से एन तक गिना जाता है। शीतलन प्रणाली को डिजाइन किया जाना चाहिए ताकि प्रत्येक नोड प्रति इकाई समय के लिए नोड में तरल प्रवाह की मात्रा नोड से बहने वाले तरल की मात्रा के बराबर हो। प्रत्येक पाइप में एक थ्रूपुट c _{ij होता है} । इसके अलावा, पर्याप्त शीतलन सुनिश्चित करने के लिए, यह आवश्यक है कि पाइप के माध्यम से प्रति यूनिट समय कम से कम एल _आईजे इकाइयां प्रवाहित हों। यही है, एक पाइप के लिए जो i-th नोड से जे-वें तक जाता है, l _ij i f _ij be c _ij संतुष्ट होना चाहिए।
   
   शीतलन प्रणाली का विवरण दिया गया है। यह पता लगाना आवश्यक है कि पाइप के माध्यम से तरल को कैसे बहने दिया जाए ताकि सभी संकेतित शर्तों को पूरा किया जा सके।
   
   
   
   

   निर्णय

   
   
   यह किनारों पर दिए गए कम प्रतिबंधों के साथ नेटवर्क में संचलन खोजने की समस्या है। यदि खंड [एल, आर] में किनारे (यू, वी) के साथ गुजरना चाहिए, तो पुनर्निर्माण नेटवर्क में तीन किनारे होंगे (जहां, वजन,): (यू, वी, आर - एल), (एस, वी, एल) ), (यू, टी, एल)। एस, टी इसके अलावा क्रमशः पेश किए गए सिंक और स्रोत हैं। वास्तव में, हम किनारे के साथ आवश्यक न्यूनतम प्रवाह पास करते हैं, और फिर इसे संतुलित करते हैं ताकि परिसंचरण प्राप्त हो सके।
   
   स्रोत: खार्कोव विंटर प्रोग्रामिंग स्कूल, 2009, दिन 4
   
   
9. फिर से नाचना। पार्टी में एन लड़कों और लड़कियों को आमंत्रित किया जाता है। वे कुछ राउंड डांस करना चाहते हैं।
   
   प्रत्येक दौर में, मेहमानों को नाचने वाले जोड़ों में विभाजित किया जाता है। प्रत्येक अतिथि को किसी न किसी जोड़ी में होना चाहिए, प्रत्येक जोड़ी में एक लड़का और एक लड़की होनी चाहिए। प्रत्येक दौर में, प्रत्येक लड़के को एक अलग लड़की के साथ नृत्य करना चाहिए। कुछ लड़के और लड़कियां एक दूसरे को पसंद नहीं करते हैं। प्रत्येक लड़का k लड़कियों से अधिक नहीं के साथ नृत्य कर सकता है जो उसे पसंद नहीं है। इसी तरह, प्रत्येक लड़की k लड़कों की तुलना में अधिक नहीं के साथ नृत्य कर सकती है जो उसे पसंद नहीं है।
   
   इस बारे में जानकारी है कि क्या i-th लड़का और j-th लड़की (1 j i, j) n) एक दूसरे की तरह हैं। सबसे बड़ी संख्या में राउंड पाएं जो आप किसी पार्टी में नृत्य कर सकते हैं।
   
   
   
   

   निर्णय

   
   
   निम्नलिखित समस्या पर विचार करें: क्या नृत्य बिल्कुल एम दौरों में जारी रह सकता है? यदि हम इस प्रश्न का उत्तर दे सकते हैं, तो द्विआधारी खोज से हम सबसे बड़ा मी पाते हैं जिसके लिए नृत्य संभव है।
   
   हम एक ग्राफ बनाते हैं जिसमें एक स्रोत और एक सिंक (काला कोने) होता है। लाल चोटियाँ लड़कों का प्रतिनिधित्व करती हैं, भूरे रंग की चोटियाँ लड़कियों का प्रतिनिधित्व करती हैं। यदि लड़का और लड़की एक दूसरे को पसंद करते हैं, तो हम उनके बीच इकाई क्षमता के एक छोर को खींचते हैं (चित्र में ये दो किनारे हैं - ऊपरी और निचले)। अन्यथा, चित्र में दिखाए गए अनुसार नीले और हरे रंग के कोने जोड़ें और किनारों के बैंडविड्थ को इसी नीले और हरे रंग के कोने से 1 के बीच सेट करें।
   
   नीली और हरी चोटियाँ एक "सुरक्षात्मक" स्तर बनाती हैं। उन लड़कियों के साथ लड़कों का संबंध जो एक दूसरे को पसंद नहीं करते हैं वे सुरक्षात्मक स्तर के किनारों के साथ जाएंगे। प्रत्येक लड़का k लड़कियों से अधिक नहीं के साथ नृत्य कर सकता है जो उसे पसंद नहीं है। लाल और नीले, हरे और ग्रे चोटियों के बीच किनारों की बैंडविड्थ को k के बराबर सेट करें। इस प्रकार, प्रत्येक लड़के और प्रत्येक लड़की के बीच, किनारे से सीधे या सुरक्षात्मक स्तर की चोटियों के माध्यम से एक कनेक्शन स्थापित किया जाएगा।
   
   बिल्कुल एम दौर में नृत्य जारी रहना चाहिए। स्रोत और लाल चोटियों के बीच किनारों की बैंडविड्थ निर्धारित करें, साथ ही साथ ग्रे चोटियों और नाली के बीच, मी के बराबर।
   
   
   
   ग्राफ़ में अधिकतम प्रवाह का पता लगाएं। यदि केवल और केवल अधिकतम प्रवाह n * m के बराबर है, जहां n लड़कों की संख्या है, तो नाच बिल्कुल m राउंड में जारी रह सकता है।
   
   स्रोत: सेवस्तोपोल समर प्रोग्रामिंग स्कूल, 2010, दिन 4
   
   

निष्कर्ष

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