1、From clown studio建模十大經典算法1、蒙特卡羅算法。該算法又稱隨機性模擬算法，足通過計算機仿真來解決問題的算法，同時通過模擬町以 來檢驗自己模型的正確性。2、數據擬合、參數估計、插值等數據處理算法。比賽中通常會遇到人最的數據需要處理，而處理數據的關鍵就在于這些算法，通常使用Matlab作為工幾。3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題。建模競賽人多數問題屬于最優化問題，很多時候這些問題町以用數學規劃算法米描述， 通常使用Lindo、Lingo、MATLAB軟件實現。4、圖論算法。這類算法町以分為很多種，包括故短路、網絡流、二分圖等算法，涉及到圖論的問題町 以用這些

2、方法解決，需要認真準備。5、動態規劃、回溯搜索、分治算法、分支定界等計算機算法。這些算法是算法設計中比較常用的方法，很多場合町以用到竟賽中。6、最優化理論的三大非經典算法：模擬退火法、神經網絡、遺傳算法。這些問題是用來解決一些較困難的故優化問題的算法，對于有些問題非常有幫助，但是 算敢的實現比較困難，需慎覓使用。7、網格算法和窮舉法。網格算法和窮舉法都是眾力搜索/優點的算法，在很多竟賽題中仃應用，當重點討論模 型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工貝。8、一些連續離散化方法。很多問題都是實際來的，數據町以是連續的，而計算機只認的是離散的數據，因此將英 離散

3、化后進行差分代替微分、求和代替積分等思想是非常乘要的。9、數值分析算法。如果在比賽中釆用高級語言進行編程的話，那一些數值分析中常用的算法比如方程組求 解、矩陣運算、函數枳分等算法就需要額外編寫庫歯數進行調用。10、圖象處理算法。賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理。歷年全國數學建模試題及解法賽題解法93A非線性交調的頻率設計擬合、規劃93B足球隊排名圖論、層次分析、整數規劃94A逢山開路圖論、插值、動態規劃94B鎖只裝箱問題圖論、組合數學95A飛行管理問題非線性規劃、線性規劃95B大車

4、與冶煉爐的作業調度動態規劃、排隊論、圖論96A最優捕魚策略微分方程、優化96B節水洗衣機非線性規劃97A冬件的參數設計非線性規劃97B截斷切割的最優排列隨機模擬、圖論98A類投資組合問題多目標優化、非線性規劃98B災情巡視的最佳路線圖論、組合優化99A自動化乍床管理隨機優化、計算機模擬99B鉆井布局0-1規劃、圖論00ADNA序列分類模式識別、Fishei-判別、人工神經網絡00B鋼管訂購和運輸組合優化、運輸問題01A血管三維巫建曲線擬合、曲面巫建01B公交乍調度問題多冃標規劃02A車燈線光源的優化非線性規劃02B彩栗問題單目標決策03ASARS的傳播微分方程、差分方程03B露天礦生產的車輛安

5、排整數規劃、運輸問題04A奧運會臨時超市網點設計統計分析、數據處理、優化04B電力市場的輸電阻塞管理數據擬合、優化05A氏江水質的評價和預測預測評價、數據處理05B DVD在線租賃隨機規劃、整數規劃06A出版資源配置06B艾滋病療法的評價及療效的預測07A中國人口增長預測07B乘公交，看奧運多目標規劃 數據處理 圖論08A數碼相機定位08B高等教育學費標準探討09A制動器試驗臺的控制方法分析09B眼科病床的合理安排動態規劃10A10B賽題發展的特點：1對選F的計算機能力提出了更高的要求：賽題的解決依賴計算機，題目的數據較兔，于工 計算不能完成，如03B,某些問題需要使用計算機軟件，01A。問題

6、的數據讀取需要計算機 技術，如00A （大數據），01A （圖象數據，圖象處理的方法獲得），04A （數據庫數據，數 據庫方法，統計軟件包）。計算機模擬和以算法形式給出最終結果。2賽題的開放性增人解法的女樣性，一道賽題可用多種解法。開放性還衷現在對模型假設和 對數據處理上。3試題向大規模數據處理方向發展4求解算法和各類現代算法的融合從歷年競賽題來看，常用的方法：線性規劃整數規劃非線性規劃動態規劃層次分析法圖論方法擬合方法插值方法隨機方法微分方程方法各種算法的詳解一、蒙特卡洛算法1、含義的理解以概率和統計理論方法為基礎的一種計算方法。也稱統計模擬方法，是指使用隨機數（或更 常見的偽隨機數）來解決

