快速求解大規(guī)模網(wǎng)路最大流問(wèn)題的研究.pdf

1、網(wǎng)絡(luò)流理論是運(yùn)籌學(xué)領(lǐng)域取得迅速發(fā)展的理論之一。到目前為止，應(yīng)該說(shuō)，無(wú)論從理論上還是實(shí)際應(yīng)用中，網(wǎng)絡(luò)流模型都是一個(gè)很成熟的模型。它的建立和求解算法的不斷改進(jìn)，為解決很多實(shí)際問(wèn)題提供了十分有用的工具。最大流問(wèn)題是網(wǎng)絡(luò)流現(xiàn)象中的特殊問(wèn)題，它是研究通過(guò)一個(gè)流通網(wǎng)絡(luò)的最大流量問(wèn)題。在網(wǎng)絡(luò)優(yōu)化領(lǐng)域，最大流問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題。最大流問(wèn)題是網(wǎng)絡(luò)流理論的極其重要的研究領(lǐng)域，除了運(yùn)用于實(shí)際網(wǎng)絡(luò)問(wèn)題的優(yōu)化以外，最大流問(wèn)題在很多科研與應(yīng)用領(lǐng)域，如電網(wǎng)

2、優(yōu)化、流量控制、線(xiàn)路優(yōu)化等和物理、化學(xué)、生物以及管理科學(xué)和應(yīng)用數(shù)學(xué)等基本學(xué)科都有著廣泛的應(yīng)用。盡管最大流問(wèn)題的研究已經(jīng)持續(xù)幾十年，該問(wèn)題的研究進(jìn)展已經(jīng)得到了很大的提高，但最大流問(wèn)題的研究還有很大的提高空間。
　　 首先，在算法的理論研究方面，人們還沒(méi)有研究出一個(gè)高效的算法，如何快速求解大規(guī)模網(wǎng)絡(luò)的最大流問(wèn)題;也沒(méi)有得到求解算法時(shí)間復(fù)雜度的準(zhǔn)確下界或近似下界。其次，伴隨著實(shí)際應(yīng)用問(wèn)題的網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，由此而產(chǎn)生的‘狀態(tài)爆炸問(wèn)題'

3、使得經(jīng)典算法以及其它們的改進(jìn)版本已經(jīng)不能滿(mǎn)足實(shí)際問(wèn)題的需要。再次，受計(jì)算機(jī)硬件本身限制，對(duì)于大規(guī)模數(shù)據(jù)，經(jīng)典算法甚至不能夠求解最大流問(wèn)題。因此，關(guān)于最大流問(wèn)題的研究具有十分重要的理論意義和實(shí)用價(jià)值。
　　 本文的研究重點(diǎn)在于，在保證計(jì)算誤差的條件下，如何簡(jiǎn)化網(wǎng)絡(luò)規(guī)模與降低計(jì)算量，從而達(dá)到降低計(jì)算規(guī)模、快速求解的目的。首先，通過(guò)獲取網(wǎng)絡(luò)中的特定結(jié)構(gòu)，根據(jù)該特定結(jié)構(gòu)的流量信息分析，進(jìn)而對(duì)特定結(jié)構(gòu)進(jìn)行選擇性壓縮，以降低網(wǎng)絡(luò)規(guī)模，構(gòu)成目

4、標(biāo)網(wǎng)絡(luò)，最終利用經(jīng)典算法求解最大流問(wèn)題?；谶@種思想，本文提出了基于壓縮社團(tuán)求解最大流的算法。其次，提出網(wǎng)絡(luò)分層的概念，對(duì)源網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分層，構(gòu)造出源網(wǎng)絡(luò)對(duì)應(yīng)的分層網(wǎng)絡(luò)，在層次網(wǎng)絡(luò)中計(jì)算相鄰層節(jié)點(diǎn)之間的流量，最后以局部最大流值的最小值作為全局的最優(yōu)值，從而對(duì)源網(wǎng)絡(luò)的最大流進(jìn)行快速有效的估計(jì)，減少計(jì)算時(shí)間。兩種算法在一定程度上降低了算法時(shí)間復(fù)雜度，并且能夠在誤差允許范圍內(nèi)，精確求解初始網(wǎng)絡(luò)最大流問(wèn)題。在國(guó)際公認(rèn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了

5、所提出算法的有效性與高效性。
　　 縱觀全文，本文的主要工作如下:
　　 1.闡述了最大流問(wèn)題研究、應(yīng)用背景及發(fā)展現(xiàn)狀，提出了經(jīng)典算法無(wú)法應(yīng)對(duì)的挑戰(zhàn)。簡(jiǎn)單介紹了網(wǎng)絡(luò)流理論、定理、經(jīng)典最大流算法及其改進(jìn)版本，并對(duì)以上所述算法進(jìn)行一定的研究與分析。
　　 2.基于壓縮網(wǎng)絡(luò)的思想提出了:基于壓縮社團(tuán)求解最大流的方法，通過(guò)獲取網(wǎng)絡(luò)中的特定結(jié)構(gòu)，根據(jù)該特定結(jié)構(gòu)的流量信息分析，進(jìn)而對(duì)特定結(jié)構(gòu)進(jìn)行選擇性壓縮，以降低網(wǎng)絡(luò)規(guī)模，構(gòu)

6、成目標(biāo)網(wǎng)絡(luò)，最終利用經(jīng)典算法求解最大流問(wèn)題，該算法能夠在一定程度上降低網(wǎng)絡(luò)規(guī)模且能夠精確求解出源網(wǎng)絡(luò)的最大流。
　　 3.基于層次網(wǎng)絡(luò)的最大流方法。提出網(wǎng)絡(luò)分層的概念，對(duì)源網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分層，構(gòu)造出源網(wǎng)絡(luò)對(duì)應(yīng)的分層網(wǎng)絡(luò)，同時(shí)結(jié)合最大流最小割定理，在層次網(wǎng)絡(luò)中計(jì)算相鄰層節(jié)點(diǎn)之間的流量，從而對(duì)源網(wǎng)絡(luò)的最大流進(jìn)行快速有效的估計(jì)，減少計(jì)算時(shí)間。對(duì)兩種算法的流程進(jìn)行詳細(xì)闡述，給出了在國(guó)際公認(rèn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，最終對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了理論分