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

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

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

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

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

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

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