7、很多計算問題的方法，它是將所求解的問題同一定的概率模型相 聯系，用計算機實現統計模擬或抽樣，以獲得問題的近似解。2、算法實例（有很多相似的例題，包括平行線等）在數值枳分法中，利用求單位圓的1/4的面積來求得P1/4從而得到Pl。單位圓的1/4面枳是 一個扇形，它是邊長為1單位正方形的一部分。只要能求出扇形面積S1在正方形而積S中 占的比例K=S1/S就立即能得到S1,從而得到P1的值。怎樣求出扇形面積在正方形面積中 占的比例K呢？ 一個辦法是在正方形中隨機投入很多點，使所投的點落在正方形中每一個 位置的機會相等看其中有多少個點落在扇形內。將落在扇形內的點數m與所投點的總數n的比m/n作為k的近

8、似值。P落在扇形內的充要條件足lC + y<l .求Pio已知：K= , K« , s=l, sl= sn4程序：(該算法口J以修改后用Mathematica計算或Matlab)/*利用蒙特卡洛算法近似求圓周率Pi*/*程序使用：VC4H5.0*/#indude<stdio.h>#indude<math.h>#include<stdlib.h>#define COUNT 800嚴循環取樣次數，每次取樣范圍依次變大*/void mainOdouble x,y;int num=0;int i;for(i=0 ;i VCOUNT i 卄)x=ran

