《高級算法設計》課件 第1、2章 線性規(guī)劃;高級圖算法

高級算法設計與分析線性規(guī)劃基本概念基本概念基本概念線性規(guī)劃的形式：線性規(guī)劃：定義標準型和松弛型標準型和松弛型非標準型目標函數(shù)不是最大化，而是最小化約束條件是大于等于約束約束條件是等式約束;存在一些變量沒有非負約束標準型和松弛型非標準型例子標準型和松弛型標準型和松弛型標準型和松弛型標準型：標準型和松弛型松弛型：在松弛型中，等式左邊的變量x4,x5,x6被稱為基本變量，等式右邊的變量x1,x2,x3被稱為非基本變量矩陣形式：標準型和松弛型圖解法將可行域為：ABCDEF的邊界和內(nèi)部，A,

B,

C,

D,

E,

F稱為極點圖解法單純形法如果我們能夠?qū)⑸鲜瞿繕撕瘮?shù)的所有變量的系數(shù)全部轉換為負數(shù)單純形法步驟松弛基本解為(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)單純形法步驟基本解為(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)在此基本解下，目標函數(shù)的值為0通過增大x1或x2來使目標函數(shù)變大單純形法步驟目標函數(shù)中x1的系數(shù)大于x2，選擇增大x1約束條件4的約束最緊湊單純形法步驟約束條件4變?yōu)橛眠@個表達式替換目標函數(shù)和其他約束條件中的x1

單純形法步驟目標函數(shù)的值為16單純形法步驟用這個表達式替換目標函數(shù)和其他約束條件中的x2

單純形法步驟單純形表注意表格中的值是變量系數(shù)的值（取負），目標函數(shù)變量的系數(shù)同樣取負單純形表1.從目標函數(shù)中選擇一個需要變大的變量（系數(shù)最?。﹛12.找出最緊湊約束最緊湊約束是b/(x1系數(shù))最小的約束（第4行約束）3.x1變量替入為基變量，而原來的基變量x6替出為非基變量單純形表1.從目標函數(shù)中選擇一個需要變大的變量（系數(shù)最?。﹛12.找出最緊湊約束最緊湊約束是b/(x1系數(shù))最小的約束（第4行約束）3.x1變量替入為基變量，而原來的基變量x6替出為非基變量單純形表4.用x1的表達式替換目標函數(shù)和其他約束條件中的x1

高斯消元單純形表4.用x1的表達式替換目標函數(shù)和其他約束條件中的x1

高斯消元重復上述步驟單純形表重復上述步驟最緊湊約束為第一行約束，對第一行進行替入和替出操作單純形表重復上述步驟用第一行約束對所有其他約束行和目標函數(shù)行進行x2高斯消元對偶對偶性是線性規(guī)劃最重要的內(nèi)容之一每個線性規(guī)劃（LP1）必然有與之相伴而生的另一個線性規(guī)劃問題（LP2），即任何一個求maxz的LP1都有一個求minw的LP2對偶對偶矩陣形式對偶例子對偶對偶規(guī)則（標準型）原問題的目標函數(shù)是最大化，對偶問題的目標函數(shù)是最小化，原問題的約束條件是小于等于，對偶問題的約束條件是大于等于原問題約束條件的個數(shù)(m)決定對偶問題變量的個數(shù)，且第一個約束條件對應第一個變量，第二個約束條件對應第二個變量，以此類推對偶對偶規(guī)則（標準型）原問題變量的個數(shù)(n)決定對偶問題約束條件的個數(shù)，且第一個變量對應第一個約束條件，第二個變量對應第二個約束條件，以此類推對偶問題的目標函數(shù)中每個變量的系數(shù)由其對應原問題中約束條件b值決定對偶問題約束條件的c值是其對應變量(原問題)在目標函數(shù)的系數(shù)，約束條件中各變量的系數(shù)是其對應變量(原問題)在約束條件中的系數(shù)對偶對偶：例子對偶：例子對偶是怎么來的設線性規(guī)劃的原始問題：轉化為優(yōu)化問題的標準形式對偶是怎么來的對偶是怎么來的對偶是怎么來的對偶問題可以化為對偶是怎么來的如果對原問題按照“原問題和對偶問題的轉換”表可得：等價對偶例子：矩陣博弈矩陣博弈：猜硬幣，兩個參與者分別同時從兩個硬幣(一元和兩元)中選取一個讓對方猜，如果都猜錯或都猜對，繼續(xù)玩，如果只有一方猜對，則猜對一方贏得此次雙方的所有硬幣對偶例子：矩陣博弈矩陣博弈：猜硬幣，收益矩陣如下：行和列表示（player1和player2）的策略（選取的硬幣和猜對方的硬幣），如（1，2）表示選取硬幣1元，猜對方選取的是2元；矩陣的值表示列player2的收益

