毛毛畢業(yè)論文答辯課件_第1頁
毛毛畢業(yè)論文答辯課件_第2頁
毛毛畢業(yè)論文答辯課件_第3頁
毛毛畢業(yè)論文答辯課件_第4頁
毛毛畢業(yè)論文答辯課件_第5頁
已閱讀5頁,還剩44頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

河北大學(xué)2013屆碩士畢業(yè)論文答辯網(wǎng)絡(luò)最大流算法研究指導(dǎo)教師:毛華答辯人:毛曉亮學(xué)科專業(yè):基礎(chǔ)數(shù)學(xué)答辯日期:2013年5月1目錄本文目錄網(wǎng)絡(luò)最大流研究背景算法改進(jìn)的基礎(chǔ)主要算法內(nèi)容總結(jié)2研究背景網(wǎng)絡(luò)最大流理論的研究至今已經(jīng)有將近60年的歷史,最早是Dantzig(1951)從運(yùn)籌學(xué)的角度出發(fā)的網(wǎng)絡(luò)單純形法,隨著Ford和Fulkerson(1956)標(biāo)號算法的提出,由圖論出發(fā)的網(wǎng)絡(luò)流理論才被系統(tǒng)的建立起來。50多年來,以2F標(biāo)號算法為基礎(chǔ),大量新穎有效的算法陸續(xù)被提出,不斷豐富和完善著網(wǎng)絡(luò)流理論,近年來,隨著計算機(jī)技術(shù)的迅猛發(fā)展,最大流算法復(fù)雜度的下界不斷被改進(jìn),同時,理論算法的實(shí)際實(shí)現(xiàn)效率不斷提高,進(jìn)而使網(wǎng)絡(luò)最大流理論在信息傳輸,路網(wǎng)交通,物資調(diào)運(yùn),配送,圖像處理等領(lǐng)域的應(yīng)用越來越廣泛,應(yīng)用價值也越來越高。3研究背景第三,基于圖論基礎(chǔ)上的網(wǎng)絡(luò)最大流理論,較之組合數(shù)學(xué),運(yùn)籌學(xué)上的方法,有其獨(dú)有的優(yōu)勢,現(xiàn)行算法比一般的線性規(guī)劃處理方法要簡單很多。正是因?yàn)槠浜啽阈?,因此,對于如何發(fā)現(xiàn)網(wǎng)絡(luò)最大流理論的更多有價值的實(shí)際應(yīng)用,本身就是一個很值得研究的重要課題。52.本文算法改進(jìn)的基礎(chǔ)第一,1956年由Ford和Fulkerson提出的2F標(biāo)號算法,此算法又被稱為增廣路算法,即在剩余網(wǎng)絡(luò)中不斷尋找增廣路,每找到一條增廣路就進(jìn)行一次增流,直至找到全部增廣路為止。但是,對于復(fù)雜網(wǎng)絡(luò),增廣路尋找本身就是一個極為棘手的問題,更為無奈的是,當(dāng)網(wǎng)絡(luò)的最大弧容量為無理數(shù)時,最大流不收斂。因此,2F標(biāo)號算法是偽多項(xiàng)式算法。62.本文算法改進(jìn)的基礎(chǔ)第二,1970年到1973年,Dinic增量網(wǎng)絡(luò)算法的提出,使得最大流算法的復(fù)雜度進(jìn)一步降低,由原來的O(nm2)和O(n2m)降低到O(m2logU)和O(nmlogU),其中U為整型網(wǎng)絡(luò)的最大弧容量。此后很長一段時間,算法時間復(fù)雜度核心因子一直停留在O(nm),沒有能被突破。73.1Dinic增量網(wǎng)絡(luò)算法的分析1.算法的基本步驟:Step0:初始化網(wǎng)絡(luò)的可行流f0;Step1:構(gòu)造網(wǎng)絡(luò)的增量網(wǎng)絡(luò)N(f);Step2:對增量網(wǎng)絡(luò)N(f)分層,若分層不能達(dá)到匯點(diǎn)y,則網(wǎng)絡(luò)的最大流為f0,否則轉(zhuǎn)下步;Step3:構(gòu)造網(wǎng)絡(luò)的輔助網(wǎng)絡(luò)AN(f),在AN(f)中尋找x-y有向路,即可增路;Step4:沿可增路增流完畢之后,刪去已經(jīng)被注滿的邊,反復(fù)增流,直至AN(f)中不存在x-y有向路為止;Step5:循環(huán)執(zhí)行以上步驟,若網(wǎng)絡(luò)已不能分層至y點(diǎn),則網(wǎng)絡(luò)最大流已找到;93.1Dinic增量網(wǎng)絡(luò)算法分析2.Dinic算法存在的問題:103.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:增廣路選擇的順序不同會導(dǎo)致最大流的流值無法達(dá)到最優(yōu)113.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:增廣路選擇的順序不同會導(dǎo)致最大流的流值無法達(dá)到最優(yōu)133.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:增廣路選擇的順序不同會導(dǎo)致最大流的流值無法達(dá)到最優(yōu)143.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:增廣路選擇的順序不同會導(dǎo)致最大流的流值無法達(dá)到最優(yōu)153.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:刪去已經(jīng)飽和的弧,更新網(wǎng)絡(luò):173.1Dinic增量網(wǎng)絡(luò)算法的分析2.Dinic算法存在的問題:此時網(wǎng)絡(luò)的最大流的流值為:2+2=4,而實(shí)際網(wǎng)絡(luò)的最大流為:2+2+2=6;183.2基于樞紐度的增廣路算法1.算法改進(jìn)中的一些重要概念樞紐度:設(shè)網(wǎng)絡(luò)N=(V,x,y,A,C),任意uV,TV,T={v|其中v為u的鄰點(diǎn)},為了表示v點(diǎn)對于u點(diǎn)的重要程度,我們稱v點(diǎn)的度(出度與入度之和)d(v)的倒數(shù)1/d(v)為網(wǎng)絡(luò)的樞紐度,記為Key(v),將樞紐度最大的點(diǎn)稱為樞紐點(diǎn)。注1(1)樞紐度表示的是此點(diǎn)在網(wǎng)絡(luò)連通性中的重要程度,換言之,刪去此點(diǎn)對網(wǎng)絡(luò)的連通性影響較大。193.2基于樞紐度的增廣路算法產(chǎn)出比值設(shè)網(wǎng)絡(luò)N=(V,x,y,A,C),任意vV,為點(diǎn)v的任一出弧,為點(diǎn)v的任一入弧,其弧容量分別為,,定義稱Tran(v)為v點(diǎn)的產(chǎn)出比值。注(1)由Tran(v)的定義可知,Tran(v)總是小于1的值。(2)給出一個新的標(biāo)記,Impo(v)=Key(x)Tran(v),稱Impo(v)為v點(diǎn)的流樞紐度。213.2基于樞紐度的增廣路算法Input:網(wǎng)絡(luò)N=(V,x,y,A,C)(即初始可行流為零流的增量網(wǎng)絡(luò))Output:網(wǎng)絡(luò)N的一個最大流Val.BeginVal=0;S={x};whileN中存在增廣路P;dowhile(v!=y)Key(v)=為u的鄰點(diǎn),uS;

