पथ को बढ़ाने में वास्तव में क्या है?

Question

जब computing network flows बारे में बात कर, Algorithm Design Manual का कहना है:

पारंपरिक नेटवर्क प्रवाह एल्गोरिदम बढ़ाने रास्तों, और बार बार रों टी के लिए से सकारात्मक क्षमता के लिए एक रास्ता खोजने और प्रवाह में जोड़ने के विचार पर आधारित होते हैं । यह दिखाया जा सकता है कि नेटवर्क के माध्यम से प्रवाह इष्टतम है और केवल तभी जब इसमें कोई संवर्धन पथ नहीं है।

मुझे समझ में नहीं आता कि augmenting paths क्या है। मैं googled है, और पाया:

• Augmenting Path in Wolfram

• Flow network in Wiki

लेकिन वे उपर्युक्त उद्धरण के सभी संदर्भ।

क्या कोई वास्तव में स्पष्ट रूप से स्पष्ट कर सकता है कि augmenting path क्या है?

Answer 1

एक संवर्धन पथ एक साधारण पथ है - एक पथ जिसमें चक्र नहीं होते - ग्राफ़ के माध्यम से केवल स्रोत से सिंक तक सकारात्मक क्षमता वाले किनारों का उपयोग करते हुए।

तो ऊपर दिया गया बयान किसी भी तरह से स्पष्ट है - अगर आपको स्रोत से सिंक तक कोई रास्ता नहीं मिल रहा है जो केवल सकारात्मक क्षमता किनारों का उपयोग करता है, तो प्रवाह में वृद्धि नहीं की जा सकती है।

जिस तरह से उस कथन का सबूत इतना आसान नहीं है।

Answer 2

बढ़ाना साधन बढ़ाने-बनाना बड़ा। दिए गए प्रवाह नेटवर्क G=(V,E) और प्रवाह f एक बढ़ते पथ p अवशिष्ट नेटवर्क Gf में source s से sink t तक एक साधारण पथ है। residual network की परिभाषा के अनुसार, हम बाधा, (u,v) और (v,u) की जो भी पर मूल प्रवाह नेटवर्क G में है उल्लंघन करने के बिना क्षमता Cf(u,v) तक एक बढ़ाने पथ की बढ़त (u,v) पर प्रवाह में वृद्धि हो सकती है। इसके अलावा अधिकतम राशि है जिसके द्वारा हम एक संवर्धित पथ पी में प्रत्येक किनारे पर प्रवाह में वृद्धि कर सकते हैं residual capacity of p कहा जाता है। सबूत थॉमस ज द्वारा एल्गोरिदम के परिचय में पाया जा सकता है। कॉर्मन इत्यादि ...

Answer 3

और आप स्रोत से सिंक तक बढ़ते पथ को कैसे ढूंढते हैं? बीएफएस के संशोधित संस्करण का उपयोग करना। आप स्रोत से BFS करते जब तक तुम सिंक तक पहुँचने और आप एक बढ़त केवल अगर यह अवशिष्ट क्षमता है पार (अर्थात कि धार के लिए, अपनी अधिकतम क्षमता - वर्तमान प्रवाह> 0)। और स्रोत डूबने से इस मार्ग के लिए, आप कम से कम अवशिष्ट क्षमता है, जो अधिकतम प्रवाह आपको लगता है कि पथ के माध्यम से पारित कर सकते हैं बनाए रखें।

bool maxFlowAchieved = false; 
int maxFlow = 0; // keeps track of what is the max flow in the network 
while(!maxFlowAchieved) 
{ 
    //BFS returns collection of Edges in the traversal order from source to sink 
    std::vector<Edge*> path = BFS(source, sink); 
    maxFlowAchieved = path.size() == 0; // all paths exhausted 
    if(maxFlowAchieved) 
     break; 
    // traverse each edge in the path and find minimum residual capacity 
    // edge->residual = edge->maxCapacity - edge->currentflow 
    int allowedFlow = GetMinResidualOnPath(path); 
    // Now add additional flow to each edge in the path. 
    // i.e. for each edge in path, edge->currentflow += allowedFlow 
    // clearly, edge->currentflow + allowedFlow <= edge->maxCapacity 
    SaturatePath(path, allowedFlow); 
    maxFlow += allowedFlow; 
} 

return maxFlow; 

Answer 4

स्रोत से प्रवाह खोजने iteratively डूबने की प्रक्रिया: उच्च स्तर कोड स्निपेट विचार प्राप्त करने के। जैसे के लिए, फोर्ड-Fulkerson एल्गोरिथ्म के मामले में, शुरू में सभी सभी किनारों पर प्रवाह शून्य कर रहे हैं। पुनरावृत्ति पर हम प्रत्येक मार्ग/किनारे के लिए मूल्य लेते हैं जो हमें आगे बढ़ने वाले पथों को खोजने के लिए प्रेरित करते हैं।