對偶例子：矩陣博弈對偶例子：矩陣博弈對偶例子：矩陣博弈對偶例子：矩陣博弈對偶例子：矩陣博弈對偶例子：矩陣博弈即player2

LP問題C的對偶問題即為player1的LP問題R對偶性質(zhì)線性規(guī)劃標準式對偶性質(zhì)可得：即：對偶性質(zhì)：弱對偶性對偶性質(zhì)：強對偶性和互補松馳性對偶性質(zhì)：互補松馳性如果原問題和對偶問題得出的解滿足互補松弛性，則為最優(yōu)解互補松馳性例子互補松馳性例子原問題的對偶問題為互補松馳性例子互補松馳性例子原問題的對偶問題為互補松弛性可得互補松馳性例子整數(shù)規(guī)劃當變量的取值從實數(shù)變?yōu)檎麛?shù)后，這個問題到底是變難了，還是變?nèi)菀琢?整數(shù)規(guī)劃松弛整數(shù)規(guī)劃：分支限界分支限界：例子對線性規(guī)劃問題求解，得最優(yōu)解為x1=2.5,x2=2.25，目標函數(shù)為21.5分支限界：例子此時，可以對x1進行分支，也可對x2進行分支。對x1進行分支，則分為x1≤2和x1≥3兩部分。

分支限界：例子對左邊分支(x1≤2)求解得x1=2,x2=2.5，目標函數(shù)為20對右邊分支(x1≥3)求解得x1=3,x2=1.5，目標函數(shù)為21分支限界：例子接著搜索節(jié)點3，對x2進行分支，則分為x2≤1和x2≥2兩部分分支限界：例子對左邊分支(x2≤1)求解得x1=3.3,x2=1，目標函數(shù)為20.7而右邊分支(x2≥2)無可行解。分支限界：例子接著搜索節(jié)點4，對x1進行分支，則分為x1≤3和x1≥4兩部分分支限界：例子對左邊分支(x1≤3)求解得x1=3,x2=1，目標函數(shù)為19，找到整數(shù)解，結束搜索而右邊分支(x1≥4)無可行解分支限界：例子因為節(jié)點2的上限大于目前找到的最優(yōu)值19，需要繼續(xù)搜索，對x2進行分支，則分為x2≤2和x2≥3兩部分分支限界：例子對左邊分支(x2≤2)求解得x1=2,x2=2，目標函數(shù)為18而右邊分支(x2≥3)無可行解最終的最優(yōu)解為x1=3,x2=1，最優(yōu)值為190-1整數(shù)規(guī)劃整數(shù)規(guī)劃的一個特列是0-1整數(shù)規(guī)劃，也就是參數(shù)的取值只能是0或1。很多算法問題都可以建模成0-1整數(shù)規(guī)劃問題，如0-1背包問題、任務分配、集合覆蓋等問題。0-1整數(shù)規(guī)劃：建模0-1背包問題中，設背包的承重為C，共n個物品，每個物品的重量和價值分別為wi和vi，則問題建模為0-1整數(shù)規(guī)劃：建模在應用中，有時會遇到變量可以取多個整數(shù)值的問題。如果用0-1變量來表示，也可以用一組0-1變量來取代。

如x取0－9之間的任意整數(shù)時。

x=20x0+

21x1+

22x2+

23x3￡90-1整數(shù)規(guī)劃：建模含有相互排斥的約束條件的問題（1）兩個約束中，只有一個起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

