基于?；枷肭蠼獯笠?guī)模網絡最大流的研究.pdf

1、網絡最大流問題是網絡流理論的重要組成，是介于連續(xù)型和離散型問題的分界線上，可作為特殊的線性規(guī)劃以及組合優(yōu)化問題。其在現實的實踐應用中，例如現實中的信息流、交通中的車流、電力網絡中的電流、物流網絡和社交網絡中的各種信息流等，網絡流都有著對應的權重大小，求解網絡最大流問題變得富有意義。
　　在過去的幾十年中，網絡最大流理論迅速發(fā)展，解決了運籌學以及計算機科學中的諸多問題。而在如今的社交網絡中，已有超過6億的社交網絡用戶，4.2億的移動

2、互聯網用戶，每天產生巨大的網絡數據，同時在新興行業(yè)，例如電子商務的350億交易量以及因此而產生的大量的物流業(yè)交易，而這些問題都可以轉化為網絡最大流問題，針對網絡優(yōu)化算法提出了更高的要求，使得最大流算法能夠更好的應用于不同的行業(yè)。因此，最大流的研究在新時期依然顯得尤為重要，更具有實際意義，在實際應用中有著較為廣闊的前景。然而經典算法類型的發(fā)展在幾十年前已經進入瓶頸時期，近年來，最大流算法在經典算法的基礎上有所改進，但是仍然不能適應當今時代

3、大規(guī)模網絡的發(fā)展速度。在人類智能思維中，當遇到復雜問題、難以一次解決的問題時，通常采用逐步求精、由粗到細的方式解決，而粒計算正是這種可以將復雜空間問題轉換為多個簡單問題的理論。為了保證最大流算法在大規(guī)模復雜網絡中快速高效的求解，本文提出使用粒計算中粒化的思想來解決最大流問題中的不足。
　　本文的研究重點在于如何通過將一個大規(guī)模復雜網絡?；癁槎鄠€結構簡單、便于求解的小型子網絡來大幅度減少求解最大流的時間，同時也要保證求解的準確率。首

4、先，根據?；枷雽⒃W絡?；癁槎鄠€不同的子網絡，形成多個不同的粒層，再分別求解由相鄰粒層組成的子網絡的最大流作為原網絡最大流的估計值，最后發(fā)現求解最大流的過程可以并行實現，因此使用多線程調度，使得其并行化。最后的實驗結果表明了本文方法的有效性，大幅度降低了求解網絡最大流所需時間，同時保證了結果的準確性。
　　本文的主要工作可以概括為:
　　1.首先介紹了本文在當前社會下的研究背景及意義，同時介紹了主題最大流求解以及主要方法粒

5、化思想現階段各自的研究現狀。
　　2.為了更好地理解本文的方法，第二章介紹了最大流問題的基礎知識以及一些基本算法，同時還介紹了粒計算思想以及粒計算基本原理在本文中的應用。
　　3.提出本文算法，基于粒化思想的求解網絡最大流算法，介紹了算法的相關概念定義以及算法的主要過程，最后給出實驗結果，驗證了算法的有效性。
　　4.在算法過程中發(fā)現算法的不足之處，并在后文給出其改進方法，將?；蟮淖泳W絡求解最大流部分采用多線程化求