Ⅰ 運籌學中的圖論問題
很多實際的生產問題都能被抽象成一張大的圖。具體一點的例子，比如需要在若干個城市之間鋪設鐵路或者架設電網，那麼城市就是圖裡面的點，鐵路電網就是圖裡面的邊。抽象一點的例子，比如完成一個項目的過程中所有可能出現的狀態都可以視為一個點，而狀態到狀態之間的轉換就是邊。上一篇文章中我們說過運籌學是處理實際生產生活中遇到的問題的。一旦實際問題被抽象成了一個圖的模型（注意與機器學習裡面的圖模型區分開來），很多圖論裡面的演算法就可以用來解決實際問題，所以圖論是運籌學當中的一個很大的分支。今天我們就介紹一下幾個圖論的基本演算法及其在生產生活中的應用。
一最小生成樹
比如現在要在若干個村子之間架設電網，保證每個城市都通上電（先不考慮電網輸電能力大小）。雖然理論上講，任何兩個村子之間都可以架設電線，不過那樣的話成本很到，不劃算，我們需要在所有可能的連線裡面找到一組總長最短的邊，保證這些邊把每個村子都連上了。在圖論中，這是一個典型的最小生成樹問題。有兩種解決最小生成樹的方法，第一種辦法是把所有的邊按照從小到大的順序添加到圖裡面，如果產生迴路就舍棄它，直到覆蓋了所有的點。另一種方法是把圖上的邊按照從大到小的順序刪除，直到再刪下去就一定會產生離散的點為止。
二最短路徑
圖論中應用最廣的問題可能就是最短路徑問題了。地圖上很多城市之間都有道路相連，想從一個城市到另一個城市，往往有多種選擇，可是走那條路距離最短呢？如果地圖規模不大，我們可以一眼就看出來。可是隨著地圖規模變大，就很難再一眼看出來了，需要有嚴格的演算法保證找到最短路徑。目前已經有了很多種最短路徑演算法，他們的基本思想也不盡相同。以著名的Dijkstra演算法為例，它每次會選擇距離「所有已經選擇過了的點」中距離最近的下一個點，一步步的迭代下去。這個流程保證了演算法會按照距離出發點由近到遠的順序選擇每一個點。
三最大流-最小割問題
油氣輸送網路又許多不同的邊組成，每一條邊的運輸能力有限。輸送油氣資源的時候，為了最大化運輸量，需要合理安排通過每一條邊的油氣流量。這就是在一個網路尋找最大流的問題（等價於尋找最小割）。解決問題的想法很簡單，找到一組邊，它們把整個網路分成了兩部分，流的源和目的地址分屬於這兩個部分。我們稱這樣一組邊為圖的一個分割。由於所有的油氣流都要通過分割中的邊，所以最大流其實受制於分割的流通能力的。於是最大流應該等於流通能力最小的分割。剩下的問題，就是一步步調整，找到最小分割了。
Ⅱ 最小割集等於最大流
最大流是一種運輸方案，割集是分割網路發點與收點的一組弧集合，割集中包含的是一組弧，而這些弧的發點跟收點分別在兩個點集，最小割集只是最大流的一部分，因而不對吧
Ⅲ 網路流的資料
編輯本段定義
圖論中的一種理論與方法，研究網路上的一類最優化問題 。1955年 ，T.E. 哈里斯在研究鐵路最大通量時首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R. 福特和 D.R. 富爾克森等人給出了解決這類問題的演算法，從而建立了網路流理論。所謂網路或容量網路指的是一個連通的賦權有向圖 D＝ （V、E、C） ， 其中V 是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網路上的流就是由起點流向終點的可行流，這是定義在網路上的非負函數，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問 ：若從起點v1將物資運送到終點v6去 ，應選擇那條路線才能使總運輸距離最短�這樣一類問題稱為最短路問題 。 如果把上圖看作一個輸油管道網 ， v1 表示發送點，v6表示接收點，其他點表示中轉站 ，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大。這樣的問題稱為最大流問題。
最大流理論是由福特和富爾克森於 1956 年創立的 ，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善 。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯系，開辟了圖論應用的新途徑。
目前網路流的理論和應用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
網路流演算法
一、網路流的基本概念
先來看一個實例。
現在想將一些物資從S運抵T，必須經過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。如下圖：
每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？
這是一個典型的網路流模型。為了解答此題，我們先了解網路流的有關定義和概念。
若有向圖G=(V,E)滿足下列條件：
1、 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發點。
2、 有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。
3、 每一條弧都有非負數，叫做該邊的容量。邊(vi, vj)的容量用cij表示。
則稱之為網路流圖，記為G = (V, E, C)
譬如圖5-1就是一個網路流圖。
1．可行流
對於網路流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足下列三條件時稱為這網路的可行流，用f表示它。
1、 每一條弧(i,j)有fij≤cij。
2、 除源點S和匯點T以外的所有的點vi，恆有：
該等式說明中間點vi的流量守恆，輸入與輸出量相等。
3、 對於源點S和匯點T有：
這里V(f)表示該可行流f的流量。
例如對圖5-1而言，它的一個可行流如下：
流量V(f) = 5。
2．可改進路
給定一個可行流f=。若fij = cij，稱<vi, vj>為飽和弧；否則稱<vi, vj>為非飽和弧。若fij = 0，稱<vi, vj>為零流弧；否則稱<vi, vj>為非零流弧。
定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。
譬如在圖5-1中，P = (S, V1, V2, V3, V4, T)，那麼
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
給定一個可行流f，P是從S到T的一條道路，如果滿足：
那麼就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作「可改進」，是因為可改進路上弧的流量通過一定的規則修改，可以令整個流量放大。具體方法下一節會重點介紹，此不贅述。
3．割切
要解決網路最大流問題，必須先學習割切的概念和有關知識。
G = (V, E, C)是已知的網路流圖，設U是V的一個子集，W = V\U，滿足S U，T W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。
對於弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：
例如圖5-1中，令U = {S, V1}，則W = {V2, V3, V4, T}，那麼
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：對於已知的網路流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。
通俗簡明的講：「最大流小於等於最小割」。這是「流理論」里最基礎最重要的定理。整個「流」的理論系統都是在這個定理上建立起來的，必須特別重視。
下面我們給出證明。
網路流、可改進路、割切都是基礎的概念，應該扎實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯系是十分緊密的。
二、求最大流
何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：
下面探討如何求得最大流。
在定義「可改進路」概念時，提到可以通過一定規則修改「可改進路」上弧的流量，可以使得總流量放大。下面我們就具體看一看是什麼「規則」。
對可改進路P上的弧<vi, vj>，分為兩種情況討論：
第一種情況：<vi, vj>∈P+，可以令fij增加一個常數delta。必須滿足fij + delta ≤ cij，即delta ≤ cij – fij。
第二種情況：<vi, vj>∈P-，可以令fij減少一個常數delta。必須滿足fij - delta ≥ 0，即delta ≤ fij
根據以上分析可以得出delta的計算公式：
因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta > 0。
容易證明，按照如此規則修正流量，既可以使所有中間點都滿足「流量守恆」（即輸入量等於輸出量），又可以使得總的流量有所增加（因為delta > 0）。
因此我們對於任意的可行流f，只要在f中能找到可改進路，那麼必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？
答案是肯定的。下面我們給出證明。
定理1 可行流f是最大流的充分必要條件是：f中不存在可改進路。
證明：
首先證明必要性：已知最大流f，求證f中不存在可改進路。
若最大流f中存在可改進路P，那麼可以根據一定規則（詳見上文）修改P中弧的流量。可以將f的流量放大，這與f是最大流矛盾。故必要性得證。
再證明充分性：已知流f，並且f中不存在可改進路，求證f是最大流。
我們定義頂點集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，則y∈U;
若x∈U，且fyx>0，則y∈U。
（這實際上就是可改進路的構造規則）
（c） W = V \ U。
由於f中不存在可改進路，所以T∈W；又S∈U，所以U、W是一個割切（U, W）。
按照U的定義，若x∈U，y∈W，則fxy = cxy。若x∈W，y∈U，則fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得證。
根據充分性證明中的有關結論，我們可以得到另外一條重要定理：
最大流最小割定理：最大流等於最小割，即max V(f) = min C(U, W)。
至此，我們可以輕松設計出求最大流的演算法：
step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。
step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。
step 3. 根據P求delta。
step 4. 以delta為改進量，更新可行流f。轉step 2。
step 5. 演算法結束。此時的f即為最大流。
三、最小費用最大流
1．問題的模型
流最重要的應用是盡可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的餘地，費用的因素就自然參與到決策中來。
圖5-8是一個最簡單的例子：弧上標的兩個數字第一個是容量，第二個是費用。這里的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。
容易看出，此圖的最大流（流量是8）為：fs1 = f1t = 5, fs2 = f2t = 3。所以它的費用是：3*5+4*5+7*3+2*3 = 62。
一般的，設有帶費用的網路流圖G = (V, E, C, W)，每條弧<Vi, Vj>對應兩個非負整數Cij、Wij，表示該弧的容量和費用。若流f滿足：
(a) 流量V(f)最大。
(b) 滿足a的前提下，流的費用Cost(f) = 最小。
就稱f是網路流圖G的最小費用最大流。
2．演算法設計
我們模仿求最大流的演算法，找可改進路來求最小費用最大流。
設P是流f的可改進路，定義 為P的費用（為什麼如此定義？）。如果P是關於f的可改進路中費用最小的，就稱P是f的最小費用可改進路。
求最小費用最大流的基本思想是貪心法。即：對於流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。
演算法可描述為：
step 1. 令f為零流。
step 2. 若無可改進路，轉step 5；否則找到最小費用可改進路，設為P。
step 3. 根據P求delta（改進量）。
step 4. 放大f。轉step 2。
step 5. 演算法結束。此時的f即最小費用最大流。
至於演算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。
2．最小費用可改進路的求解
求「最小費用可改進路」是求最小費用最大流演算法的關鍵之所在，下面我們探討求解的方法。
設帶費用的網路流圖G = (V, E, C, W)，它的一個可行流是f。我們構造帶權有向圖B = (V』, E』)，其中：
1、 V』 = V。
2、 若<Vi, Vj>∈E，fij<Cij，那麼<Vi, Vj>∈E』，權為Wij。
若<Vi, Vj>∈E，fij>0，那麼<Vj, Vi>∈E』，權為-Wij。
顯然，B中從S到T的每一條道路都對應關於f的一條可改進路；反之，關於f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關系。
故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。
現在的問題變成：給定帶權有向圖B = (V』, E』)，求從S到T的一條最短路徑。
考慮到圖中存在權值為負數的弧，不能採用Dijkstra演算法；Floyd演算法的效率又不盡如人意——所以，這里採用一種折衷的演算法：迭代法。
設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那麼迭代演算法描述如下：（為了便於描述，令n = |V』|，S的編號為0，T的編號為n+1）
step 1. 令Short[k] +∞（1≤k≤n+1），Short[0] 0。
step 2. 遍歷每一條弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，則令Short[j] Short[k] + <k, j>，同時Last[j] k。倘不存在任何一條弧滿足此條件則轉step 4。
step 3. 轉step 2.
step 4. 演算法結束。若Short[n + 1]= +∞，則不存在從S到T的路徑；否則可以根據Last記錄的有關信息得到最短路徑。
一次迭代演算法的時間復雜度為O(kn2)，其中k是一個不大於n的變數。在費用流的求解過程中，k大部分情況下都遠小於n。
3．思維發散與探索
1）可改進路費用：「遞增！遞增？」
設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那麼會不會有p1≤p2≤p3≤……≤pk呢？
2）迭代法：「小心死循環！嘿嘿……」
迭代法會出現死循環嗎？也就是說，構造的帶權有向圖B中會存在負迴路嗎？
3）費用：「你在乎我是負數嗎？」
網路流圖中的費用可以小於零嗎？
4）容量：「我管的可不僅是弧。」
網路流圖中的「容量」都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？
四、有上下界的最大流
上面討論的網路流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧<Vi, Vj>加上一個下界限制Aij（即必須滿足Aij≤fij）。
例如圖5-9：
弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具體方案見圖5-10(b)。
那麼有上下界的網路最大流怎麼求呢？
一種自然的想法是去掉下界，將其轉化為只含上界的網路流圖。這種美好的願望是可以實現的。具體方法如下：
設原網路流圖為G = (V, E, C, A)，構造不含下界的網路流圖G』 = (V』, E』, C』)：
1、 V』 = V∪{S』, T』}
2、 對每個頂點x，令 ，若h-(x)≠0，就添加一條弧<S』, x>，其上界為h-(x)。
3、 對每個頂點x，令 ，若h+(x)≠0，就添加一條弧<x, T』>，其上界為h+(x)。
4、 對於任何<Vi, Vj>∈E，都有<Vi, Vj>∈E』，其上界C』ij = Cij – Aij。
5、 新增<T, S>∈E』，其上界CTS = +∞。
在G』中以S』為源點、T』為匯點求得最大流f』。若f』中從S』發出的任意一條弧是非飽和弧，則原網路流圖沒有可行流。否則可得原圖的一個可行流f = f』 + A，即所有的fij = f』ij + Aij。（其正確性很容易證明，留給讀者完成）
然後再求可改進路（反向弧<Vi, Vj>必須滿足fij≥Aij，而非fij≥0），不斷放大f，直到求出最大流。
我們看到，上幾節所討論的一種可行網路流實際上是{Aij = 0}的一種特殊網路流，這里提出的模型更一般化了。解決一般化的復雜問題，我們採取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解決。這是一種重要的基本思想：化歸——簡單有效。基於這種思想，請讀者自行思考解決：
1、 有上下界的最小流。
2、 有上下界的最小費用最大流。
五、多源點、多匯點的最大流
已知網路流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。
它的解決很簡單：
1、 增設一個「超級源」S』，對每個源點Si，新增弧<S』, Si>，容量為無窮大。
2、 增設一個「超級匯」T』，對每個匯點Ti，新增弧<Ti, T』>，容量為無窮大。
3、 以S』為源點、T』為匯點求最大流f。
4、 將f中的S』和T』去掉，即為原圖的最大流。
演算法正確性顯然。
六、頂點有容量限制的最大流
上一節已經提出了這個問題，即對於進出每個頂點的流量也規定一個上限，這樣的最大流如何求？
既然我們已經解決了「邊限制」問題，現在何不把「點限制」問題轉化為「邊限制」呢？具體辦法如下：
1、 對除源點和匯點之外的每個頂點i拆分成兩個頂點i』和i』』。新增一條弧<i』, i』』>，其容量為點i的流量限制。
2、 對於原圖中的弧<i, j>，我們將其變換成<i』』, j』>。
3、 對變換後的圖求最大流即可。
這里我們又一次運用到了化歸的思想：將未知的「點限制」問題轉化為已知的「邊限制」問題。
七、網路流與二部圖的匹配
{二部圖和匹配的定義可參見本書專門介紹二部圖匹配的章節}
設二部圖為G = (X, Y, E)。
增設點S』，對於所有i∈X，新增弧<S』, Xi>，容量為1；增設點T』，對於所有i∈Y，新增一條弧<Yi, T』>，容量也為1。原圖中所有的弧予以保留，容量均為+∞。對新構造出來的網路流圖以S』為源點、T』為匯點求最大流：流量即為最大匹配數；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一條匹配邊。
二部圖最大匹配問題解決。
那麼二部圖的最佳匹配問題又如何？
仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然後以S』為源點、T』為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。
復制的我快吐了~
Ⅳ 演算法基礎
謹以此文，感謝我在這個學校最喜歡的兩個老師之一——肖my老師。本文基本為老師上課說講授內容加上一部分自己的感悟拼湊而來，寫作文本的目的是為自己的演算法課程留下一點點東西，站在老師肩膀上形成粗糙的框架，方便以後的復習以及深入。文筆有限，其中包含的錯誤還請多多包容，不吝賜教。
to do list：
時間復雜度中遞歸樹法；動規，分治新的感悟；
點覆蓋：一組點的集合，使得圖中所有邊都至少與該集合中一個點相連。
支配集：一組點的集合，使得圖中所有的點要麼屬於該集合，要麼與該集合相連。
最大團：在一個無向圖中找出點數最多的完全圖。
獨立集：一組點的集合，集合中的頂點兩兩不相鄰。（團轉過來）
SAT問題：也稱布爾可滿足性問題。給一組變
其中Ci被稱為句子。
點覆蓋<->獨立集<->最大團
最小割：割是一組邊集。如s-t割就是如果去掉這些邊，將把原圖劃分為兩個點集，其中一個點集包含s，一個點集包含t。（兩個是指不相連，而不是代表不存在邊相連，如反向邊）
decision problem: 是否存在。
search problem:找到一個解。
（這個還能擴展，比如decision problem在多項式時間內解決，所以他是P問題嗎）
漸進符號：
注意以上三種都是緊的，對應的兩個小寫的符號是不緊的，即如下圖所示：
概念：演算法的時間復雜度是一個函數，用於定性描述演算法的運行時間。注意，這個一個代表演算法輸入字元串長度的函數。
[注]輸入字元串長度是一個比較關鍵的理解，比如在背包問題中，其時間復雜度為O(nW)，因為W不定，所以只能是一個偽多項式時間。
比較：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n
大致：常數<對數<冪函數<指數函數<階乘
對於指數是n相關的進行比較，優先比較指數，再比較底數。
記住一個特例：n (logn)<n!<n n
計算：
一般來說，計算採用主方法和遞歸樹法，其中遞歸樹技巧性比較強，主方法其實也是遞歸樹推導歸納而來，且主方法能得到一個比較緊的結果。
主方法：
f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )
P：decision problems有一個多項式演算法。
NP（nondeterministic polynomial-time）：decision problems能夠在多項式時間內驗證。
NPC：NP完全問題，首先這個問題是NP的，其次，其他所有問題都可以多項式時間內歸約到它。
NPH：如果所有NP問題都可以多項式時間歸約到某個問題，則稱該問題為NP困難。
因為NP困難問題未必可以在多項式時間內驗證一個解的正確性（即不一定是NP問題），因此即使NP完全問題有多項式時間的解（P=NP），NP困難問題依然可能沒有多項式時間的解。因此NP困難問題「至少與NP完全問題一樣難」。
一些NP問題能在多項式時間內解決，因為 P∈NP
NP難類型問題的證明：
先選好一個已知NP難的問題，然後將已知NP難問題多項式歸約到要證明的問題上。先給出這個歸約，然後再證明這個歸約的正確性。
NPC類型問題的證明：
證明一個問題Y是NPC問題，先說明Y是NP的，然後找到一個NPC問題X，將這個問題X歸約到問題Y上，即證明完成。
常見的NPC問題（重要，規約的時候有用！）：
packing problems: set-packing，獨立集
覆蓋問題：集合覆蓋問題，頂點覆蓋問題
嚴格滿足問題(constraint satisfaction problems)：SAT，3SAT
序列問題：哈密爾頓迴路，旅行商問題
劃分問題：3D-matching, 3著色問題
數字問題：子集合問題（子集元素之和為t），背包問題
其他：分團問題（是否存在一個規模為k的團）
規約的概念與理解
規約：意味著對問題進行轉換，例如將一個未知的問題轉換成我們能夠解決的問題，轉換的過程可能涉及到對問題的輸入輸出的轉換。
自歸約：search problem <=p decision problem
歸約：A歸約到B，也就是說，我們對A套一個函數f，在f函數的作用下形成一個新的問題，對這個問題運用B的黑盒解法，能夠解決問題A。
(B <=p A)一般說來，B問題如果可以歸約到A問題，也就是說，一個解決A問題的演算法可以被用做子函數（子程序）來解決B問題，也就是說，求解B問題不會比求解A問題更困難。因此，如果B問題是困難的，那麼A問題也就是困難的，因為不存在求解A問題的高效演算法。(最後一句不懂)
我簡單說一下我理解的規約，以X規約到Y為准，大概分成兩個方面：
註：在 三 的一些實例中細品。
概念：在對問題求解時，總是做出在當前看來是最好的選擇。
貪心的證明：先假設貪心演算法得到的解不是最優解，假設S1是貪心演算法得到的解，而S2是所有最優解中和S1具有最多相同元素的解，然後比較S1和S2，觀察S1和S2中第一個（最前面一個）不一樣的元素，然後在貪心解S2中將不一樣的元素換成S1中的那個元素得到另一個最優解S3，這樣S3和S1比S2和S1有更多相同元素，和假設S2是與S1有最多相同元素的最優解矛盾，這樣來推導S1是最優解。
我的理解：假設這個不是最優的，但是一定存在一個最優的解在某一個位置之前和我當前解結構是一樣的，那麼在這個位置，選最優解也可以選當前解，不影響最終答案。
[注]概念很簡單，但是實際操作的時候，貪心的角度很重要，同樣的貪心，方向對了，演算法就是對的。
例子：
給你一系列活動，每個活動有一個起始時間和一個結束時間，要求在活動不沖突的情況下找到一種有最多活動的安排。
對於這個問題，我們有一下幾種貪心的角度：
①將任務按照 開始時間 升序排列。
②將任務按照 結束時間 升序排列。
③將任務按照 任務時長 升序排列。
④對於每一個任務，都記錄與其他任務沖突的數量，按照 沖突數量 的升序排列。
其中1，3，4都是不可以的。
任務結束時間的貪心證明（反證法）：
假設貪心不是最最優的，那我們在最優解中找一個與當前解有最相似的解。
由圖可以知道，貪心貪的就是最早結束，所以如果不是最優，那麼最優的結束時間一定晚於貪心的結束時間。
由上圖就可以證明。
最大流通常與最小割相聯系。
f 為任意一個流，cap為容量，對於任意的s-t割出來的點集（A，B），v( f ) <= cap(A, B)。
當流增加到與割的容量相等時候，就不可能再有增長空間了，稱為最大流。
對於割的容量來說，不同的割法會有不同流量，有些割法永遠不會有流達到，比如部分A = {s}, B = {V - s}，這種把源點割出來的割法。
綜上，通過這種感性的認識，如果能找到一個最小的割，那麼這個割就一定是最大能跑到的流（如果流能更高的話在這個割上就會超過容量，反證。）
上圖為一條增廣路，一條增廣路即為一條s-t的路徑，在路徑上仍有流可以跑，其曾廣的流就是該條路徑上最小的剩餘容量。（相當於每找一條增廣路，就至少有一條邊達到滿流。）
直到在圖中找不到增廣路，此時已經達到了最大流。
找ST集合：把滿流的邊去掉，從S出發走到能到的點，遍歷的點就是S集合；剩下的點就屬於T集合。注意，如果找到了在找S集合的時候找到了T點，說明還可以繼續找增廣路。
[補]有一個很有趣的延伸，如多源點多終點問題。問：如果我有兩個源點s1，s2，兩個終點t1，t2，我想求一組流，使得s1-t1，s2-t2的流達到最大，是否可以加一個源點S，S與s1，s2相連，邊流無限大；加一個終點T，T與t1，t2相連，邊流無限大，然後這組ST的最大流即可。——答案是No，無法保證是s1-t1，s2-t2，有可能交錯。
例子講的感覺不是特別好，對理解感覺起不到很大作用，希望以後有新的想法後進行補充。
規約是一個重要的概念和思想。
一個圖的 最大獨立集 與 最小點覆蓋 是不相交的兩個點集，它們的並就是整個點集。
個人理解：獨立集和點覆蓋都是從點的角度進行劃分的，如果我們從邊的角度來看，①一個最小的點覆蓋即為我集合中的每一個點都盡可能與更多的邊相連，②同時，一條邊的兩個端點中，只能有一個端點在最小點覆蓋中[下注]
[注]我們假設有一條邊兩個端點（u，v）都在點覆蓋之中，首先顯然u，v都不是端點，因為假設u是端點的話只需要選擇v即可；
給一個集合S和一堆S的子集S1，S2，...，Sm，問是否存在存在k個子集，使它們的並集為S。
構造：
集合為點，集合中的元素為邊，有相同元素的邊相連。（注意如果某一元素只在一個子集中出現，應該怎麼處理呢！）
規約：在構造的圖中找最小的點覆蓋，選中的點能覆蓋所有的邊即為對應集合的並集能包含所有的元素。所以就完成了集合覆蓋到點覆蓋的規約。
構造：每個句子構造一個三角形，把對應變數但是相反取值的點相連。
規約：3SAT的有一個特點就是，每一個句子中至少有一個為真即可，每個句子都必須是真。將相同變數相反取值相連的目的就是，在最大獨立集中，比如選擇x為真，則剩下所有句子中x-ba一定不會被選中，同時由獨立集和構造出來三角形的性質可以知道，每一個句子，有且僅有一個會被選中（為真）。如上圖，x1-ba為真，x2-ba和x3任選一個為真即可滿足。
search problem <=p decision version
比如：如果能在多項式時間內找到一個哈密爾頓圈，那麼就能在多項式時間內找到一個哈密爾頓圈（刪邊）
在此再談P和NP：
我們知道有些問題是可以從搜索問題規約到判斷問題的，也就是所該問題如果能在多項式內判斷，那麼久能在多項式中搜索到，那麼我們只需要說，這個判斷問題能在多項式時間內求解，就叫做P問題，也就是上圖紅字的意思；那NP問題呢，必須要給出一個解的實例，判斷的是這個實例是否滿足求解問題，這個才是上圖中的紅字。比如，我如果能在多項式時間內判斷哈密爾頓圈是否（Yes/No）存在，那這個就是ploy-time algorithm，如果我給出了一系列點，能過多項式時間內判斷這些點能否構成哈密爾頓圈，那這個就是poly-time certifier。
構造：把一個點拆分成三個點。
構造：（下面兩個圖要連在一起看）
從行的角度看，一行代表一個變數；從列的角度來看，每三列代表一個句子。兩邊中一邊是兩個點，一邊是一個點，所以有k個句子的話，每一行有3k+3個節點。從哈密爾頓圈的答案轉到3SAT的答案看這個圈在每一行是從左到右還是從右到左。
子集和問題：給一個集合S，問是否能在集合中選取元素，使得總和為W。
構造：如下圖，按照前六行和前三列進行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，變數v列和 變數為v（包括變數及取反）的行對應的格子為0，其餘為0；第三部分全為0；第四部分按照12依次寫下來。第二部分，如果Ci句子中有變數v，則記為1，因為一個句子只有三個變數，可以簡單通過第二部分每一列和為3進行判定。此時集合已經構造出來，W為111444，與上面的規約相似，可以通過3SAT的簡單性質進行感性的認知。
近似的想法很簡單，要解決一個問題，我們希望能夠做到①求解結果是最優的 ②在多項式時間內解決 ③對於任意的實例都能夠通過該演算法解決。現在對於部分問題，無法完全滿足以上要求，所以就犧牲了①，但是我們希望結果不是盲目的，所以就引入了近似的概念。
近似演算法。比如2-近似，認為W為近似解，W 為最優解，在求最小值的情況下W<=2W ；在求最大值的情況下，W>=1/2W*
給m個機器和n個任務，每個任務有一個ti的執行時間，我們認為完成最後一個任務所需的時間為負載時間，希望能夠讓這個負載時間最短。
第一種：將任務依次放在機器上，當某個機器空閑時立即放入新任務。此時是2近似的。
證明：
引理1.最短時間安排是大於等於任務中時間最長的任務，L* >= max tj
我們在考慮放入最後一個任務前，根據我們放置的規則，該機器是耗時最短，也就是說，該機器此時的用時是低於除掉最後一個任務後的平均時長，更低於所有任務的平均時長（引理2）；再根據引理1，最後一個任務應該是小於最優解的。
補充：
在這里，我還想討論一下這個近似演算法的中等於符號，先上結論：等號不一定能夠找到一個實例，但是可以構造出一種結構，通過取極限求得，我們認為這樣 也算是緊的。
構造實例：有m個機器，其中m(m-1)個任務的用時為1，1個任務的用時為m。肯定有一種任務集合，可以按照以下方式進行安排，此時的貪心解為19。
此時最佳的解為10，如下圖：
通過推廣可以知道此時的比為（2m-1）/m，當m取極限，能夠達到2倍。
第二種：將任務從大到小排序，然後依次放在機器上，當某個機器空閑時立即放入新任務。此時是2近似的。
引理3：如果有大於m個任務，那麼L*>=2t(m-1)。證明：t(m+1)是目前最短的任務，且目前所有機器上都有任務了，所以該任務加入時最優的情況不過是加入設備的原有任務剛好和t(m+1)相等，即等號。
（2近似）在n個點中，選取k個中心點，使得這些中心點能夠以半徑R的圓包含所有的點，讓其中最大的半徑最小，如下圖所示：
基礎：距離需要滿足的三個定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)
r(C)為C集合中所有點的最大覆蓋半徑。（需要求min r(C)）
演算法：在點集中任選一個作為中心點，然後重復以下步驟k-1次:選取距離已選點集中最遠的點，加入點集。
證明：先假設r(C )< 1/2 * r(C)以選好的點畫半徑為1/2 * r(C)的圓，顯然可知[注]，這個圓里有且僅有一個r(C )中的點。那麼根據在下圖中，根據三角不等式可以得出：
[注]在每個點上r(c )一定會包含到c點，而r(C )<1/2 * r(C)，相當於大圓套小圓，所以c*一定在c的圓中。
（2近似）問題還是很好理解的，在點上加權值，要找一個點覆蓋，使得權值最小。如下圖左邊就是一個帶權的最小點覆蓋。
演算法： 任選一條邊(i, j)加上代價，這個代價從零開始，且這個代價的最大值低於i和j節點的權值。顯然，這個邊權值的最大值取決於兩個端點權值的最小值，我們認為當邊權值與點權值相等時，對應的那個點是緊的。把所有緊的點找出來即為點覆蓋。
流程：
證明：
引理：邊權之和小於等於點覆蓋的點權之和。這主要是由於涉及到一條邊上兩個點都被選（緊的）的情況，感性認知可以看上圖，縮放證明如下：
w(S)是等於所選的節點的權值之和的，等於所選節點節點所對應的邊權之和，可以把它放大到所有節點對應邊權之和，這樣因為一條邊(u, v)在u上算過一次後還要在v上算一次，所以等於邊權和的兩倍。再由上面引理可得。
主要為了線性規劃和整數規劃。
（2近似）沒啥好說的，只需要把方程構造出來就行了。
由於求解出來結果不一定是整數，所以我們認為某一點的值大於1/2，就選入點集。
證明：
因為xi+xj >=1,且都是正數，那必至少一個點是大於1/2的（反證，兩個都小於1/2則和小於1）。
給你n個物品和一個背包，每個物品有一個價值v和一個大小w，背包的容量是W，要求讓背包裝下盡可能大價值。
背包的時間復雜度：O(nW)
注意其中n表示物品的個數，無論是1個還是999個，他都是多項式的，這個很好理解。但是W就不一樣了，這是一個數字。我理解的是這個數字會很奇特，比如1.00001，比如99999，這些有可能看起來不大但是實際在處理的時候很難處理的數字，統一的來說，如果我們把這些數字放在電腦上，都會以二進制的方式存儲起來，有些數字用十進製表示很小，但是放在二進制上面就會很大，由W導致不能在多項式時間內解決（找不到一個范圍/上界來框它）。
演算法： 為了處理這個問題，我們改動了dp的狀態轉移方程，要讓這個轉移方程和W無關[注]。
此時還不是多項式的，然後我們再對value進行約。[注]
[注]這兩步中，我們把w改成v，並對v進行近似處理。OPT的含義變成了，在面對是否選擇第i個物品時，要想讓價值達到當前值，最少的weight。理由是更改後的誤差是可以忍受的：對v進行近似，結果只會出現最大價值的上下誤差，如果對w進行近似，則有可能出現該物品不能放入背包中，導致整個物品直接放棄的情況。
Ⅳ 高分：網路流問題
一、引言
網路流演算法是一種高效實用的演算法，相對於其它圖論演算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些演算法（如最短路徑、寬度搜索演算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非np問題。
網路流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網路流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網路流演算法的效率。
二、網路流演算法時間效率
當我們確定問題可以使用最大流演算法求解後，就根據常用的ford-fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶演算法解題。ford-fulkerson標號法的運行時間為o（ve2），對偶法求最小費用流的運行時間大約為o（v3e2）。
顯然，影響網路流演算法的時間效率的因素主要是網路中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網路模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。
三、模型的優化與選擇
(一)減少模型的頂點數與邊數，優化模型
如果能根據問題的一些特殊性質，減少網路模型中的頂點的數目和邊的數目，則可以大大提高演算法的效率。
例1：最少皇後控制
在國際象棋中，皇後能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇後的位置，標有k的格子為皇後可攻擊到的格子）。現在給定一個m*n（n、m均不大於於50）的棋盤，棋盤上某些格子有障礙。每個皇後被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇後所控制。
請你編一程序，計算出至少有多少個皇後才能完全控制整個棋盤。
圖1(a) 圖1(b)
輸入格式：
輸入文件的第一行有兩個整數m和n，表示棋盤的行數與列數。接下來m行n列為一個字元矩陣，用''.''號表示空白的格子，''x''表示有障礙的格子。
輸出格式：
輸出文件的第一行僅有一個數s，表示需要皇後的數目。
sample input
3 4
x...
x.x.
.x..
sample ouput
5
問題分析]
如果本問題用簡單的搜索來做，由於題目給的棋盤很大，搜索演算法很難在短時間內出解。由於一個皇後在棋盤最多隻能控制兩個格子，因此最少需要的皇後數目的下界為[n*m/2]。要使得皇後數目最少，必定是盡量多的皇後控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似於二分圖的最大匹配問題。
[模型一]
1． 將每個非障礙的格子按行優先編號(0~m*n-1)。
2． 將上述的每個格子i折成兩個格子i''和i''''，作為網路模型中的頂點。
3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i''到j''''之間加上一條有向弧，容量為1。
4． 增加一個源點s，從s點向所有頂點i''添上一條弧；增加一個匯點t，從所有頂點j''''到t添上一條弧，容量均為1。
圖1(b)所示的棋盤，對應的模型為：
圖2
顯然，任一解對應於以上模型的一個最大匹配。且最大匹配中，匹配數必定是偶數。因此至少需要的馬匹數為m＊n－障礙數－最大匹配數/2。
[模型二]
如果我們將棋盤塗成黑白相間的格子，則某皇後控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設這兩個格子中皇後在白格子上。於是，我們將n*m個格子分成兩部分白格與黑格。因此我們可以將模型一優化為：
圖3
1．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構成一個二分圖。
2．增加一個源點s，從s點向所有非障礙的白格添上一條弧；增加一個匯點t，從所有非障礙的黑格到t添上一條弧。
3．設置所有的弧的流量為1。
圖1(b)所示的棋盤，對應的模型為：
圖4
[兩種模型的比較]
顯然，模型二的頂點數與邊數大致是模型一的一半。下面是在bp環境下兩種模型的時間效率比較(p166/32m)：
模型一 模型二
可擴展性 不易列印出一種解 容易列印出一種解
模型二正是根據問題的特殊性（即馬的走法），將網格中的格點分成白與黑兩類，且規定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數，同時也大大減少了邊的數目。達到了很好的優化效果。
(二)綜合各種模型的優點，智能選擇模型
有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優缺點，根據測試數據智能地選擇問題的模型。
例2火星探測器（ioi97）
有一個登陸艙（pod），里邊裝有許多障礙物探測車（mev），將在火星表面著陸。著陸後，探測車離開登陸艙向相距不遠的先期到達的傳送器（transmitter）移動，mev一邊移動，一邊採集岩石（rock）標品，岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過。探測車mev不能通過有障礙的地面。
本題限定探測車mev只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車mev在同一時間占據同一位置。
任務：計算出所有探測車的移動途徑，使其送到傳送器的岩石標本的數量最多，且使得所有的探測車都必須到達傳送器。
輸入：
火星表面上的登陸艙pod和傳送器之間的位置用網路p和q表示，登陸艙pod的位置為（1，1）點，傳送器的位置在（p，q）點。
火星上的不同表面用三種不同的數字元號來表示：
0代表平坦無障礙
1代表障礙
2代表石塊。
輸入文件的組成如下：
numberofvehicles
p
q
(x1y1)(x2y1)(x3,y1)…(xp-1y1)(xpy1)
(x1y2)(x2y2)(x3,y2)…(xp-1y1)(xpy2)
(x1y3)(x2y3)(x3,y3)…(xp-1y3)(xpy3)
…
(x1yq-1)(x2yq-1)(x3,yq-1)…(xp-1yq-1)(xpyq-1)
(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)
p和q是網路的大小；numberofvehicles是小於1000的整數，表示由登陸艙pod所開出的探測車的個數。共有q行數據，每行表示火星表面的一組數據，p和q都不超過128。
[模型一]
很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過，且允許多個探測車mev在同一時間占據同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網路模型構造如下：
1． 將網格中的每個非障礙點分成(x,y)兩個點(x,y,0)和(x,y,1)，其中源點s = v(1, 1, 0),匯點t = v(maxx, maxy, 1)。
2． 在以上頂點中添加以下三種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = maxint,w1 = 0。
u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（這里要求(x, y)必須是礦石）
u e3 = v(x, y, 1) -> v(x'', y'', 0)，c3 = maxint,w3 = 0.
其中x''=x+1 y''=y 或x''=x y''=y+1,1 <= x'' <= maxx，1 <= y'' <= maxy，且(x'' y'')非障礙。
從以上模型中可以看出，在構造的過程中，將地圖上的一個點"拆"成了網路的兩個節點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對於這個網路，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數目。對於網路g求流量為numberofvehicles的固定最小費用流，可以得到問題的解。
[模型二]
事實上，如果我們只考慮這numberofvehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經過的礦石就是一條流，因此我們以網格中的礦石為網路的頂點建立以下的網路流模型。
1. 將網格中的每個起點(網格左上角)能到達，且能從它能到達終點(右下角)的礦石 (x,y)點分成左點(x,y,0)和右點(x,y,1)兩個點，並添加源點s和匯點t。
2. 在以上頂點中添加以下五種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。
u e2 = v(x, y, 1) -> v(x'', y'', 0)，c2 = 1，w2 = 0（礦石點(x, y)可到達礦石點(x'',y'')）。
u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。
u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。
u e5=s->t,c5=maxint,w5=0。
由於每個石塊被折成兩個點，且容量為1，就保證了每個石塊只被取走一次，同時取走一塊石塊就得到-1的費用。因此對以上模型，我們求流量為numberofvehicles的最小費用流，就可得到解。
[兩種模型的比較]
1.模型一以網格為頂點，模型二以礦石為頂點，因此在頂點個數上模型二明顯優於模型一，對於一些礦石比較稀疏，而網格又比較大的數據，模型二的效率要比模型一來得高。且只要礦石的個數不超過一定數目，模型二可以處理p，q很大的數據，而模型一卻不行。
2．模型一中邊的數目最多為3*p*q，而模型二中邊的數目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對於一些礦石比較密集且網格又比較大的數據，模型二的邊數將大大超過模型一，從而使得時間效率大大低於模型一。
下面是網格中都是礦石的情況比較（piii700/128m ，bp7.0保護模式）：
numberofvehicles＝10 模型一 模型二
通過以上數據，可知對於p，q不超過60的情況，模型一都能在10秒內出解。而模型二則對於p、q＝30的最壞情況下速度就很慢了，且p、q超過30後就出現內存溢出情況，而無法解決。
因此，對於本題，以上兩種模型各有利弊，我們可根據測試數據中礦石稀疏程度來決定建立什麼樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網路模型；若礦石比較密集則建立模型一所示網路模型。然後，再應用求最小費用最大流演算法求解。對於p，q＞60，且礦石比較多情況下，兩種模型的網路流演算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合一些其它演算法來求解。
四、結束語
綜上所述，網路流演算法中模型的優化是網路流演算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高演算法的效率。對於有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下採用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。