解：引入0-1變量Y1,Y2和足夠大的正數(shù)M，則a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=10-1整數(shù)規(guī)劃：建模某企業(yè)生產(chǎn)產(chǎn)品的費用如下，建立0-1規(guī)劃模型單耗量產(chǎn)品資源IIIIII資源量A248500B234300C123100單件可變費用456固定費用100150200單件售價810120-1整數(shù)規(guī)劃：建模解：設Xj是第j種產(chǎn)品的產(chǎn)量。Yj是0－1變量，表示是（Yj=1）否（Yj=0）生產(chǎn)第j種產(chǎn)品。maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X3￡5002X1+3X2+4X3￡300X1+2X2+3X3￡100X1￡

M1Y1X2￡

M2Y2X3

￡

M3

Y3X1,

X2,

X330整數(shù)Y1,Y2,Y3為0－1變量。

s.t.0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法原始-對偶算法通過對偶問題來求解原問題的最優(yōu)解或者近似解，統(tǒng)稱為原始-對偶算法對于0-1整數(shù)規(guī)劃問題，是很難通過互補松弛性來求得最優(yōu)解，但我們依然可以通過原問題(Primal)和對偶問題(Dual)的弱對偶性來求得一個近似解原始-對偶算法原始-對偶算法原始-對偶算法原始-對偶算法的應用：頂點覆蓋頂點覆蓋問題是指從圖中選取最少的頂點，這些頂點能夠覆蓋圖中所有的邊(一個頂點覆蓋一條邊，指這個頂點和這條邊相連)。數(shù)學模型。設G=(V,E)，節(jié)點個數(shù)為n，邊的條數(shù)為m，令xv

為0-1變量，0代表不選取頂點v，1代表選取頂點v，則頂點覆蓋的0-1整數(shù)規(guī)劃模型:原始-對偶算法的應用：頂點覆蓋頂點覆蓋問題是指從圖中選取最少的頂點，這些頂點能夠覆蓋圖中所有的邊(一個頂點覆蓋一條邊，指這個頂點和這條邊相連)。對偶：圖的最大匹配問題原始-對偶算法的應用：頂點覆蓋擴展頂點覆蓋問題：給每個頂點都賦予一個權重wv(wv>0)，頂點覆蓋問題轉化為求頂點集合，使其能夠覆蓋所有的邊且頂點集的總權重最小。線性模型對偶模型原始-對偶算法的應用：頂點覆蓋原始-對偶算法來求解帶權重頂點覆蓋問題的近似最優(yōu)解。原始-對偶算法的應用：頂點覆蓋原始-對偶算法來求解帶權重頂點覆蓋問題的近似最優(yōu)解。原始-對偶算法的應用：頂點覆蓋原始-對偶算法的應用：頂點覆蓋高級算法設計與分析高級圖算法主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法流網(wǎng)絡找到一個從s出發(fā)，到t的流量最大的流，這就是最大流問題網(wǎng)絡的流網(wǎng)絡的流需要滿足的兩個條件：網(wǎng)絡的流如何找到最大流從流量為0開始，逐步增加流量，直到達到最大流量為止從s出發(fā)，找到一條到t的可行路徑，并將流增加到這個路徑能夠支持的最大流量在剩余的流網(wǎng)絡（殘存網(wǎng)絡）中再找一條可行的路徑，增加相應的流重復以上步驟網(wǎng)絡的流原始流網(wǎng)絡找到一條路徑殘存網(wǎng)絡？殘存網(wǎng)絡網(wǎng)絡的流殘存網(wǎng)絡新的路徑：新的流網(wǎng)絡網(wǎng)絡的流殘存網(wǎng)絡此時已無法在此殘存網(wǎng)絡中再找到一條從s到t的路徑，前面的流為最大流Ford-Fulkerson算法Ford-Fulkerson算法Ford-Fulkerson算法的兩個問題當在殘存網(wǎng)絡中無法再找出一條從s到t的路徑時，那么得到的流一定是最大流嗎？最大流最小割定理在殘存網(wǎng)絡中如何找到一條從s到t的路徑？Edmonds-Karp算法最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理設f是最大流，其所對應的殘存網(wǎng)絡Gf還存在一條從s到t的路徑p，

在殘存網(wǎng)絡Gf

上可以找到一個流f′

最大流最小割定理最大流最小割定理結論1:也就是由最大流最小割陳述2得出的(S,T)割上，(S,T)的流量(從S到T的流量)等于(S,T)的容量最大流最小割定理(S′,T′)是任意s-t割,根據(jù)能量守恒來證明，即從源節(jié)點s來的流f等于從集合S流到T的流

