運籌學(xué)：第六章 圖與網(wǎng)路分析2

6.4.5

以最短路為基礎(chǔ)匯總網(wǎng)路上的流在電路網(wǎng)中每兩點之間都有中繼電路群需求，但并不是任兩點都有物理傳輸鏈路根據(jù)兩點間最短傳輸路徑將該兩點間的電路需求量加載到這條傳輸路徑上去：設(shè)a25=10是節(jié)點2和5之間的電路需求，節(jié)點2和5之間的最短傳輸路徑為2135，則加載過程為:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是傳輸鏈路ij

上加載的電路數(shù)；當(dāng)所有點間電路都加載完則算法結(jié)束6.5歐拉回路和中國郵遞員問題中國郵遞員問題(ChinesePostmanProblem,CPP)是由我國管梅谷教授于1962年首先提出并發(fā)表的問題是從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，走什么路由才能使總的路程最短？如果街區(qū)圖是一個偶圖，根據(jù)定理3，一定有歐拉回路，CPP問題也就迎刃而解了若街區(qū)圖不是偶圖，則必然有一些街道要被重復(fù)走過才能回到原出發(fā)點顯然要在奇次點間加重復(fù)邊如何使所加的邊長度最少歸結(jié)為求奇次點間的最小匹配(minimumweightedmatch)—由Edmons給出多項式算法(1965)

解中國郵遞員問題的步驟0、將圖中的所有懸掛點依次摘去1、求所有奇次點間的最短距離和最短路徑2、根據(jù)奇次點間的最短距離求最小完全匹配3、根據(jù)最小完全匹配和最短路徑添加重復(fù)邊4、將懸掛點逐一恢復(fù)，并加重復(fù)邊5、根據(jù)得到的偶圖，給出歐拉回路的若干種走法

解中國郵遞員問題的步驟6.6哈密爾頓回路及旅行推銷員問題

6.6.1哈密爾頓回路(Hamiltoniancircuit)連通圖G(V,E)中的回路稱為哈密爾頓回路，若該回路包括圖中所有的點。顯然哈密爾頓回路有且只有n

條邊，若|V|=n連通圖具有哈密爾頓回路的充分必要條件是什么？這個問題是由愛爾蘭數(shù)學(xué)家哈密爾頓1859年提出的，但至今仍未解決歐拉回路是對邊進行訪問的問題，哈密爾頓回路是對點進行訪問的問題搜索哈密爾頓回路的難度是NP-complete任兩點間都有邊的圖稱為完全圖(或全連接圖)完全圖中有多少個不同的哈密爾頓回路？完全圖中有多少個邊不相交的哈密爾頓回路？最小哈密爾頓回路問題

(NP-complete)哈密爾頓路徑：包含圖中所有點的路徑為什么說找兩點間的最長路是非常困難的問題？(n1)!/2(n1)/26.6.2旅行推銷員問題(TravelingSalesman

Problem)旅行推銷員問題(TSP)：設(shè)v1,v2,...,vn

為n

個已知城市，城市之間的旅程也是已知的，要求推銷員從v1出發(fā)，走遍所有城市一次且僅一次又回到出發(fā)點，并使總旅程最短這種不允許點重復(fù)的旅行推銷員問題就是最小哈密爾頓回路問題一般旅行推銷員問題(GTSP)：允許點重復(fù)的TSP當(dāng)網(wǎng)路邊權(quán)滿足三角不等式時，一般旅行推銷員問題就等價于最小哈密爾頓回路問題當(dāng)網(wǎng)路邊權(quán)不滿足三角不等式時，只要用兩點間最短路的距離代替原來的邊權(quán)，就可以滿足三角不等式，在此基礎(chǔ)上求最小哈密爾頓回路

典型的應(yīng)用：鄉(xiāng)郵員的投遞路線郵遞員開郵箱取信的路線問題郵車到各支局的轉(zhuǎn)趟問題

TSP的啟發(fā)式算法(Heuristicalgorithm)窮舉法：指數(shù)算法分支定界法：隱枚舉法二交換法(two-option,Lin’salgorithm)哈密爾頓回路可以用點的序列表示從任一個哈密爾頓回路(即任何一個序列)出發(fā)按照一定順序試圖交換相鄰兩個點的順序，若路程減少則完成交換，繼續(xù)下一個交換；若沒有改善，則不進行本次交換，嘗試下一個交換；若所有的相臨交換都試過而不能改善，則算法結(jié)束，得到一個局部最優(yōu)點模擬退火(SimulatedAnnealing)隨機地采用二交換法當(dāng)交換后沒有使目標(biāo)函數(shù)改善，也可能以玻爾茲曼分布概率被接受，但這種概率是隨模擬的溫度下降而減少的發(fā)揮了計算機的優(yōu)點，盡量減少陷入局部極值點模擬物理機制

