阻塞流理論及其應(yīng)用

內(nèi)容概要

本書是作者在國家自然科學(xué)基金三次資助下進(jìn)行隨機網(wǎng)絡(luò)中阻塞流理論與應(yīng)用研究的研究報告，全書分上中下三篇，共12章，上篇主要介紹阻塞流的基本理論，包括網(wǎng)絡(luò)飽和流、阻塞流、完全截面、阻塞截面等基本概念、定義及其相互關(guān)系，研究了確定阻塞截面多種算法，還探討了求解網(wǎng)絡(luò)最大阻塞流(最大流)和最小阻塞流(最小流)的算法，并用網(wǎng)絡(luò)隨機流動仿真模型進(jìn)行了仿真驗證；中篇介紹阻塞流在交通網(wǎng)絡(luò)防阻塞沒計、改造和運行控制中的應(yīng)用及考慮阻塞的最短時間流問題，探討仿真方法在優(yōu)化改造中的應(yīng)用；下篇利用無環(huán)最小支撐流的模型來解決在一般圖中構(gòu)造哈密頓軌(或圈)問題的研究結(jié)果，提出了構(gòu)造哈密頓軌(或圈)的自組織算法并論證了算法的多項式性質(zhì)，在其實證研究中通過大約12000個網(wǎng)絡(luò)實例和解決一般圖中哈密頓圈問題研究的結(jié)果，驗證了算法的有效性，此外，還探討了象棋盤中馬步哈密頓圈和廣義哈密頓圈問題及其解法，附錄中給出了幾種網(wǎng)絡(luò)生成器算法源程序清單和若于特殊圖中哈密頓圈解的數(shù)據(jù)。    本書可供從事圖論、網(wǎng)絡(luò)流理論、計算復(fù)雜性、運籌學(xué)、組合數(shù)學(xué)、哈密頓圈和算法設(shè)計研究的工作者和研究生參考。

書籍目錄

緒論上篇 阻塞流理論基礎(chǔ)  第1章 必備的圖論與網(wǎng)絡(luò)分析知識    1.1 圖論中常用的名詞    1.2 最短路問題    1.3 最大流問題    1.4 最小費用流問題  第2章 阻塞流的基本理論    2.1 阻塞流的基本概念與定義    2.2 網(wǎng)絡(luò)的理論最小流通能力與其最小完全截集的關(guān)系    2.3 網(wǎng)絡(luò)理論最小流通能力的確定方法    2.4 阻塞流與阻塞截面  第3章 網(wǎng)絡(luò)的最大阻塞流問題    3.1 最大流問題的重新定義    3.2 最大流問題的圖單純形算法    3.3 圖單純形算法的計算復(fù)雜性分析  第4章 網(wǎng)絡(luò)的最小阻塞流問題    4.1 求解網(wǎng)絡(luò)最小流的分支定界法    4.2 求解網(wǎng)絡(luò)最小流的雙向增流算法    4.3 求解網(wǎng)絡(luò)最小流的圖單純形算法    4.4 關(guān)于最小流性質(zhì)的討論    4.5 求解網(wǎng)絡(luò)無環(huán)最小流的近似算法    4.6 最小流算法的計算機實現(xiàn)  第5章 交通網(wǎng)絡(luò)隨機流仿真研究    5.1 隨機流動仿真模型的建立    5.2 交通網(wǎng)絡(luò)隨機阻塞流仿真軟件設(shè)計    5.3 仿真結(jié)果的分析中篇 阻塞流理論在交通網(wǎng)絡(luò)設(shè)計與運行控制中的應(yīng)用  第6章 阻塞流理論在交通網(wǎng)絡(luò)設(shè)計與運行控制中的應(yīng)用    6.1 交通網(wǎng)絡(luò)防阻塞設(shè)計的基本準(zhǔn)則    6.2 最小流控制    6.3 最大流控制方法  第7章 隨機流動網(wǎng)絡(luò)防阻塞優(yōu)化設(shè)計和改造研究    7.1 隨機流動網(wǎng)絡(luò)防阻塞優(yōu)化設(shè)計的一般模型    7.2 交通網(wǎng)絡(luò)防阻塞的優(yōu)化改造    7.3 基于評價指標(biāo)對隨機流動網(wǎng)絡(luò)優(yōu)化改造及運行的仿真研究  第8章 考慮擁堵的最短時間流問題及其算法研究    8.1 考慮路段擁堵的最短時間流問題    8.2 考慮弧段阻塞的最小風(fēng)險時間流問題下篇 阻塞流理論在一般圖中構(gòu)造哈密頓圈上的應(yīng)用研究  第9章 阻塞流理論在一般圖中構(gòu)造哈密頓圈上的應(yīng)用研究    9.1 有向網(wǎng)絡(luò)中哈密頓軌構(gòu)造問題的網(wǎng)絡(luò)流模型    9.2 在有向網(wǎng)絡(luò)中構(gòu)造無環(huán)最小支撐流的方法    9.3 在一般圖中構(gòu)造哈密頓圈的實證研究  第10章 一般象棋盤中的馬步哈密頓圈問題及其實證研究    10.1 前言    10.2 象棋盤中的馬步哈密頓圈問題研究的基本理論    10.3 廣義象棋盤中的馬步哈密頓圈問題及其實證研究    10.4 有洞棋盤的馬步哈密頓圈問題及其實證研究    10.5 正方棋盤中廣義馬步哈密頓圈問題的若干研究結(jié)果    10.6 大型象棋盤中的馬步哈密頓圈實證解  第11章 廣義哈密頓圈問題及其構(gòu)造算法研究    11.1 廣義哈密頓圈問題的界定及其研究的意義    11.2 多哈密頓軌問題的支撐流模型及其構(gòu)造算法  第12章 馬步哈密頓圈(騎士巡游)在圖像置亂加密技術(shù)上的應(yīng)用    12.1 基于傳統(tǒng)騎士巡游路線的置亂算法    12.2 改進(jìn)算法1——改變騎士巡游矩陣    12.3 改進(jìn)算法2——分塊分層置亂的算法    12.4 改進(jìn)算法3——騎士巡游路線與Arnold置亂相結(jié)合的算法參考文獻(xiàn)