結論2:是s?t流f等于任意(S′,T′)割最大流最小割定理(S′,T′)是任意s-t割結論3:

f小于等于任意(S′,T′)割的容量最大流最小割定理由結論1和結論2，可知s?t流f等于(S,T)割的容量，即f=C(S,T)結合結論3

，可知(S,T)割的容量小于等于任意割，即C(S,T)≤C(S′,T′)，即C(S,T)是最小割

最大流最小割定理Edmonds-Karp算法在殘存網(wǎng)絡中如何找到一條從s到t的路徑?圖的深度優(yōu)先遍歷方法？Edmonds-Karp算法最短路徑算法Dijsktra算法(復雜度O(mlogn))廣度優(yōu)先搜索（O(m)）短路徑為vs→v2→vt

或者vs→v3→vt，所以通過兩次增廣路徑即可找到網(wǎng)絡的最大流Edmonds-Karp算法：復雜度基于最短路徑算法證明：設在殘存網(wǎng)絡G中找到流f，形成新的殘存網(wǎng)絡G’。從G到G’，增加了指向上一層級的邊，并刪除了指向下一層級的關鍵邊增加的邊并不會減少從s到其他節(jié)點的距離，但減少的邊有可能會增加s到其他節(jié)點的距離，所以引理得證Edmonds-Karp算法：復雜度基于最短路徑算法Edmonds-Karp算法：復雜度邊ei→j再次成為關鍵邊時，源節(jié)點到vi的距離至少增加了2跳Edmonds-Karp算法：復雜度可以得出邊ei→j最多(n?2)/2次成為關鍵邊總的關鍵邊的次數(shù)為O(m?(n?2)/2)=O(mn)Edmonds-Karp算法最大容量路徑也為vs→v2→vt

或者vs→v3→vt，所以也通過兩次增廣路徑即可找到網(wǎng)絡的最大流最大容量路徑算法Dijsktra算法

Edmonds-Karp算法

Dijkstra算法，對路徑的邊求最小容量，并最大化之，Edmonds-Karp算法Edmonds-Karp算法流量分解證明Edmonds-Karp算法流量分解證明由流量守恒，可得：在每次容量更新中，路徑中最小容量的邊(至少一條)的容量會被置0，因圖G邊的條數(shù)是mEdmonds-Karp算法流量分解定理說明了最大流fopt

可以被分解為最多m個路徑流{f1,f2,···,fm}，在這些路徑流中，必然存在一個流fk≥fopt/m,1≤k≤m，而此流所在路徑上所有邊的容量必然≥fopt/m。引理得證。Edmonds-Karp算法Edmonds-Karp算法如果原始圖G的邊數(shù)為m，則在任意的殘存圖Gt中，其邊的條數(shù)不會超過2m，所以對任意殘存圖Gt，剩余最大流為

因為容量都為整型主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法圖的中心性算法度中心性(DegreeCentrality):一個點與其他點直接連接的程度緊密中心性(ClosenessCentrality):一個節(jié)點到所有其他節(jié)點的距離，一個擁有高緊密性中心性的節(jié)點擁有著到所有其他節(jié)點的距離較小;中介中心性(BetweennessCentrality):一個節(jié)點位于最短路徑上的次數(shù)，如果有很多條最短路徑經(jīng)過此節(jié)點，說明此節(jié)點的中介中心性越高;特征向量中心性(EigenvectorCentrality):一個節(jié)點的重要性有時也取決于其鄰居節(jié)點的重要性，與之相連的鄰居節(jié)點越重要，則該節(jié)點特征向量中心性就越高;PageRank:PageRank也是考慮鄰節(jié)點重要性的一種中心性算法，可看出是特征向量中心性的一種變體。度中心性度中心性是來衡量一個節(jié)點重要性相對簡單的算法，其基于一個非常直接的觀察，和越多其他節(jié)點連接的節(jié)點越重要緊密中心性緊密中心性用來衡量一個節(jié)點處于圖的中心的程度，當一個節(jié)點越處于中心的位置，則其在圖上散播信息的能力越強。為了適應圖不是強連通圖的情況，采用調(diào)和平均數(shù)緊密中心性前面的表述形式難以處理這種對幾個子圖進行連接的情形緊密中心性Dangalchev變體中介中心性在社交網(wǎng)絡中，有時候并不是那些具有最多關注者的節(jié)點(度中心性)或者處于網(wǎng)絡中心位置的節(jié)點(緊密中心性)是最重要的，而是那些起著關鍵橋梁或者中介作用的節(jié)點起著決定性的作用其中，σjk