令Val+=223.2基于樞紐度的增廣路算法更新增量網(wǎng)絡(luò);End仍然以原來的網(wǎng)絡(luò)的為例:233.2基于樞紐度的增廣路算法同理,第二條樞紐路:253.2基于樞紐度的增廣路算法第三條樞紐路:263.3基于流樞紐度的增廣路算法Input:網(wǎng)絡(luò)N=(V,x,y,A,C).Output:網(wǎng)絡(luò)N的一個最大流Val.BeginVal=0;S={x};whileN中存在增廣路P;dowhile(v!=y)Impo(v)=maxImpo(vi),vi為u的鄰點(diǎn),uS;

Val+=

293.3基于流樞紐度的增廣路算法End網(wǎng)絡(luò)實(shí)例運(yùn)行結(jié)果與理論值十分吻合303.3基于流樞紐度的增廣路算法例3如圖所示網(wǎng)絡(luò)N=(V,x,y,A,C):利用流樞紐度增廣路算法來求解網(wǎng)絡(luò)的最大流。313.3基于流樞紐度的增廣路算法首先,初始化Val=0,S={x},考察x的鄰點(diǎn)v1,v3,現(xiàn)在分別計算其樞紐度和產(chǎn)出比值:Key(v1)=1/4,Tran(v1)=Key(v3)=1/3,Tran(v3)=323.3基于流樞紐度的增廣路算法因此,流樞紐度為:Impo(v1)=Key(v1)Tran(v1)=Impo(v3)=Key(v3)Tran(v3)=

