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

內(nèi)容概要

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

書籍目錄

緒論上篇 阻塞流理論基礎(chǔ)  第1章 必備的圖論與網(wǎng)絡(luò)分析知識(shí)    1.1 圖論中常用的名詞    1.2 最短路問題    1.3 最大流問題    1.4 最小費(fèi)用流問題  第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 圖單純形算法的計(jì)算復(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 最小流算法的計(jì)算機(jī)實(shí)現(xiàn)  第5章 交通網(wǎng)絡(luò)隨機(jī)流仿真研究    5.1 隨機(jī)流動(dòng)仿真模型的建立    5.2 交通網(wǎng)絡(luò)隨機(jī)阻塞流仿真軟件設(shè)計(jì)    5.3 仿真結(jié)果的分析中篇 阻塞流理論在交通網(wǎng)絡(luò)設(shè)計(jì)與運(yùn)行控制中的應(yīng)用  第6章 阻塞流理論在交通網(wǎng)絡(luò)設(shè)計(jì)與運(yùn)行控制中的應(yīng)用    6.1 交通網(wǎng)絡(luò)防阻塞設(shè)計(jì)的基本準(zhǔn)則    6.2 最小流控制    6.3 最大流控制方法  第7章 隨機(jī)流動(dòng)網(wǎng)絡(luò)防阻塞優(yōu)化設(shè)計(jì)和改造研究    7.1 隨機(jī)流動(dòng)網(wǎng)絡(luò)防阻塞優(yōu)化設(shè)計(jì)的一般模型    7.2 交通網(wǎng)絡(luò)防阻塞的優(yōu)化改造    7.3 基于評(píng)價(jià)指標(biāo)對(duì)隨機(jī)流動(dòng)網(wǎng)絡(luò)優(yōu)化改造及運(yùn)行的仿真研究  第8章 考慮擁堵的最短時(shí)間流問題及其算法研究    8.1 考慮路段擁堵的最短時(shí)間流問題    8.2 考慮弧段阻塞的最小風(fēng)險(xiǎn)時(shí)間流問題下篇 阻塞流理論在一般圖中構(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)造哈密頓圈的實(shí)證研究  第10章 一般象棋盤中的馬步哈密頓圈問題及其實(shí)證研究    10.1 前言    10.2 象棋盤中的馬步哈密頓圈問題研究的基本理論    10.3 廣義象棋盤中的馬步哈密頓圈問題及其實(shí)證研究    10.4 有洞棋盤的馬步哈密頓圈問題及其實(shí)證研究    10.5 正方棋盤中廣義馬步哈密頓圈問題的若干研究結(jié)果    10.6 大型象棋盤中的馬步哈密頓圈實(shí)證解  第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在實(shí)用中縮短運(yùn)算時(shí)間的方法　　在上面SoA的理論研究中，證明了該算法的時(shí)問復(fù)雜性為O（n3m）.固然它相當(dāng)于O（n5）的多項(xiàng)式時(shí)間，但當(dāng)n較大時(shí)也需要很長的運(yùn)算時(shí)間。因此，研究縮短運(yùn)算時(shí)間的方法就有十分重要的實(shí)用意義，在大量的實(shí)證研究中發(fā)現(xiàn)，如果某一般圖是哈密頓圖，其中，哈密頓圈一般都有很多個(gè)，用SOA僅僅構(gòu)造出其中的某一個(gè)。因此，在SOA中，原始基本流的不同、最小支撐流流譜的不同、頂點(diǎn)編號(hào)方法的不同等，雖然它們都不會(huì)影響算法的有效性（指如果圖中存在哈密頓圈，則用它一定可以構(gòu)造出其中某一個(gè)哈密頓圈），但運(yùn)算的時(shí)間可能不同，結(jié)果（指哈密頓圈）也不一定相同，這種特點(diǎn)提供了可以縮短SOA運(yùn)算時(shí)間的組合并行算法?！　?）組合算法　　因?yàn)镾OA是結(jié)構(gòu)化方法、計(jì)算時(shí)間主要與網(wǎng)絡(luò)（或圖）的結(jié)構(gòu)有關(guān)，因此在算法的第二步（2）產(chǎn)生不同的引導(dǎo)單位流時(shí)，會(huì)產(chǎn)生不同的流譜結(jié)構(gòu)，這使得對(duì)不同的結(jié)構(gòu)圖來說，使用不同的程序（指產(chǎn)生的引導(dǎo)單位流不同）計(jì)算時(shí)間也有所不同，例如，在后面構(gòu)造22個(gè)金字塔圖中哈密頓圈的實(shí)證例子中，采用程序CGHP運(yùn)算的總時(shí)間為3074分57秒，采用程序CHPB則用4356分57秒，而采用組合算法選取它們之中的最小值，總時(shí)間為2406分27秒.這種實(shí)證結(jié)果表明，可以設(shè)計(jì)不同的產(chǎn)生單位最小流流譜的程序，同時(shí)并行使用，以便達(dá)到以最短時(shí)間達(dá)到計(jì)算要求的效果.這種縮短運(yùn)算時(shí)間的方法可稱為SOA的組合算法。　　2）去邊并行算法　　在原圖上去掉不同的邊后產(chǎn)生不同的子圖，對(duì)每一個(gè)子圖運(yùn)用同一個(gè)程序在單獨(dú)的計(jì)算機(jī)上運(yùn)行，多機(jī)同時(shí)并行工作，以最早得到結(jié)果的時(shí)間為準(zhǔn)?！　≡谠瓐D中去掉一定的邊的作用是　?。?）如果去掉的邊是在原圖某最小流流譜中的一個(gè)環(huán)上，則該環(huán)就在子圖的流譜上消失，而產(chǎn)生一個(gè)新的流譜；　　（2）如果去掉的邊是在基本流上，那么當(dāng)基本流改變時(shí)，環(huán)流布局就會(huì)改變，因而也會(huì)產(chǎn)生新的流鐠；　?。?）如果去掉的邊既不在環(huán)上，也不在基本上，但在SOA中的（3）尋找調(diào)整閉鏈時(shí)，也有可能會(huì)走不同的路線，而產(chǎn)生不同的最小流流譜.因此每次去掉一條不同的邊可以產(chǎn)生m個(gè)不同的流譜（其中包括可能無解的情況）。

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

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

---