二交換法舉例初始解：1-2-3-4-51-3-2-4-51-3-2-4-51-3-4-2-51-3-4-2-51-3-4-5-25-3-4-2-13-1-4-2-5

算法復(fù)雜度(Complexityofalgorithm)算法：一步一步求解問題的步驟及其正規(guī)描述。問題：所謂“問題”就是需要給出確切答案的一個提問。這種提問通常包含一些自由變量和若干參數(shù)，但它們的值是沒有給定的。問題的描述必須給出：(1)所有變量和參數(shù)的一般性描述；(2)陳述問題答案(解)必須滿足的性質(zhì)。給問題的所有變量和參數(shù)指定具體的值，就得到該問題的一個“實例”。問題的規(guī)模：問題的規(guī)?？梢杂蓡栴}變量及有關(guān)參數(shù)的輸入長度表示，而這種輸入長度又由它的編碼方案所決定。編碼方案不同會影響一個問題的輸入長度，但它們的差異至多是多項式的。例如，在圖論中常用節(jié)點的數(shù)目n作為問題規(guī)模的一般表達方式；如果用邊的數(shù)目表示，最多是n2；如果邊權(quán)是實數(shù)，則問題輸入長度為32n2bits。在線性規(guī)劃問題中，一般用m+n表示問題的規(guī)模，其中n為變量個數(shù)，m為約束行數(shù)，其技術(shù)矩陣A

為主要輸入，其大小為m×(m+n)

。顯然，算法的難度和復(fù)雜度與問題規(guī)模有關(guān)。

算法復(fù)雜度(Complexityofalgorithm)算法的特征算法必有開始，表現(xiàn)為初始化，初始解的給定；算法必有結(jié)束，表現(xiàn)為必有判定是否停止的步驟；算法一般表現(xiàn)為通用步驟的反復(fù)循環(huán)，稱為迭代(iterative)。通用迭代的基本計算量往往是問題規(guī)模的一個函數(shù)；算法的迭代步數(shù)也是問題規(guī)模的函數(shù)。算法復(fù)雜度算法復(fù)雜度的兩種根本性的差別關(guān)于問題規(guī)模的多項式算法：P(n)，如n4,n3,n2–n等；關(guān)于問題規(guī)模的指數(shù)算法：E(n),如2n,n!,nn等；

算法復(fù)雜度(Complexityofalgorithm)指數(shù)算法

(壞算法)采用窮舉法搜索TSP的最優(yōu)解，其運算時間的估計式為：城市數(shù)(n)1015202130解的數(shù)量1.81441054.358910106.082310161.216510184.42091030運算時間－69.7s4y84.86y4.351014y多項式算法

(好算法)Prim算法i=1n1次比較，最多n1次賦值i=22(n2)次比較，最多2(n2)次賦值i=k

k(n

k)次比較，最多k(n

k)次賦值Dijkstra算法i=1n1次臨時標(biāo)記，永久標(biāo)記n1次比較和賦值i=2n2次臨時標(biāo)記，永久標(biāo)記n2次比較和賦值i=k

n

k

次臨時標(biāo)記，永久標(biāo)記n

k

次比較和賦值

算法復(fù)雜度(Complexityofalgorithm)指數(shù)算法

(壞算法)如果一類問題被證明只有指數(shù)算法，這類問題就被稱為難解的。多項式算法

(好算法)如果一類問題被證明有多項式算法，這類問題就被稱為非難解的。NP-完備問題一類問題目前找不到多項式算法，也沒有被證明只有指數(shù)算法，但它可以由一個已知的NP-完備問題多項式轉(zhuǎn)變過來，它就是NP-完備的。目前只有(隱)枚舉法可以保證找到最優(yōu)解；一般采用啟發(fā)式的近似算法求次最優(yōu)解。Prim算法的改進增加一個輔助記錄型數(shù)組，用以記錄當(dāng)前V

中各節(jié)點到V

的最小邊，minedge[i].cost記錄該邊的權(quán)值，minedge[i].vex記錄該邊V

中的頂點。若minedge[i].cost<0則表明i

