प्रॉम्प्ट और संदर्भ
प्रत्येक निर्देशित एज में क्षमता और इकाई लागत होती है। समान प्रवाह वाले समाधानों में लागत को कम करते हुए, s से t तक प्रवाह की एक सीमा तक भेजें। रेसिड्यूअल रिवर्स एजेस, नकारात्मक लागतों, समानांतर एजेस, अगम्य सिंक और पूर्णांक ओवरफ्लो को संभालते हुए वास्तविक प्रवाह और लागत लौटाएं।
साक्षात्कारकर्ता क्या परीक्षण कर रहा है
- क्या आप रेसिड्यूअल एजेस और रिवर्स लागतों का सही निर्माण करते हैं।
- क्या आप नकारात्मक एजेस के साथ क्रमिक सबसे छोटे पथ (successive shortest paths) या पोटेंशियल्स का उपयोग कर सकते हैं।
- क्या आप अधिकतम-प्रवाह उद्देश्य को न्यूनतम-लागत टाई-ब्रेकर से अलग करते हैं।
- क्या आप जटिलता, ओवरफ्लो सीमाएं और प्रॉपर्टी-आधारित परीक्षण बताते हैं।
उत्तर देने से पहले स्पष्ट करने वाले प्रश्न
पूर्णांक क्षमताओं और लागतों, अनुमत नकारात्मक-लागत चक्रों, सटीक-सीमा आवश्यकताओं, ग्राफ के आकार और लागत सीमाओं की पुष्टि करें। यदि नकारात्मक चक्रों की अनुमति है, तो स्पष्ट करें कि क्या असीमित लागत में कमी मॉडल का हिस्सा है और प्रारंभिक पोटेंशियल्स कैसे प्राप्त किए जाते हैं।
30-सेकंड का उत्तर ढांचा
प्रत्येक इनपुट एज के लिए, एक फॉरवर्ड रेसिड्यूअल एज और नकारात्मक लागत के साथ एक शून्य-क्षमता वाली रिवर्स एज जोड़ें। रेसिड्यूअल ग्राफ में s-से-t तक सबसे छोटा पथ बार-बार खोजें और इसके बॉटलनेक को तब तक बढ़ाएं (augment करें) जब तक कि सीमा पूरी न हो जाए या कोई पथ न बचे। यदि लागतें नकारात्मक हो सकती हैं, तो Bellman-Ford के साथ प्रारंभिक पोटेंशियल्स की गणना करें, फिर एजेस का पुनर्वितरण (reweight) करें ताकि Dijkstra मान्य हो सके। जटिलता केवल सामान्य मैक्स-फ्लो जटिलता पर ही नहीं, बल्कि ऑग्मेंटेशन और सबसे छोटे पथ कार्यान्वयन पर निर्भर करती है।
चरण-दर-चरण गहन विश्लेषण
1. रेसिड्यूअल एज संरचना
गंतव्य, रिवर्स इंडेक्स, रेसिड्यूअल क्षमता और लागत को स्टोर करें। ऑग्मेंटेशन फॉरवर्ड क्षमता को कम करता है, रिवर्स क्षमता को बढ़ाता है, और कुल में प्रवाह गुणा लागत जोड़ता है। रिवर्स एजेस बाद के पथों को पहले के चयनों को पूर्ववत करने की अनुमति देती हैं, जो इष्टतम लागत के लिए आवश्यक है।
2. सबसे छोटे पथ और पोटेंशियल्स
गैर-नकारात्मक लागतों के साथ, Dijkstra पर्याप्त है। नकारात्मक लागतों लेकिन बिना किसी नकारात्मक चक्र के साथ, प्रत्येक वर्टेक्स के लिए एक पोटेंशियल बनाए रखें, कम की गई लागतों (reduced costs) का उपयोग करके सबसे छोटे पथों की गणना करें, फिर पोटेंशियल्स को अपडेट करें। नकारात्मक एजेस वाले ग्राफ पर कभी भी सीधे सामान्य Dijkstra लागू न करें।
3. ऑग्मेंटेशन और रोकना
ऑग्मेंटेशन राशि शेष सीमा, पथ बॉटलनेक और किसी भी बैच कैप का न्यूनतम मान है। जब कोई पथ मौजूद न हो तो रुकें और वास्तविक प्रवाह लौटाएं; यदि सटीक सीमा की आवश्यकता है, तो असाध्यता (infeasibility) की रिपोर्ट करें। एक विस्तृत पूर्णांक प्रकार (wide integer type) का उपयोग करें और लागत संचित करने से पहले गुणन की जांच करें।
उच्च गुणवत्ता वाला नमूना उत्तर
मैं रेसिड्यूअल एजेस को आसन्नता सूचियों (adjacency lists) में स्टोर करूंगा और प्रत्येक फॉरवर्ड और रिवर्स जोड़ी को एक साथ जोड़ूंगा। मुख्य लूप सकारात्मक-क्षमता वाली एजेस के बीच एक सबसे छोटा s-से-t पथ ढूंढता है, इसे ऑग्मेंट करता है और लागत को अपडेट करता है। गैर-नकारात्मक लागतों के लिए Dijkstra काम करता है; नकारात्मक लागतों और बिना किसी नकारात्मक चक्र के साथ, प्रारंभिक पोटेंशियल्स की गणना करें और कम की गई लागतों को गैर-नकारात्मक रखें। प्रत्येक ऑग्मेंटेशन को शेष मांग और पथ बॉटलनेक द्वारा सीमित करें। यदि सिंक अगम्य हो जाता है, तो वास्तविक प्रवाह लौटाएं और अपूर्ण लक्ष्य को असाध्य के रूप में चिह्नित करें। परीक्षण रिवर्स कैंसिलेशन, समानांतर एजेस, शून्य क्षमता, नकारात्मक लागत, डिस्कनेक्ट किए गए ग्राफ, आंशिक प्रवाह, नकारात्मक-चक्र मान्यताओं और बड़ी-लागत ओवरफ्लो को कवर करते हैं। यह मॉडल OR-Tools के न्यूनतम-लागत प्रवाह फॉर्मूलेशन से मेल खाता है, लेकिन जटिलता में वर्टेक्स, एज और ऑग्मेंटेशन कारकों का नाम होना चाहिए; यह संख्यात्मक क्षमताओं में स्वचालित रूप से बहुपद (polynomial) नहीं है।
सामान्य गलतियाँ
- रिवर्स एजेस को भूल जाना या उन्हें नकारात्मक के बजाय सकारात्मक लागत सौंपना।
- रेसिड्यूअल एजेस में नकारात्मक लागत होने पर सीधे Dijkstra चलाना।
- बिना किसी औचित्य के प्रति सबसे छोटे पथ पर केवल एक इकाई को ऑग्मेंट करना।
- अधिकतम प्रवाह और न्यूनतम लागत को एक अविभाजित सॉर्ट कुंजी के रूप में मानना।
- एक संकीर्ण पूर्णांक प्रकार में बड़े क्षमता-गुणा-लागत मानों को संचित करना।
फॉलो-अप प्रश्न और प्रतिक्रियाएं
एक रिवर्स एज पहले के चयन को कैसे ठीक कर सकती है?
यह पहले भेजे गए प्रवाह को वापस लेने का प्रतिनिधित्व करती है और उस प्रवाह की लागत को नकारती है। बाद का सबसे छोटा पथ समाधान को पुनर्व्यवस्थित करने और कुल लागत को कम करने के लिए इसका उपयोग कर सकता है।
आपको Bellman-Ford की आवश्यकता कब होती है?
जब प्रारंभिक रेसिड्यूअल ग्राफ में नकारात्मक-लागत वाली एजेस हों लेकिन कोई नकारात्मक चक्र न हो, तो प्रारंभिक पोटेंशियल्स की गणना के लिए इसका या किसी समकक्ष विधि का उपयोग करें; इसके बाद गैर-नकारात्मक कम की गई लागतें Dijkstra की अनुमति देती हैं।
क्या होगा यदि अनुरोधित प्रवाह तक नहीं पहुंचा जा सकता है?
रुकें और एक स्पष्ट असाध्य (infeasible) परिणाम के साथ वास्तविक प्रवाह और लागत लौटाएं। यदि व्यवसाय को लक्ष्य की आवश्यकता है, तो कॉलर को आंशिक प्रवाह को सफलता मानने के बजाय रोलबैक करना चाहिए या एक फ़ॉलबैक नेटवर्क चुनना चाहिए।