9、dO*l 0/RAND_MAX;/*RAND_MAX=32767,包含在vstdio.h>中水/ y=randO*l 0/RAND_MAX;if(x*x+y*y)<=l)mmi-H-; /*統計落在四分之一圓之內的點數*7printf(nPi 值等于：%firnum*4.0/COUNT);結果：測試6次的結果顯示：循壞取樣次數求得的P1值8003 085CC080003.110C00800003.1352008000003 13915080000003 141393From clown studio800000003 141321可以看出:隨看點數的增加，求得的Pl值漸漸接近真實值

10、。如果加入程序：si*and（time（NULL）,同時循環取樣次數一定，讓取樣結果隨時間變化，當 取樣次數為80000000時，可得6次的結果顯示：3 1412903.141400 3 1412683.141484 3 141358 3 1414623、應用的范國蒙特卡羅方法在金融工程學，宏觀經濟學，計算物理學（如粒子輸運計算、最子熱力學計算、空氣動力學計算）等領域應用廣泛。4、參考書籍1 蒙特卡羅方法及其在粒子輸運問題中的應用2蒙特卡羅方法引論二、數據擬合、參數估計、插值等數據處理算法（1）數據擬合在Nfathematica中，用Fit對數據進行最小二乘擬合：Fit data,fims,v

11、ars在Matlab中，工具箱（toolboxes）中有曲線擬合工具（curve Fitting）* 實例：2010年蘇北賽B題 溫室中的綠色生態臭氧病蟲害防治中關于中華稻蝗密度與水稻減產 率之間的關系町以通過數據擬合來觀察（簡單舉例，沒有考慮全部數據）數據:密度（頭/m）310203040減產率（%）2.412. 916. 320. 126. 8程序(Mathematica )：data=(3,2.4,(10,12.9,(20,16.3),30,20.1,(40,26.8; al=Fitdata,1,x,x八2,x八3,xShowListPlotdata,Filling->Axis,P

12、lot al, x,0,60 結果：-3.68428+2.38529 x-0.0934637 x=+0.00132433 x3（2）參數估計（參考書：概率論與數理統計） 參數估計為統計推斷的基本問題，分為點估計和區間估計。點估計：矩估計法x連續型隨機變最，概率密度f（x；q,q,q）x為離散型隨機變量分布律px=x= p（%q,q,久）q，2，,q為待估參數，是來自x的樣本，假設總體x的前k階矩存在，為（X連續型）或” = E（X】）=工£p（x；q,，,久）（X離散型）1 =1,2,k （其中&是xuj能取 JCERy值的范國）。一般來說，它們是q,a,q的函數。基于樣本矩

13、a =依概率收斂1】臺于相應的總體矩“（l=l,2,k）,樣本矩的連續函數依概率收斂于相應的總體矩的連續函 數，我們就用樣本矩作為相應的總體矩的估計量，而以樣本矩的連續函數作為相應的總體矩 的連續函數的估計量。這種估計方法成為矩估計法。最大似然估計法X連續型隨機變量 似然函數L（9） = L（x1,x2,.,xn；） = nf（；）其中1=1 1=1是來自X的樣本XpX"九的聯合密度。x為離散型隨機變最似然函數1/0 = 1/齊,馮,£；0 =冇卩（;0,6®其中fjp區；。）是來自X的樣本務仝2，£的聯合分布律。 1=1若 L（0 = 1/逅，圣,，斗

14、；6 = 111宓1/齊心,0E則稱&.*,£）為8的最人似然估計值，稱/（XpX?,£）為0的最人似然估計量。這樣，確定最人似然估計最的問題就歸結為微分學中的求垠人值的問題了。估計量的評選標準為：（丄）無偏性（2）有效性（3）相合性區間估計：對于一個未知最，人們在測最或計算時，常不以得到近似值為滿足，還需要估計誤差，即要 求知道近似值的精確程度（亦即所求真值所在的范I韋I）。這樣的范I韋I常以區間的形式給出， 同時還給出此區間包含參數真值的對信度，這種形式的估計稱為區間估計，這樣的區間即所 謂冒信區間。正態總體均值、方差的置信區間與單側置信限（置信水平為1-

15、71;）一個正態總體未知參數英他參數樞軸量的分布置信區間b2己知z = £dn（oj） cr! yjn（唇 Z“）A未知1 =t(n-l)S/Vn-s(X 土za/2 (n 一 1)CT未知(n-l)S2(n-l)S2zt2(Ta(T另外還包括兩個正態總體的情況，其他區間估計：(0-1)分布參數的區間估計(3) 插值1、含義的理解在離散數據的基礎匕補插連續曲數，使得這條連續曲線通過全部給定的離散數據點。插值是 離散函數逼近的巫要方法，利用它叮通過函數在有限個點處的取值狀況，估算出函數在其他 點處的近似值(與擬合的不同點在于擬合的函數不需通過每一個離散點)。插值問題的提法是：假定區間a

16、, b上的實值函數f (x)在該區間上n+1個互不相 同點x0, xl . xn處的值是fx0,f (xn),要求估算f (x)在a, b中某點的值。 其做法是：在事先選定的一個由簡單函數構成的有n+1個參數CO, Cl, .Cn的函 數類(CO, Cl, .Cn)中求出滿足條件 P (xi) =f (xi) (1 = 0, 1. . n)的函數 P(x), 并以P0作為f0的估值。此處f (x)稱為被插值旳數，x0, xl, .xn稱為插值結(節) 點，(CO, Cl, .Cn)稱為插值函數類，上面等式稱為插值條件，(CO, . Cn)中 滿足上式的函數稱為插值函數，R (x) = f (x

17、) -P (x)稱為插值余項。當估算點 屬于包含x0, xl. xn的最小閉區間時，相應的插值稱為內插，否則稱為外插。2、基本類型多項式插值在般插值問題中，若選取為n次多項式類，由插值條件可以唯一確定一個n次插 值多項式滿足上述條件。拉恪朗口插值和牛頓插值都屈于多項式插值。拉格朗日插值：設連續函數y = f (x)在a,b上對給定n+1個不同結點：,檢分別取函數值,%,其中 乂=片(兀)i = 0,1 v n(1)試構造一個次數不超過n的插值多項式匕(x) = % + aX+gx2 + + ©疋(2)使之滿足條件匕(兀)i = 0,1,-2-,n(3)構造n次多項式l'x)

18、k = 0,lv n 使(4)由 只（兀）=Z yA） =y： i = o, i ,2,n k=i即pn（x）滿足插值條件，于是問題歸結為具體求出基本插值實項式h（x）。根拯（4）式h（x）以外所有的節點都是lk（x）的根，因此令h (x) = 2(x- Xq)(x-齊)(x- Vi)(x-觀乜)(x xj= 2fJ(x-xJ) j=0 存k又由lk(x)=l,得:（兀一毛）（怎氏）-忑1）（彖兀也）（ xj所以旳(X)= (Xf( -況)(忑-xi) - Vi)( - +1) ( - )代入（5）得拉格朗日插值多項式為:W = S1k(x)yk=Sk=0k=OYk牛頓描值：（拉格朗日插值的峽

19、點）拉格朗口插值公式的形式雖然冇一定的規律，但是肖增加 一個節點時，不僅要增加項數，而且以前各項也必須覓新全部計算，不能利用己有的 結果。為克服這一缺點，我們取用另一種形式一一牛頓插值公式。牛頓插值公式中用到了差商。一般稱：差商町列表計算：XIyi一階差商二階差商三階差商xOf(xO)X1f(xl)f xO, xlxZf (xZ)f xl, xZf xO, xl, x2x3f(x3)f x2, x3f xl, x2» x3f xO, xl, x2, x3為f（x）在Xg,Xp,處的n階差商。四階差商x4 f (x4) f x3, x4 f x2, x3, x4 f xlt x2t x

20、3, x4 f xOm> x4由差商定義可知E(x)= f(Xo)+坷(X-Xjj)+ f%,兀，叩(X-Xjj)(X-齊)由差商定義町求得f(X)= f (Xq) +(X- Xq) fXo，xJ+(X-Xq)(X-齊)口毛,齊,卷+ +(x_x；j)(x_ 齊)(x_ 心i)fXo，»i，兀+ (X-Xo)(X-Xi).(X-) 口耳忌，齊,，兀J記Nn(x) = f (*)+ (x- Xq) fXQ,齊+ (x- Xq)(X-舌)f%“+ -+(x-x0)(x-).(x-_1)fx0,x1,.,x11%( x> g oX)(X 1 X) K x)fl %jX ,沖則

21、(x) = Nn(x) + Rh(x)其中Nn(x)稱為n次牛頓插值多項式，RJx)是截斷誤差。最終我們町以證明Nn(X)滿足插值條件Nn() = §(兀)i = 0,1,2,.,n因此有叫(£)=(X牛頓插值公式的優點是：當增加一個節點時，只要再增加一項就行了，即有遞推式當然，與拉格朗口插值相比它還有節省運算次數的優點(尤其是節省乘法運算次數)。 分段插值與樣條插值為了避免高次插值町能出現的大幅度波動現象，在實際應用中通常采用分段低次插值 來提離近似程度埃爾米特插值許多實際插值問題中，為使插值兩數能更好地和原來的兩數更合，不但要求二者在節 點上函數值相等，而且還要求柑切，

22、對應的導數值也相等，其至要求高階導數也相等。 這類插值稱作切觸插值，或埃爾米特(Hermite)插值。滿足這種要求的插值多項式就是 埃爾米特插值多項式三角函數插值當被插曲數是以2兀為周期的函數時，通常用n階三角多項式作為插值函數，并通過 高斯三角插值表出。三、線性規劃、整數規劃.多元規劃、二次規劃(1) 線性規劃1、含義的理解線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔 助人們進行科學管理的一種數學方法研究線性約束條件下線性目標函數的極值問題的數學 理論和方法，英文縮寫LP。它是運籌學的一個重要分支。在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟效果

23、是人們不可缺少的要求, 而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，使用新設 $和新型原材料二是生產組織與計劃的改進，即介理安排人力物力資源線性規劃所研究的 是：在一定條件F，合理安排人力物力等資源，使經濟效果達到最好一般地，求線性目標 函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題。滿足線性約束條 件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變童、約束條件、目標函 數是線性規劃的三要素。2、線性規劃問題的數學模型的-般形式和模型建立（1）列出約束條件及目標函數（2）畫出約束條件所表示的可行域（3）在可行域內求目 標函數的最優解及最優值（實

24、際問題中建立數學模型一般有以下三個步驟：根據影響所要達 到目的的因素找到決策變最：2由決策變量和所在達到目的之間的函數關系確定目標函數； 3由決策變量所受的限制條件確定決策變量所要滿足的約束條件。） 所建立的數學模型具有以下特點：（1）、每個模型都有若干個決策變量（xl,x2,x3，xn）,其中n為決策變量個數。決策變 量的一組值表示一種方案，同時決策變量一般是非負的。（2）、目標函數是決策變屋的線性函數，根據具體問題可以是最人化（max）或最小化（min）, 二者統稱為最優化（opt）。（3）、約束條件也是決策變量的線性函數。當我們得到的數學模型的目標函數為線性函數, 約束條件為線性等式或不

25、等式時稱此數學模型為線性規劃模型。3、實例生產計劃問題問題：某企業要在計劃期內安排生產甲、乙兩種產品，這個企業現有的生產資料是：設備18臺時, 原材料A : 4噸，原材料B： 12噸；已知單位產品所需消耗生產資料及利潤如卜表。問 應如何確定生產計劃使企業獲利最多？品資源'、甲乙資源量設備/臺時318原料A/噸104原料B/噸012單位嵐利/萬元55設xl為甲產品分配的設備臺數，為乙產品分配的臺數。則 條件限制為：3*xl+2*x2<18 l*xl+0*x2<4 0*xl+2*x2<12 xl>0, x2>0 求 max z=3*xl+5*x2用lingo編

26、程，程序如卜：max=3*xl+5*x2;3*xl+2*x2<=l &xlv=4,x2<=6,xl>=0,x2>=0,結果為：Global optimal solution foundObjective value:36. 00000Total solver iterations:1VariableValue2.0000006.000000Reduced Cost0.000000D.000000XIX2RowSlack.or SurplusDual Price136.000001.000000o0.0000001.0000D03o0000000.0000D040

27、.0000003.0000005o0000000.00000066.0000000.0000D0即在xl=2» 乂2=6時企業獲利最多，為36萬元。4、線性規劃的應用在企業的各項管理活動中，例如計劃、生產、運輸、技術等問題,線性規劃是指從各種限制條 件的組合中，選擇出放為介理的計算方法,建立線性規劃模型從而求得最佳結果廣泛應用于 軍爭作戰、經濟分析、經營管理和工程技術等方面。為合理地利用有限的人力、物力、財力 等資源作出的最優決策，提供科學的依據。（2）整數規劃一類要求問題的解中的全部或一部分變最為整數的數學規劃。從約束條件的構成又町細分為 線性，二次和非線性的整數規劃。在線性規劃問

28、題中，有些域優解町能是分數或小數,但對于某些具體問題，常要求某些變量的解必須足整數。例如，當變量代表的是機器的臺 數，工作的人數或裝貨的車數等。為了滿足整數的要求，初看起來似乎只要把已得的非整 數解舍入化整就町以了。實際上化整后的數不見得是可行解和最優解，所以應該有特殊的 方法來求解整數規劃。在整數規劃中，如果所仃變量都限制為整數，則稱為純整數規劃； 如果僅一部分變量限制為盛數，則稱為混介整數規劃。整數規劃的一種特殊情形是01規劃, 它的變數僅限于0或1。不同于線性規劃問題，整數和01規劃問題至今尚未找到一般的多 項式解法。組合鍛優化通常都可表述為整數規劃問題。兩者都是在有限個町供選擇的方案中

29、，尋找滿 足一定約束的最好方案。有許多典型的問題反映整數規劃的廣泛巧景。例如，背袋（或裝載） 問題、固定費用問題、和睦探險隊問題（組合學的對集問題）、有效探險隊問題（組合學的 覆孟問題）、旅行推銷員問題，車輛路徑問題等。因此整數規劃的應用范圉也是極其廣泛的。 它不僅在工業和工程設計和科學研究方面有許多應用，而且在計算機設計、系統可靠性、編 碼和經濟分析等方面也有新的應用。整數規劃是從1958年由RE戈莫里提出割平面法之后形成獨立分支的。解整數規劃最典 型的做法是逐步生成一個相關的問題，稱它是原問題的衍生問題。對每個衍生問題又伴隨 一個比它更易于求解的松弛問題（衍生問題稱為松弛問題的源問題）。通

30、過松地問題的解來 確定它的源問題的歸宿，即源問題應被舍棄，還是再生成一個或多個它本身的衍生問題來 替代它。隨即再選擇一個尚未被舍棄的或替代的原問題的衍生問題，車復以上步驟直至不 再剩令未解決的衍生問題為止。目前比較成功又流行的方法是分枝定界法和割平面法，它 們都是在上述框架下形成的。0-1規劃在整數規劃中占有更要地位，一方面因為許多實際問題，例如指派問題、選地問題、 送貨問題都町歸結為此類規劃，另一方面任何右界變最的整數規劃都與0規劃等價，用 0-1規劃方法還町以把多種非線性規劃問題表示成整數規劃問題，所以不少人致力丁這個 方向的研究。求解01規劃的常用方法是分枝定界法，對齊種特殊問題還冇一些

31、特殊方法， 例如求解指派問題用匈牙利方法就比較方便。（4）二次規劃二次規劃是非線形規劃中一類特殊的數學規劃問題，它的解是町以通過求解得到的。通常通 過解英庫恩一塔克條件（KT條件），獲取一個KT條件的解稱為KT對，英中與原問題的變 最對應的部分稱為KT點。二次觀劃分為凸二次規劃與非凸二次規劃，前者的KT點便是其全局極小值點，而后者的 KT點町能連局部極小值點都不是。若它的目標函數是二次函數，則約束條件是線性的。由 于求解二次規劃的方法很多，所以較為復雜：英較簡便易行的足沃爾夫法，它是依據庫恩 塔克條件，在線性規劃單純形法的基礎卜.加以修正而成的。此外還有萊姆基法、畢爾法、 凱勒法等。From

32、clown studioFrom clown studioU!圖論: （參考資料：建模教程（圖與網絡）From clown studio（1）含義的理解圖論是專門研究圖的理論的一門數學分支，屬于離散數學范躊，與運籌學有交叉。圖論中常用點和點之間的線所構成的圖，反映實際生產和生活中的某些特定對象之間的特定 關系。一般來說，通常用點表示研究對象、用點與點之間的線表示研究對彖之間的特定關系。在一般情況卜，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之 間的關系，顯的并不重要。因此，圖論中的圖與幾何圖，工程圖等本質上是不同的。（2）歷史（包括應用范闈）它有200多年歷史，大體可劃分為三

33、個階段：第一階段是從十八世紀中葉到十九世紀中葉，處于萌芽階段，多數問題閑游戲而產生，故有 代表性的工作是所謂的Euler七橋問題，即一筆畫問題。第二階段是從十九世紀中葉到二十世紀中葉，這時，圖論問題大最出現，如Hamilton問題, 地圖染色的四色問題以及可平面性問題等，這時，也出現用圖解決實際問題，如Cayley把 樹應用于化學領域，Kirchhoff用樹去研究電網絡等.第三階段是二十世紀中葉以后，由生產管理、軍班、交通、運輸、計算機網絡等方面提出實 際問題，以及人型計算機使人規模問題的求解成為可能，特別是以Ford和Fulkerson建立 的網絡流理論，與線性規劃、動態規劃等優化理論和方法

34、柑互滲透，促進了圖論対實際問題 的應用。算法重要的算法1、求有向圖的強連通分支(Strongerst Connected Component)(1) Kos ar a j u 算法(2) Gabow 算法(3) Tarjan 算法2、求最小生成樹(Minimal Spanning Trees)(1) Kruskal 算法(2) Prim 算法3、最小樹形圖(1)朱水津劉振宏算法4、最短路徑問題(1) SSSP (Single-source Shortest Paths)©Dijkstra 算法BelIman-Ford 算法(SPFA 算法)(2) APSP(All-pairs Sho

35、rtest Paths) Floyd-Warshall 算法 Johnson算法5、網絡流問題(1) 最人網絡流 增廣路算法1 .Ford-Fulkerson 篦法2. Edmonds-Karp 算法3加短路徑增殖EK-2 (MPLA)4.Dinic 預流推進算法(2) 最小費用流6、圖匹配問題(1) 匈牙利算法(2) Hopcroft Karp 算法(3) KuhnMunkres 算法(4) Edmonds' blossom_contraction 算法(有關資料網址：http: www. nocow. cn/index, php/%E5%9B%BE%E8%AE%BA)(1)基本概念

36、無向圖一個無向圖(undirected graph) G是由一個非空有限集合V(G)和V(G)中某些元素的 無序對集合E(G)構成的二元組，記為G=(V(G),E(G)。其中V(G) = %“,稱 為圖G的頂點集(vertex set )或節點集(node set ) , V(G)中的每一個元素 出(i = 12,口)稱為該圖的個頂點(vertex)或廿點(node )； E(G) = 勺冷,稱 為圖G的邊集(edge set), E(G)中的每一個元素q (即V(G)中某兩個元素乂,耳的無序From clown studio對)記為豈= (V"Vj)或ek =vy =Vj2 (k

37、= 12,m),被稱為該圖的一條從v】到Vj的 邊(edge)。當邊時，稱V,V)為邊耳的端點，并稱V：與V相鄰(adjacent)：邊乞稱為與頂點V,Vj關聯(incident )o如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖G中 相鄰。邊上賦權的無向圖稱為賦權無向圖或無向網絡(undirected network)。我們對圖和網絡不 作嚴格區分，因為任何圖總是可以賦權的有向圖一個有向圖(directed graph或digraph) G是由一個非空有限集合V和V中某些元素的有序 對集合A構成的二元組，記為G=(V,丹。其中V = %,%,*稱為圖G的頂點集或節點集， V中的每一個元素v

38、】(i =稱為該圖的一個頂點或節點；A=a1,a2,- -,am稱為圖G的弧集(arc set), A中的每一個元素兀(即V中某兩個元素vx,Vj的有序對)記為孔=(VpVj)或孔=vy (k = 12,n)，被稱為該圖的一條從y到v的弧(arc)a肖弧ak = 時，稱V為疋的尾(tail),耳為a的頭(head),并稱弧a*為V】的出弧(outgoing arc), 為V)的入弧 (incoming arc)。對應于每個有向圖D,可以在相同頂點集上作一個圖G,使得對于D的每條弧，G有一條 有相同端點的邊與之相對應。這個圖稱為D的基礎圖。反之，給定任意圖G,對于它的每 個邊，給其端點指定一個順

39、序，從而確定一條弧，由此得到一個有向圖，這樣的有向圖稱 為G的一個定向圖。完全圖、二分圖每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(complete graph)o n個頂點的完全圖 記為Kn。若V (G)=XUY, XnY=<D, |X|Y|hO (這里| X |表示集合X中的元素個數)，X中無相鄰頂點對,Y中亦然,則稱G為二分圖(bipartitegraph)；特別地,若VxwXNywY,則取wE(G),則稱G為完全二分圖，記成片鞏曲。最短路、網絡流、二分圖1、最短路問題(SPPshortest patli problem)最短路徑問題足圖論中十分幣.要的最優化問題之一，它作為

40、一個經常被用到的基本工只，町 以解決生產實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優化問題。若網絡中的每條邊都有一個數值（長度、成本、時間等），則找出兩節點（通常是源節點 和阱節點）之間總權和最小的路徑就是最短路問題。最短路問題是網絡理論解決的典 型問題之一，可用來解決管路鋪設、線路安裝、廠區布局和設備更新等實際問題。最 短路問題，我們通常歸屬為三類單源瑕短路徑問題包扌舌起點的最短路徑問題，確定終點的最短路徑問題（與確定起點的問題相反，該問 題是已知終結結點，求授短路徑的問題。在無向圖中該問題與確定起點的問題完全相 同，在有向圖中該問題等同

41、于把所有路徑方向反轉的確定起點的問題。）確定起點終點的最短路徑問題即己知起點和終點，求兩點之間的最短路徑。全局最短路徑問題求圖中所有的最短路徑。算法只要采用Floyed-Warshall算法（這是北洛伊德利用動態 規劃（dynamic programming）的原理設計的一個高效算法）。Floyed-Warshall算法用來找出每對點之間的繪短距離。它需要用鄰接矩陣來儲存邊，這個 算法通過考世最佳子路徑來得到瑕佳路徑。注意單獨一條邊的路徑也不一定是最佳路徑。從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有 邊相連。對于每一對頂點u和v,看看是否存在一個頂點w使得

42、從u到w再到v比己知的路徑 更短。如果是更新它。不可思議的是，只要按排適半，就能得到結果。最短路算法：Dijkstra 算法Dijksti'a 復雜度是 o（nt）,如果用 binary heap 優化可以達到 o（E+N）iogN），用 fibonacci heap可以優化到o（NiogN+E）其基本思想是釆用貪心法，對于每個節點vi,維護估計敲短路長度敲人值，每次取出一個 使得該估計值最小的t,并采用與t相連的邊對英余點的估計值進行更新，更新后不再考慮 to在此過程中，估計值單調遞減，所以町以得到確切的最短路。Dijkstra 程序：:void DijkstraO ；for(int

43、 i=l;i<=n;i+)；disi = mapl i;II:int k;:for(int i=l;i<n;i+)int tmin = maxint;:for(int j=l:j<=n;j+):if( !usedj && tmin > disj )；tmin 二 dis j;:k = j;: ；usedk = 1;:for(int j=l;j<=n;j+) if ( disk + mapk j < disj):disj = disk + mapk j:I printfdis n);:II:/*求1到N的最短路,disij表示第i個點到第一個點

44、的最短路By Ping*/II«»OB«還有其他算法：FloydWarshal 1 算法Be liman "Ford 算法Johnson 算法實例：某公司在六個城市q,c2，-,c6中有分公司，從c,到勺的直接航程票價記在下述矩陣的(i,j)位宣上。(s表示無直接航路)，請幫助該公司設計一張城市q到其它城市間的票價最便宜的路線圖。050co4025105001520CO25CO1501020CO4020100102525CO20100551025CO25550用矩陣玄如“(n為頂點個數)存放備邊權的鄰接矩陣，行向最pb、index、index.d分別用來

