大規(guī)模網(wǎng)絡(luò)最大流問題研究.pdf

1、網(wǎng)絡(luò)最大流問題是一個(gè)經(jīng)典的組合優(yōu)化問題，是計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)的重要內(nèi)容，在工程領(lǐng)域和科學(xué)研究領(lǐng)域具有廣泛的應(yīng)用。在網(wǎng)絡(luò)最大流算法的研究中，為了減少計(jì)算量，研究者們提出了許多改進(jìn)的方法。但是目前關(guān)于最大流問題的算法在理論性能和實(shí)際性能方面都還存在不足之處，算法的實(shí)際性能和許多應(yīng)用問題的要求之間還存在差距。特別是近年來隨著各種網(wǎng)絡(luò)和計(jì)算機(jī)科學(xué)的飛速發(fā)展，網(wǎng)絡(luò)的規(guī)模呈指數(shù)級(jí)增長，大規(guī)模網(wǎng)絡(luò)的流量計(jì)算也面臨著越來越多的挑戰(zhàn)，仍然使用經(jīng)典的網(wǎng)絡(luò)流

2、算法去直接求解這些大規(guī)模網(wǎng)絡(luò)的流量問題將會(huì)變得很困難甚至不可能。
　　 本文的研究重點(diǎn)在如何簡化大規(guī)模網(wǎng)絡(luò)以求解其最大流，通過將網(wǎng)絡(luò)中合適的節(jié)點(diǎn)集合構(gòu)成的子圖收縮成為一點(diǎn)，從而達(dá)到簡化網(wǎng)絡(luò)規(guī)模的目的。建立了一個(gè)先對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行簡化再求解其最大流的新模型。在這個(gè)模型的基礎(chǔ)上提出了三個(gè)計(jì)算大規(guī)模網(wǎng)絡(luò)最大流的新算法，它們分別是基于極大團(tuán)收縮簡化網(wǎng)絡(luò)的最大流算法，基于鄰居節(jié)點(diǎn)收縮簡化網(wǎng)絡(luò)的最大流算法以及基于分層節(jié)點(diǎn)收縮簡化網(wǎng)絡(luò)的最大流

3、算法。使用這些算法可以不同程度地減小網(wǎng)絡(luò)的規(guī)模從而降低計(jì)算的復(fù)雜性，為在大規(guī)模網(wǎng)絡(luò)中求解流量問題提供了方便，同時(shí)提供了一個(gè)解決大規(guī)模網(wǎng)絡(luò)最大流問題的新思路。在不同測試網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明了我們算法的有效性。
　　 縱觀全文，主要工作如下：
　　 1.介紹了最大流問題研究的背景、意義以及研究現(xiàn)狀。詳細(xì)地概括了網(wǎng)絡(luò)流基本的概念、結(jié)論和算法，并對(duì)這些算法的優(yōu)缺點(diǎn)進(jìn)行了分析。
　　 2.提出了對(duì)流網(wǎng)絡(luò)的一些預(yù)處理操作(容