章節(jié)摘錄

　　4.SOA在實用中縮短運算時間的方法　　在上面SoA的理論研究中，證明了該算法的時問復(fù)雜性為O（n3m）.固然它相當(dāng)于O（n5）的多項式時間，但當(dāng)n較大時也需要很長的運算時間。因此，研究縮短運算時間的方法就有十分重要的實用意義，在大量的實證研究中發(fā)現(xiàn)，如果某一般圖是哈密頓圖，其中，哈密頓圈一般都有很多個，用SOA僅僅構(gòu)造出其中的某一個。因此，在SOA中，原始基本流的不同、最小支撐流流譜的不同、頂點編號方法的不同等，雖然它們都不會影響算法的有效性（指如果圖中存在哈密頓圈，則用它一定可以構(gòu)造出其中某一個哈密頓圈），但運算的時間可能不同，結(jié)果（指哈密頓圈）也不一定相同，這種特點提供了可以縮短SOA運算時間的組合并行算法?！　?）組合算法　　因為SOA是結(jié)構(gòu)化方法、計算時間主要與網(wǎng)絡(luò)（或圖）的結(jié)構(gòu)有關(guān)，因此在算法的第二步（2）產(chǎn)生不同的引導(dǎo)單位流時，會產(chǎn)生不同的流譜結(jié)構(gòu)，這使得對不同的結(jié)構(gòu)圖來說，使用不同的程序（指產(chǎn)生的引導(dǎo)單位流不同）計算時間也有所不同，例如，在后面構(gòu)造22個金字塔圖中哈密頓圈的實證例子中，采用程序CGHP運算的總時間為3074分57秒，采用程序CHPB則用4356分57秒，而采用組合算法選取它們之中的最小值，總時間為2406分27秒.這種實證結(jié)果表明，可以設(shè)計不同的產(chǎn)生單位最小流流譜的程序，同時并行使用，以便達(dá)到以最短時間達(dá)到計算要求的效果.這種縮短運算時間的方法可稱為SOA的組合算法?！　?）去邊并行算法　　在原圖上去掉不同的邊后產(chǎn)生不同的子圖，對每一個子圖運用同一個程序在單獨的計算機上運行，多機同時并行工作，以最早得到結(jié)果的時間為準(zhǔn)。　　在原圖中去掉一定的邊的作用是　?。?）如果去掉的邊是在原圖某最小流流譜中的一個環(huán)上，則該環(huán)就在子圖的流譜上消失，而產(chǎn)生一個新的流譜；　?。?）如果去掉的邊是在基本流上，那么當(dāng)基本流改變時，環(huán)流布局就會改變，因而也會產(chǎn)生新的流鐠；　?。?）如果去掉的邊既不在環(huán)上，也不在基本上，但在SOA中的（3）尋找調(diào)整閉鏈時，也有可能會走不同的路線，而產(chǎn)生不同的最小流流譜.因此每次去掉一條不同的邊可以產(chǎn)生m個不同的流譜（其中包括可能無解的情況）。

圖書封面

評論、評分、閱讀與下載

---

    阻塞流理論及其應(yīng)用 PDF格式下載

---