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

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

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

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

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

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

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