點進入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=minedge[k].cost;{找到k，將k

加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{該算法復(fù)雜度約為5n(n-1)}

匹配問題(MatchingProblem)定義：圖中一組邊的集合，當(dāng)圖中的每個節(jié)點最多只與該集合中的一條邊相關(guān)聯(lián)，則該邊集就成為匹配。1、兩部圖的匹配問題圖中的節(jié)點可分為兩個集合，X,Y，X與Y

之間有邊相連，但X

內(nèi)部和Y

內(nèi)部無關(guān)聯(lián)邊，稱為兩部圖運輸問題實際上是兩部圖的最小費用最大流問題任務(wù)分配問題實際上是兩部圖的最小完全匹配問題2、非兩部圖的匹配問題(1)最大基數(shù)匹配(maximumcardinalitymatching)(2)最大權(quán)匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最優(yōu)分?jǐn)?shù)匹配(optimalfractionalmatching)兩部圖的最小完全匹配匈牙利算法任務(wù)分配問題的抽象就是兩部圖的最小完全匹配問題匈亞利算法(Hungarianmethod)由Kuhn教授提出，它實際上是主對偶算法的先驅(qū)匈亞利算法借助于效率矩陣和兩部圖來完成運算任務(wù)分配問題的效率矩陣對應(yīng)的是兩部圖的邊權(quán){cij}，對偶問題的解對應(yīng)的是每條邊的兩個端點{ai,bj}；對偶約束為ai＋bjcij匈亞利算法的實質(zhì)是通過構(gòu)造對偶問題的可行解，得到一個等值邊子圖，即所有ai,＋bj＝cij

的邊構(gòu)成的圖；然后在等值邊子圖上求最大基數(shù)匹配；當(dāng)?shù)玫皆瓎栴}的完全匹配，則算法結(jié)束對偶問題的可行解等值邊子圖滿足互補松弛定理求原問題的解(部分可行解)檢驗擴充等值邊子圖最大基數(shù)匹配最大基數(shù)匹配是基于交錯樹(匈牙利樹)的算法敞露點、根、交錯鏈、外點、內(nèi)點、增廣鏈尚未匹配的節(jié)點稱為敞露點以敞露點為根，由非匹配邊和匹配邊交替構(gòu)成的鏈稱為交錯鏈交錯鏈的根為外點，其后內(nèi)點與外點交替；外點是交錯鏈的生長點以內(nèi)點結(jié)束的交錯鏈稱為增廣鏈，因為反轉(zhuǎn)該鏈上各邊的匹配狀態(tài)可使匹配的邊數(shù)增加一條匈牙利算法步驟令所有ai＝0在效率矩陣中找每列最小值qj，令bj＝qj

，故i,j，滿足ai＋bjcij在滿足ai＋bj＝cij

的邊構(gòu)成的等值子圖中求最大基數(shù)匹配；若達到完全匹配則結(jié)束，否則到下一步對敞露點求每列的最小松弛量sj＝mini*{ci*j－ai*－bj}求最大增廣量S＝0.5minj{sj}增廣等值子圖，j，bj＝bj＋S

i*(敞露點)，ai*＝ai*＋S

；

i(非敞露點)，ai＝ai－S返回到第3

步匈牙利算法舉例**匈牙利算法舉例*匈牙利算法舉例

任務(wù)分配問題、匹配問題和TSP的關(guān)系三個問題都有一個nn

正權(quán)值的邊權(quán)矩陣三個問題的解都可以用代數(shù)置換(permutation)表示i1,i2,i3,i4,i5是1,2,3,4,5的任一排列，表示元素位置的交換輪換，全輪換，對換TSP的解必須是一個全輪換任務(wù)分配問題的解可以是任一個置換匹配的解必須是n/2個對換任務(wù)分配問題是匹配問題的松弛問題

6.7

選址問題使所選地址到最遠(yuǎn)的服務(wù)對象距離盡可能小——中心點使所選地址到各服務(wù)對象的總距離最小——中位點有時間限制的多用中心點，如鄉(xiāng)郵局總資源約束的多用中位點，如電話交換局

6.7.1各點之間的距離節(jié)點到節(jié)點間的最短距離，稱為節(jié)點—節(jié)點距離邊上某點到節(jié)點的最短距離，稱為點—節(jié)點距離節(jié)點到某邊上最遠(yuǎn)一點的距離，稱為節(jié)點—邊距離邊上一點到另一邊上最遠(yuǎn)點的距離，稱為點—邊距離1、邊上某點到節(jié)點的最短距離dij

代表vi

與vj

間的最短距離，ars

代表邊(r