45、存放P標號信息、標號頂點順序.標號頂點索引、最短通路的值。其中分最pb(i) = ?為第訂貞點己標號當第訂頁點未標號iiidex2(i)存放始點到第i點蟻短通路中第i頂點前一頂點的序號;d(i)存放由始點到第i點最短通路的值。求第一個城市到其它城市的蟻短路徑的Matlab程序如K：clear;clc;M=10000;a(l, :) = 0,50,M, 40,25,10;a (2,:) = zeros(1<2)r15r20rMr25;a(3r:) = zeros(lz 3)r10f20rM;a(4,:) = zeros(lz 4)F10r25;a(5r:) = zeros (1,5),55

46、;a(6r:)=zeros (1,6);a=a+a1;pb(1:length(a)=0;pb(1)=1;indexl=l;index2=ones(lrlength(a); d(1:length(a)=M;d(1)=0;temp=l;while sum(pb)<iength (a)tb=find(pb=0);d (tb)=min (d (tb)# d(temp)+a(temp,tb);tmpb=find(d(tb)=min(d(tb);temp=tb(tmpb(1);pb (temp)=1;indexl=indexlf temp;index=indexl (find(d (indexl)=

47、d (temp)-a(temp,indexl); if length (index)>=2index=index(1);endindexZ (temp)=index;endd, indexlrindex?運行結果為：d =03545352510indexl =1 6543index?=1 65611即:d （最短通路的值）03545352510indexl （標號頂點順序）16543index?（標號頂點索引）1656112、網絡流（1）含義的理解網絡流（network flows）是圖論中的一種理論與方法，研究網絡上的一類址優化問題。（2）歷史及應用1955年，T. E.哈里斯在研究鐵

48、路最大通量時首先提出在一個給定的網絡上尋求兩點間最 人運輸量的問題。1956年，L. R.福特和D.R.常爾克森等人給出了解決這類問題的算法， 從而建立了網絡流理論。所謂網絡或容屋網絡指的是一個連通的賦權有向圖D= （V、E、C）, 其中V是該圖的頂點集，E是有向邊（即弧）集，C是弧上的容量。此外頂點集中包括一個起 點和一個終點。網絡上的流就是由起點流向終點的可行流，這是定義在網絡上的非負函數, 它一方而受到容量的限制，另一方而除去起點和終點以外，在所有中途點要求保持流入量和 流出量是平衡的。最人流理論是由福特和富爾克森于1956年創立的，他們指出最人流的流值等于繪小割（截 集）的容屋這個重要

49、的事實，并根據這-原理設計了用標號法求最人流的方法，后來又宿人 加以改進，使得求解最人流的方法更加豐富和完善。最人流問題的研究密切了圖論和運籌 學，特別是與線性規劃的聯系，開辟了圖論應用的新途徑。最人流問題僅注意網絡流的流通能力，沒有考慮流通的費用。實際上費用內素是很重要的。 例如在交通運輸問題中，往往要求在完成運輸任務的前提F，尋求一個使總運輸費用般省的 運輸方案，這就是最小費用流問題。如果只考慮單位貨物的運輸費用，那么這個問題就變成 最短路問題。由此町見，最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成 功方法。最小費用流（或繪小費用最人流）問題，町以交替使用求解最人流和址短路兩

50、種方 法，通過迭代得到解決。目前網絡流的理論和應用在不斷發展，出現了具有熠益的流、多終端流、毛商品流以及網絡 流的分解與合成等新課題。網絡流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、 設備更新以及計算機輔助設計等眾多領域。（3）算法的實現Edmonds _Karp 算法建立在Ford-Fulkerson方法上的增廣路算法，與一般的Ford-Fulkerson算法不 同的是，它用廣度搜索實現對增廣路的尋找.以下為代碼：int n;long int c128 128:long maxflow int s, int tint p, q, queue ., u, v, pre 128;long

51、 int flow, aug;flow = 0;while truememset pre, 1, sizeof pre 丨；for(queue p = q = _ = s; p <= q; p+u = queue p ;for(v = 0; (v < n) && (pre t) < 0; v+) if (c u v > 0) && (prev < 0)pre v一 = u; queue +q= v;if pre t >= ： breakif (pre t < 0)breakaug = OxTfff;v = u , u=p

52、re ufor u = pre v 二 t ; v if c u v < aug aug = c u_ V-;for u = pre v 二 t ; vcuv -= aug; c v u += aug;flow += aug;return flow:3、二分圖(1) 含義的理解二分圖又稱作二部圖，是圖論中的一種特殊模型。設G=(V,E)是一個無向圖，如果頂點V 可分割為兩個互不相交的子集(A,B),并且圖中的每條邊(I, j)所關聯的兩個頂點1和j分 別屬于這兩個不同的頂點集(iinAjinB),則稱圖G為一個二分圖。2、相關應用作為種數學模型，二分用途是十分有用的，許多問題可以用它來刻

53、劃。例如“資源匹配”、 “工作安排”、“人員擇偶”等等。而這就需要考慮匹配問題。匹配：給定一個二分圖G,在G的一個子圖M中，M的邊集中的任意兩條邊都不依 附于同一個頂點，則稱M是一個匹配。而二分圖最人匹配可以用最人流或者匈牙利算法。最大流在網絡流中有介紹。匈牙利算法為：(資料：百度百科)匈牙利算法是由匈牙利數學家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理（此定理使用于組合問題中。二部圖G中的兩部分頂點組成的集介分別為X, Y, Z,=X1, X2, X3.X4,Xm , Y=yl,y2, y3, y4 yn,G 中有一組無公共點的邊，一端恰好為組成X的點的充分必要條

54、件足：X中的任意k個點至少與Y中的k個點相鄰.（l<k<m）中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增 廣路徑，它是一種用増廣路徑求二分圖最大匹配的算法。算法的思路：不停的找增廣軌，并增加匹配的個數，增廣軌顧名思義是指一條町以使匹配數變多的路 徑，在匹配問題中,增廣軌的表現形式是一條”交錯軌，也就是說這條由圖的邊組成的路 徑，它的第一條邊是冃前還沒有參與匹配的，第二條邊參與了匹配,第三條邊沒有最后 一條邊沒有參與匹配，并且始點和終點還沒有被選擇過這樣交錯進行，顯然他有奇數 條邊那么對于這樣一條路徑，我們可以將第一條邊改為己匹配，第二條邊改為未匹配 以此類推也就是將所冇的邊進行反色"，容易發現這樣修改以后，匹配仍然是介法的, 但是匹配數增加了一對另外，單獨的一條連接兩個未匹配點的邊顯然也是交錯軌可 以證明，當不能再找到增廣軌時,就得到了一個最人匹配這也就是匈牙