是節(jié)點vj到節(jié)點vk

的最短路徑的個數(shù)，σijk是節(jié)點vj到節(jié)點vk

且經(jīng)過節(jié)點vi

的最短路徑的個數(shù)中介中心性假設從節(jié)點vj

到vk

的最短路徑在就要到達vk

前，可沿著不同的路徑分別經(jīng)由三個節(jié)點u1、u2、u3，也就是u1、u2、u3

是vk

在最短路徑上的前一鄰節(jié)點中介中心性中介中心性算法如何降低復雜度？快速中介中心性算法累積節(jié)點對依賴簡單場景節(jié)點vs

到任意其他節(jié)點只存在一條最短路徑，即σst=1,?vt∈V

快速中介中心性算法累積節(jié)點對依賴：簡單場景快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法累積節(jié)點對依賴：簡單場景從前面的例子可以看出，累積節(jié)點對依賴(δ值)是個遞歸式，所以其計算類似于動態(tài)規(guī)劃，也就是從最底層的值，這里是樹中葉子節(jié)點的δ值(其值為0)開始計算，依次沿著樹枝向跟節(jié)點計算快速中介中心性算法累積節(jié)點對依賴：一般場景在簡單場景中，如果最短路徑經(jīng)過某個節(jié)點vj，則必然經(jīng)過其父節(jié)點。但是在一般場景中，并不存在這樣的關系，也就是最短路徑經(jīng)過節(jié)點vj，但并不一定經(jīng)過其前一跳鄰節(jié)點從vs

到vk

的最短路徑數(shù)目共有σsk

個，從vs

到v1

的最短路徑數(shù)目共有σs1

個。所以我們只需考慮σsk/σs1

比例的最短路徑快速中介中心性算法累積節(jié)點對依賴：一般場景特征向量中心性在度中心性中，節(jié)點的重要程度只考慮了連接數(shù)，而沒有考慮到連接節(jié)點的重要程度。在社交網(wǎng)絡上，和一個有影響力的節(jié)點有連接關系，顯然比和一個普通節(jié)點有連接關系，更能使提高自身的重要程度。特征向量中心性特征向量中心性圖的鄰接矩陣特征向量中心性第一次迭代特征向量中心性第二次迭代特征向量中心性第三次迭代特征向量中心性第四次迭代收斂時特征向量中心性從以上式子可知，特征向量中心性x是圖的鄰接矩陣A的特征值為λ時的特征向量，這就是為什么稱之為特征向量中心性的原因特征向量中心性特征向量中心性發(fā)現(xiàn)節(jié)點3和節(jié)點5

的特征向量中心性是一致的，這個從圖12.7很容易得到驗證，這兩個節(jié)點的鄰節(jié)點是相似的，它們都連接了4節(jié)點，同時連接對方。此外，節(jié)點4具有最大的特征向量中心性，這個從圖中也容易得出，節(jié)點4具有最多的鄰節(jié)點，且其鄰居具有較大的特征向量中心性值。PageRankPageRank是谷歌的網(wǎng)頁排序算法，可以認為其特性向量中心性算法的一個變體：節(jié)點的重要性不僅僅取決于有多少個其他節(jié)點指向自己，同時也取決于那些指向自己的節(jié)點的重要性PageRankPageRankPageRankPageRankPageRank另得主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法社群發(fā)現(xiàn)社群發(fā)現(xiàn)基于模塊度的算法基于標簽傳播的算法基于團的算法社群發(fā)現(xiàn):基于模塊度的算法模塊度其中m是圖邊的條數(shù);A為鄰接矩陣，也就是說如vi和vj間存在邊，Aij=1，否則，Aij=0;ki表示vi的度;Si表示vi所屬的社群，Sj表示vj所屬的社群，當Si=Sj時，δ(Si,Sj)=1，當Si?