大網(wǎng)絡(luò)流最小費用流模型.ppt

1,最大網(wǎng)絡(luò)流,1 基本概念和術(shù)語 （1） 網(wǎng)絡(luò) G是一個簡單有向圖，G=(V,E)，V=1，2，n。 在V中指定一個頂點s，稱為源, 另一個頂點t，稱為匯。 有向圖G的每一條邊(v,w)E，對應(yīng)有一個值cap(v,w)0，稱為邊的容量。 這樣的有向圖G稱作一個網(wǎng)絡(luò)。 （2） 網(wǎng)絡(luò)流 網(wǎng)絡(luò)上的流是定義在網(wǎng)絡(luò)的邊集合E上的一個非負函數(shù)flow=flow(v,w)，并稱flow(v,w)為邊(v,w)上的流量。,2,（3） 可行流 滿足下述條件的流flow稱為可行流： (3.1)容量約束：對每一條邊(v,w)E，0flow(v,w)cap(v,w)。 (3.2)平衡約束： 對于中間頂點：流出量=流入量。 即對每個vV(vs,t)有：頂點v的流出量頂點v的流入量=0，即 對于源s：s的流出量s的流入量=源的凈輸出量f，即 對于匯t：t的流入量t的流出量的=匯的凈輸入量f，即 式中f 稱為這個可行流的流量，即源的凈輸出量(或匯的凈輸入量)。 可行流總是存在的。 例如，讓所有邊的流量flow(v,w)=0，就得到一個其流量f=0的可行流(稱為0流)。,3,（4） 邊流 對于網(wǎng)絡(luò)G的一個給定的可行流flow，將網(wǎng)絡(luò)中滿足flow(v,w)=cap(v,w)的邊稱為飽和邊；flow(v,w)0的邊稱為非零流邊。當邊(v,w)既不是一條零流邊也不是一條飽和邊時，稱為弱流邊。 （5） 最大流 最大流問題即求網(wǎng)絡(luò)G的一個可行流flow，使其流量f達到最大。即flow滿足： 0flow(v,w)cap(v,w)，(v,w)E；且 （6） 流的費用 在實際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問題，不僅涉及流量，而且還有費用的因素。此時網(wǎng)絡(luò)的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個單位流量費用cost(v,w)。對于網(wǎng)絡(luò)中一個給定的流flow，其費用定義為：,4,（7） 殘流網(wǎng)絡(luò) 對于給定的一個流網(wǎng)絡(luò)G及其上的一個流flow，網(wǎng)絡(luò)G關(guān)于流flow的殘流網(wǎng)絡(luò)G*與G有相同的頂點集V，而網(wǎng)絡(luò)G中的每一條邊對應(yīng)于G*中的1條邊或2條邊。 設(shè)(v,w)是G的一條邊。 當flow(v,w)0時，（w,v）是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)； 當flow(v,w)cap(v,w)時，(v,w)是G*中的一條邊，該邊的容量為 cap*(v,w)=cap(v,w)-flow(v,w)。 按照殘流網(wǎng)絡(luò)的定義，當原網(wǎng)絡(luò)G中的邊(v,w)是一條零流邊時，殘流網(wǎng)絡(luò)G*中有唯一的一條邊(v,w)與之對應(yīng)，且該邊的容量為cap(v,w)。 當原網(wǎng)絡(luò)G中的邊(v,w)是一條飽和邊時，殘流網(wǎng)絡(luò)G*中有唯一的一條邊(w,v)與之對應(yīng)，且該邊的容量為cap(v,w)。 當原網(wǎng)絡(luò)G中的邊(v,w)是一條弱流邊時，殘流網(wǎng)絡(luò)G*中有2條邊(v,w)和(w,v)與之對應(yīng)，這2條邊的容量分別為cap(v,w) -flow(v,w)和flow(v,w)。 殘流網(wǎng)絡(luò)是設(shè)計與網(wǎng)絡(luò)流有關(guān)算法的重要工具。,5,增廣路算法,1 算法基本思想 設(shè)P是網(wǎng)絡(luò)G中聯(lián)結(jié)源s和匯t的一條路。定義路的方向是從s到t。 將路P上的邊分成2類： 一類邊的方向與路的方向一致，稱為向前邊。向前邊的全體記為P+。 另一類邊的方向與路的方向相反，稱為向后邊。向后邊的全體記為P-。 設(shè)flow是一個可行流，P是從s到t的一條路，若P滿足下列條件： （1）在P的所有向前邊(v,w)上，flow(v,w)0，即P-中的每一條邊都是非零流邊。 則稱P為關(guān)于可行流flow的一條可增廣路。 可增廣路是殘流網(wǎng)絡(luò)中一條容量大于0的路。 將具有上述特征的路P稱為可增廣路是因為可以通過修正路P上所有邊流量flow(v,w)將當前可行流改進成一個流值更大的可行流。,6,增流的具體做法是： （1）不屬于可增廣路P的邊(v,w)上的流量保持不變； （2）可增廣路P上的所有邊(v,w)上的流量按下述規(guī)則變化： 在向前邊(v,w)上，flow(v,w)+d； 在向后邊(v,w)上，flow(v,w)-d。 按下面的公式修改當前的流。 其中d稱為可增廣量，可按下述原則確定：d取得盡量大，又要使變化后的流仍為可行流。 按照這個原則，d既不能超過每條向前邊(v,w)的cap(v,w)-flow(v,w)，也不能超過每條向后邊(v,w)的flow(v,w)。 因此d應(yīng)該等于向前邊上的cap(v,w)-flow(v,w)與向后邊上的flow(v,w)的最小值。也就是殘流網(wǎng)絡(luò)中P的最大容量。 增廣路定理：設(shè)flow是網(wǎng)絡(luò)G的一個可行流，如果不存在從s到t關(guān)于flow的可增廣路P，則flow是G的一個最大流。,7,2 算法描述 最大流的增廣路算法如下。該算法也常稱作Ford Fulkerson算法。,template class MAXFLOW const Graph ,8,3 算法的計算復(fù)雜性 增廣路算法的效率由下面2個因素所確定。 （1）整個算法找增廣路的次數(shù)； （2）每次找增廣路所需的時間。 給定的網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M。 可以證明，在一般情況下，增廣路算法中找增廣路的次數(shù)不超過nM次。 最短增廣路算法在最壞情況下找增廣路的次數(shù)不超過nm/2次。 找1次增廣路最多需要O(m)計算時間。 因此，在最壞情況下最短增廣路算法所需的計算時間為O(nm2) 。 當給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)，即m=O(n)時，最短增廣路算法所需的計算時間為O(n3)。 最大容量增廣路算法在最壞情況下找增廣路的次數(shù)不超過2mlogM次。 由于使用堆來存儲優(yōu)先隊列，找1次增廣路最多需要O(nlogn)計算時間。 因此，在最壞情況下最大容量增廣路算法所需的計算時間為 當給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)時，最大容量增廣路算法所需的計算時間為,9,預(yù)流推進算法,1 算法基本思想 增廣路算法的特點是找到增廣路后，立即沿增廣路對網(wǎng)絡(luò)流進行增廣。 每一次增廣可能需要對最多n-1條邊進行操作。 最壞情況下，每一次增廣需要O(n)計算時間。 有些情況下，這個代價是很高的。下面是一個極端的例子。,10,無論用哪種增廣路算法，都會找到10條增廣路，每條路長為10，容量為1。 共需要10次增廣，每次增廣需要對10條邊進行操作，每條邊增廣1個單位流量。 10條增廣路中的前9個頂點（前8條邊）是完全一樣的。 如果直接將前8條邊的流量增廣10個單位，而只對后面長為2的不同的有向路單獨操作，就可以節(jié)省許多計算時間。 這就是預(yù)流推進（preflow push )算法的基本思想。 預(yù)流推進算法注重對每一條邊的增流，而不必每次一定對一條增廣路增流。 通常將沿一條邊增流的運算稱為一次推進（push）。 在算法的推進過程中，網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量平衡約束。 從每個頂點（除s和t外）流出的流量之和總是小于等于流入該頂點的流量之和。 這種流稱為預(yù)流（preflow）。這也是這類算法被稱為預(yù)流推進算法的原因。 下面先給出預(yù)流的嚴格定義。 給定網(wǎng)絡(luò)G=(V,E)一個預(yù)流是定義在G的邊集E上的一個正邊流函數(shù)。 該函數(shù)滿足容量約束，即對G的每一條邊(v,w)E，滿足0flow(v,w)cap(v,w)。,11,G的每一中間頂點滿足流出量小于或等于流入量。 即對每個vV(vs,t)有 滿足條件 的中間頂點v稱為活頂點。 量 稱為頂點v的存流。 按此定義，源s和匯t不可能成為活頂點。 對網(wǎng)絡(luò)G上的一個預(yù)流，如果存在活頂點，則說明該預(yù)流不是可行流。 預(yù)流推進算法就是要選擇活頂點，并通過把一定的流量推進到它的鄰點，盡可能地將當前活頂點處正的存流減少為0，直至網(wǎng)絡(luò)中不再有活頂點，從而使預(yù)流成為可行流。 如果當前活頂點有多個鄰點，那么首先推進到哪個鄰點呢? 由于算法最后的目的是盡可能將流推進到匯點t，因此算法應(yīng)尋求把流量推進到它的鄰點中距頂點t最近的頂點。 預(yù)流推進算法中用到一個高度函數(shù)h來確定推流邊。 對于給定網(wǎng)絡(luò)G=(V,E)的一個流，其高度函數(shù)h是定義在G的頂點集V上的一個非負函數(shù)。該函數(shù)滿足： （1）對于G的殘流網(wǎng)絡(luò)中的每一條邊(u,v)有，h(u) h(v)+1； （2）h(t)=0。 G的殘流網(wǎng)絡(luò)中滿足h(u) = h(v)+1的邊(u,v)稱為G的可推流邊。,12,一般的預(yù)流推進算法,一般的預(yù)流推進算法的每次迭代是一次推進運算或者一次高度重新標號運算。 如果推進的流量等于推流邊上的殘留容量，則稱為飽和推進，否則稱為非飽和推進。 算法終止時，網(wǎng)絡(luò)中不含有活頂點。此時只有頂點s和t的存流非零。此時的預(yù)流實際上已經(jīng)是一個可行流。 算法預(yù)處理階段已經(jīng)令h(s)=n，而高度函數(shù)在計算過程中不會減少，因此算法在計算過程中可以保證網(wǎng)絡(luò)中不存在增廣路。 根據(jù)增廣路定理，算法終止時的可行流是一個最大流。,步驟0：構(gòu)造初始預(yù)流flow： 對源頂點s的每條出邊(s,v)令flow(s,v)=cap(s,v)； 對其余邊(u,v)令flow(u,v)=0。構(gòu)造一有效的高度函數(shù)h。 步驟1：如果殘量網(wǎng)絡(luò)中不存在活頂點，則計算結(jié)束，已經(jīng)得到最大流； 否則轉(zhuǎn)步驟2。 步驟2：在網(wǎng)絡(luò)中選取活頂點v。 如果存在頂點v的出邊為可推流邊，則選取一條這樣的可推流邊，并沿此邊推流。 否則令h(v) = minh(w)+1 | (v,w)是當前殘流網(wǎng)絡(luò)中的邊，并轉(zhuǎn)步驟1。,13,一般的預(yù)流推進算法并未給出如何選擇活頂點和可推流邊。 不同的選擇策略導(dǎo)致不同的預(yù)流推進算法。 在基于頂點的預(yù)流推進算法中，選定一個活頂點后，算法沿該活頂點的所有推流邊進行推流運算，直至無可推流邊或該頂點的存變成0時為止。 3 算法的計算復(fù)雜性 基于頂點的預(yù)流推進算法用一個廣義隊列g(shù)Q存儲當前活頂點集合。 廣義隊列可以是通常的FIFO隊列，LIFO棧，隨機化隊列，隨機化棧，或按各種優(yōu)先級定義的優(yōu)先隊列。 算法的效率與廣義優(yōu)先隊列的選擇密切相關(guān)。 如果選用通常的FIFO隊列，則在最壞情況下，預(yù)流推進算法求最大流所需的計算時間為O(mn2)，其中m和n分別為圖G的邊數(shù)和頂點數(shù)。 如果以頂點高度值為優(yōu)先級，選用優(yōu)先隊列實現(xiàn)預(yù)流推進算法，則在最壞情況下，求最大流所需的計算時間為 這個算法也稱為最高頂點標號預(yù)流推進算法。 近來已提出許多其它預(yù)流推進算法的實現(xiàn)策略，在最壞情況下算法所需的計算時間已接近O(mn)。,14,最小費用流問題,1 網(wǎng)絡(luò)流的費用 在實際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問題，不僅涉及流量，而且還有費用的因素。 網(wǎng)絡(luò)的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個單位流量費用cost(v,w)。對于網(wǎng)絡(luò)中一個給定的流flow，其費用定義為： 2 最小費用流問題 給定網(wǎng)絡(luò)G，要求G的一個最大用流flow，使流的總費用最小。 3 最小費用可行流問題 給定多源多匯網(wǎng)絡(luò)G，要求G的一個可行流flow，使可行流的總費用最小。 可行流問題等價于最大流問題。最小費用可行流問題也等價于最小費用流問題。,15,消圈算法,1 算法基本思想 最小費用流問題有關(guān)的算法中，仍然沿用殘流網(wǎng)絡(luò)的概念。 此時，殘流網(wǎng)絡(luò)中邊的費用定義為： int costRto(int v) return from(v) ? -pcost : pcost; 當殘流網(wǎng)絡(luò)中的邊是向前邊時，其費用不變。 當殘流網(wǎng)絡(luò)中的邊是向后邊時，其費用為原費用的負值。 由于殘流網(wǎng)絡(luò)中存在負費用邊，因此殘流網(wǎng)絡(luò)中就不可避免地會產(chǎn)生負費用圈。 在與最小費用流問題有關(guān)的算法中，負費用圈是一個重要概念。 最小費用流問題的最優(yōu)性條件 網(wǎng)絡(luò)G的最大流flow是G的一個最小費用流的充分且必要條件是flow所相應(yīng)的殘流網(wǎng)絡(luò)中沒有負費用圈。,16,最小費用流的消圈算法,步驟0：用最大流算法構(gòu)造最大流flow。 步驟1：如果殘量網(wǎng)絡(luò)中不存在負費用圈，則計算結(jié)束，已經(jīng)找到最小費用流； 否則轉(zhuǎn)步驟2。 步驟2：沿找到的負費用圈增流，并轉(zhuǎn)步驟1。,17,3 算法的計算復(fù)雜性 給定網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M，每條邊的費用不超過C。 最大流的費用不超過mCM，而每次消去負費用圈至少使得費用下降1個單位，因此最多執(zhí)行mCM次找負費用圈和增流運算。 用Bellman-Ford算法找1次負費用圈需要O(mn)計算時間。 最小費用流的消圈算法在最壞情況下需要計算時間,18,最小費用路算法,1 算法基本思想 消圈算法首先找到網(wǎng)絡(luò)中的一個最大流，然后通過消去負費用圈使費用降低。 最小費用路算法不用先找最大流，而是用類似于求最大流的增廣路算法的思想，不斷在殘流網(wǎng)絡(luò)中尋找從源s到匯t的最小費用路，然后沿最小費用路增流，直至找到最小費用流。 殘流網(wǎng)絡(luò)中從源s到匯t的最小費用路是殘流網(wǎng)絡(luò)中從s到t的以費用為權(quán)的最短路。 殘流網(wǎng)絡(luò)中邊的費用定義為： 當殘流網(wǎng)絡(luò)中邊(v,w)是向前邊時，其費用為cost(v,w)； 當(v,w)是向后邊時，其費用為-cost(w,v)。,19,最小費用流的最小費用路算法 步驟0：初始可行0流。 步驟1：如果不存在最小費用路，則計算結(jié)束，已經(jīng)找到最小費用流； 否則用最短路算法在殘流網(wǎng)絡(luò)中找從s到t的最小費用可增廣路，轉(zhuǎn)步驟2。 步驟2：沿找到的最小費用可增廣路增流，并轉(zhuǎn)步驟1。,20,3 算法的計算復(fù)雜性 算法的主要計算量在于連續(xù)尋找最小費用路并增流。 給定網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M，每條邊的費用不超過C。 每次增流至少使得流值增加1個單位，因此最多執(zhí)行M次找最小費用路算法。 如果找1次最小費用路需要s(m,n,C)計算時間，則求最小費用流的最小費用路算法需要O(Ms(m,n,C)計算時間。,21,網(wǎng)絡(luò)單純形算法,1 算法基本思想 消圈算法的計算復(fù)雜度不僅與算法找到的負費用圈有關(guān)，而且與每次找負費用圈所需的時間有關(guān)。 網(wǎng)絡(luò)單純形算法是從解線性規(guī)劃問題的單純形算法演變而來，但從算法的運行機制來看，可以將網(wǎng)絡(luò)單純形算法看作另一類消圈算法。 其基本思想是用一個可行支撐樹結(jié)構(gòu)來加速找負費用圈的過程。 對于給定的網(wǎng)絡(luò)G和一個可行流，相應(yīng)的可行支撐樹定義為G的一棵包含所有弱流邊的支撐樹。 網(wǎng)絡(luò)單純形算法的第一步是構(gòu)造可行支撐樹。 從一個可行流出發(fā)，不斷找由弱流邊組成的圈，然后沿找到的弱流圈增流，消除所有弱流圈。 在剩下的所有弱流邊中加入零流邊或飽和邊構(gòu)成一棵可行支撐樹。 在可行支撐樹結(jié)構(gòu)的基礎(chǔ)上，網(wǎng)絡(luò)單純形算法通過頂點的勢函數(shù)，巧妙地選擇非樹邊，使它與可行支撐樹中的邊構(gòu)成負費用圈。然后，沿找到的負費用圈增流。,22,定義了頂點的勢函數(shù)后，殘流網(wǎng)絡(luò)中各邊(v,w)的勢費用定義為： c*(v,w)=c(v,w)-(v)- (w)。 其中，c(v,w)是(v,w)在殘流網(wǎng)絡(luò)中的費用。 如果對可行支撐樹中所有邊（v,w）有c*(v,w)=0，則相應(yīng)的勢函數(shù)是一個有效勢函數(shù)。 對于一棵可行支撐樹，如果將一條非樹邊加入可行支撐樹，產(chǎn)生殘流網(wǎng)絡(luò)中的一個負費用圈，則稱該非樹邊為一條可用邊。 可用邊定理：給定一棵可行支撐樹及其上的一個有效勢函數(shù)，非樹邊e是一條可用邊的充分必要條件是，e是一條有正勢費用的飽和邊，或e是一條有負勢費用的零流邊。 事實上，設(shè)e=(v,w)。 邊e與樹邊t1,t2,td構(gòu)成一個圈cy