333.3基于流樞紐度的增廣路算法maxImpo(v1)=5/28,maxImpo(v3)=8/27,顯然,maxImpo(v3)>maxImpo(v1),由算法的執(zhí)行過程可知,樞紐路上選擇v3點(diǎn),且指向v4點(diǎn),依照深度優(yōu)先的原則,下一個點(diǎn)將會標(biāo)到v4,顯然,第一條樞紐路為P1=xv3v4y

343.3基于流樞紐度的增廣路算法同理,得到其他的流樞紐度增廣路,最終得到更新后的網(wǎng)絡(luò):354.二分部分割矩陣算法本節(jié)算法的思想如下:首先,對于網(wǎng)絡(luò)N=(V,x,y,A,C),構(gòu)造其逆向網(wǎng)絡(luò)=(V,y,x,A-1,C),同時構(gòu)造出兩者的部分割矩陣;其次,由連通性定理,尋找N的部分割矩陣的子陣,當(dāng)子陣階數(shù)較大時,轉(zhuǎn)向求N-1的部分割矩陣的子陣;最后,對子陣進(jìn)行集合的并交運(yùn)算,并最終求得網(wǎng)絡(luò)的最小割,也即,網(wǎng)絡(luò)的最大流。364.二分部分割矩陣算法得到的幾個定理:流等價定理設(shè)網(wǎng)絡(luò)N=(V,x,y,A,C),N

-1=(V,y,x,A-1,C),則,N與N

-1的最大流值相等。(2)連通性定理K=(S,)是N=(V,x,y,A,C)的一個割集,若G(S)不連通,則K一定不是網(wǎng)絡(luò)N的最小割。374.二分部分割矩陣算法2.給出的一些概念:(1)(部分割容量矩陣)下面的n-1階容量矩陣T稱為網(wǎng)絡(luò)N的部分割容量矩陣:384.二分部分割矩陣算法(2)部分割容量矩陣的特殊子陣=394.二分部分割矩陣算法網(wǎng)絡(luò)實(shí)例:404.二分部分割矩陣算法首先,構(gòu)造網(wǎng)絡(luò)和逆向網(wǎng)絡(luò)的部分割容量矩陣:T=414.二分部分割矩陣算法逆向網(wǎng)絡(luò):424.二分部分割矩陣算法特殊子陣:1階子陣:2階子陣:等等,最后得出所有需要考慮的全體子陣,根據(jù)并交運(yùn)算,得到最后的部分割,進(jìn)而得到最小割,也即最大流。

435.總結(jié)本文創(chuàng)新點(diǎn):本文的創(chuàng)新點(diǎn):克服了Dinic算法的占路問題障礙優(yōu)化了2F算法和Greedy算法二分部分割算法大大減少了計算量445.總結(jié)未來發(fā)展方向進(jìn)一步降低算法的時間復(fù)雜度進(jìn)一步減少割集矩陣方程數(shù)量拓展最大流技術(shù)的實(shí)際應(yīng)用45研究生期間撰寫的論文[1]毛華,毛曉亮,李斌.網(wǎng)絡(luò)最大流部分割矩陣算法.計算機(jī)科學(xué),2011,38(12)229-233.(中文核心期刊)[2]毛華,趙小娜,毛曉亮.危險品運(yùn)輸中的最小風(fēng)險最大流算法.計算機(jī)工程,2012,32(3),17-22.(計算機(jī)中文核心期刊)[3]毛華,趙小娜,史田敏,毛曉亮等.多部圖的最大匹配算法.鄭州大學(xué)學(xué)報(理學(xué)版),2013,3,45(1)27-29.(中文核心期刊)46致謝

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論