最大流問題是圖論中一個(gè)重要的基礎(chǔ)性問題,其求解算法在科學(xué)和工程領(lǐng)域以及現(xiàn)實(shí)生活中都有廣泛的應(yīng)用,城市交通相關(guān)的車流量控制、城市排水管道的最大排水量計(jì)算、網(wǎng)絡(luò)規(guī)劃、路徑規(guī)劃等重要問題都可以抽象為最大流問題;最大流問題也是計(jì)算機(jī)視覺、大數(shù)據(jù)以及圖像處理等技術(shù)的理論基礎(chǔ)。上述技術(shù)目前仍在快速發(fā)展和更新,因此對(duì)最大流問題的深入研究有助于促進(jìn)相關(guān)領(lǐng)域的發(fā)展,具有重要的理論意義和實(shí)際意義。學(xué)術(shù)界已提出多種用來解決最大流問題的新算法和新思路,逐步建立了單機(jī)求解最大流問題的較為完善的理論體系。雖然現(xiàn)有算法從多個(gè)角度求解最大流問題,但在應(yīng)用到海量圖數(shù)據(jù)處理時(shí)仍存在計(jì)算結(jié)果不準(zhǔn)確和求解效率較低等問題。針對(duì)這些問題,本文主要研究基于GraphChi框架的大規(guī)模圖最大流加速,并在該并行圖計(jì)算框架中嘗試解決圖分割計(jì)算復(fù)雜度較高,多次計(jì)算存在大量冗余工作等關(guān)鍵問題。本文主要內(nèi)容如下:(1)研究面向最大流計(jì)算的圖數(shù)據(jù)劃分和覆蓋圖構(gòu)建方法,利用割點(diǎn)構(gòu)建覆蓋圖并把原圖拆分成多個(gè)子圖,將割點(diǎn)映射到覆蓋圖并把其余頂點(diǎn)放入不同的子圖。在美國(guó)路網(wǎng)等經(jīng)典數(shù)據(jù)集上的測(cè)試結(jié)果表明,該算法將頂點(diǎn)數(shù)量縮減到了原圖的0.97%^6...

【文章頁數(shù)】：62 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 研究現(xiàn)狀
    1.3 主要?jiǎng)?chuàng)新點(diǎn)
    1.4 章節(jié)安排
第二章 最大流問題的相關(guān)理論和算法
    2.1 最大流問題模型
        2.1.1 圖的定義及相關(guān)概念
        2.1.2 最大流理論模型
        2.1.3 BDT理論模型
        2.1.4 基于BDT的查詢優(yōu)化
    2.2 增廣路徑算法
    2.3 預(yù)流推進(jìn)算法
    2.4 本章小結(jié)
第三章 覆蓋圖構(gòu)建算法
    3.1 圖數(shù)據(jù)劃分方法
    3.2 覆蓋圖構(gòu)建算法
        3.2.1 算法思想
        3.2.2 算法步驟
    3.3 實(shí)例分析
    3.4 實(shí)驗(yàn)結(jié)果與分析
    3.5 本章小結(jié)
第四章 最大流并行加速算法
    4.1 最大流問題回顧及限制條件
    4.2 查找路徑算法
    4.3 并行計(jì)算最大流
    4.4 實(shí)驗(yàn)結(jié)果與分析
    4.5 本章小結(jié)
第五章 基于Graph Chi框架加速計(jì)算
    5.1 Graph Chi框架簡(jiǎn)介
    5.2 并行滑動(dòng)窗口機(jī)制
        5.2.1 磁盤加載機(jī)制
        5.2.2 并行更新機(jī)制
        5.2.3 數(shù)據(jù)持久化機(jī)制
    5.3 基于框架的多子圖計(jì)算
    5.4 實(shí)驗(yàn)結(jié)果與分析
        5.4.1 基于框架加速構(gòu)建覆蓋圖實(shí)驗(yàn)
        5.4.2 基于框架并行計(jì)算多子圖最大流實(shí)驗(yàn)
        5.4.3 本文算法與經(jīng)典算法的對(duì)比實(shí)驗(yàn)
    5.5 本章小結(jié)
第六章 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
參考文獻(xiàn)
致謝
個(gè)人簡(jiǎn)歷、攻讀碩士學(xué)位期間取得的學(xué)術(shù)成果



本文編號(hào)：3970816