基于粒化思想求解大規(guī)模網(wǎng)絡(luò)最大流的研究.pdf

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

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

3、大規(guī)模網(wǎng)絡(luò)的發(fā)展速度。在人類(lèi)智能思維中，當(dāng)遇到復(fù)雜問(wèn)題、難以一次解決的問(wèn)題時(shí)，通常采用逐步求精、由粗到細(xì)的方式解決，而粒計(jì)算正是這種可以將復(fù)雜空間問(wèn)題轉(zhuǎn)換為多個(gè)簡(jiǎn)單問(wèn)題的理論。為了保證最大流算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)中快速高效的求解，本文提出使用粒計(jì)算中?；乃枷雭?lái)解決最大流問(wèn)題中的不足。
　　本文的研究重點(diǎn)在于如何通過(guò)將一個(gè)大規(guī)模復(fù)雜網(wǎng)絡(luò)?；癁槎鄠€(gè)結(jié)構(gòu)簡(jiǎn)單、便于求解的小型子網(wǎng)絡(luò)來(lái)大幅度減少求解最大流的時(shí)間，同時(shí)也要保證求解的準(zhǔn)確率。首

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

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