一種新的最大流算法的研究.pdf

1、伴隨著計算機(jī)技術(shù)這幾十年來的高速發(fā)展，互聯(lián)網(wǎng)特別是移動互聯(lián)網(wǎng)和智能移動終端得到了迅速的發(fā)展和普及，大量的互聯(lián)網(wǎng)用戶每天通過電腦和移動終端產(chǎn)生的各種各樣的數(shù)據(jù)已經(jīng)達(dá)到了非常驚人的數(shù)量級。如何處理和分析這些大規(guī)模的數(shù)據(jù)，發(fā)現(xiàn)有用的數(shù)據(jù)為人們創(chuàng)造價值已經(jīng)成為現(xiàn)在非常熱門的研究方向。然而面對這樣大規(guī)模甚至超大規(guī)模的數(shù)據(jù)，很多傳統(tǒng)的串行的數(shù)據(jù)處理算法已經(jīng)不能夠滿足人們的需要，因而迫切需要研究新相應(yīng)的的并行化算法，提高數(shù)據(jù)的處理效率，滿足數(shù)據(jù)高速發(fā)

2、展的新要求。
　　網(wǎng)絡(luò)最大流問題是圖論有向圖部分中一個非常重要的基本問題，在圖論研究領(lǐng)域有著非常重要的理論意義。求解網(wǎng)絡(luò)最大流在圖論基本理論、社交網(wǎng)絡(luò)中的Web社團(tuán)發(fā)現(xiàn)、圖分割、快遞企業(yè)選址和交通分配等方面有非常廣泛和重要的應(yīng)用。然而在互聯(lián)網(wǎng)大數(shù)據(jù)計算的新要求下，傳統(tǒng)的求解網(wǎng)絡(luò)最大流的串行算法目前已經(jīng)難以滿足新的計算要求。研究求解網(wǎng)絡(luò)最大流算法的并行化實現(xiàn)是互聯(lián)網(wǎng)發(fā)展帶給我們的新的課題。
　　在數(shù)據(jù)量和數(shù)據(jù)規(guī)模不斷增大的形勢

3、下，為了研究最大流問題的并行算法，本文充分分析和研究了現(xiàn)有的最大流算法和基于BSP模型的Hama圖計算框架，根據(jù)流網(wǎng)絡(luò)中最大流算法的特點，結(jié)合 Hama中通過消息傳遞的方式來實現(xiàn)圖(Graph)的計算，設(shè)計并實現(xiàn)了分布式的Sense-Push最大流算法。
　　本文詳細(xì)介紹了 Sense-Push最大流算法的設(shè)計思路以及設(shè)計過程。詳細(xì)講解了Sense-Push算法的思想和流程，同時從理論上證明了Sense-Push算法的正確性。接著