阻塞流理论及其应用

出版时间：2009-4  出版社：科学  作者：宁宣熙  页数：262  字数：338000  

内容概要

本书是作者在国家自然科学基金三次资助下进行随机网络中阻塞流理论与应用研究的研究报告，全书分上中下三篇，共12章，上篇主要介绍阻塞流的基本理论，包括网络饱和流、阻塞流、完全截面、阻塞截面等基本概念、定义及其相互关系，研究了确定阻塞截面多种算法，还探讨了求解网络最大阻塞流(最大流)和最小阻塞流(最小流)的算法，并用网络随机流动仿真模型进行了仿真验证；中篇介绍阻塞流在交通网络防阻塞没计、改造和运行控制中的应用及考虑阻塞的最短时间流问题，探讨仿真方法在优化改造中的应用；下篇利用无环最小支撑流的模型来解决在一般图中构造哈密顿轨(或圈)问题的研究结果，提出了构造哈密顿轨(或圈)的自组织算法并论证了算法的多项式性质，在其实证研究中通过大约12000个网络实例和解决一般图中哈密顿圈问题研究的结果，验证了算法的有效性，此外，还探讨了象棋盘中马步哈密顿圈和广义哈密顿圈问题及其解法，附录中给出了几种网络生成器算法源程序清单和若于特殊图中哈密顿圈解的数据。    本书可供从事图论、网络流理论、计算复杂性、运筹学、组合数学、哈密顿圈和算法设计研究的工作者和研究生参考。

书籍目录

绪论上篇 阻塞流理论基础  第1章 必备的图论与网络分析知识    1.1 图论中常用的名词    1.2 最短路问题    1.3 最大流问题    1.4 最小费用流问题  第2章 阻塞流的基本理论    2.1 阻塞流的基本概念与定义    2.2 网络的理论最小流通能力与其最小完全截集的关系    2.3 网络理论最小流通能力的确定方法    2.4 阻塞流与阻塞截面  第3章 网络的最大阻塞流问题    3.1 最大流问题的重新定义    3.2 最大流问题的图单纯形算法    3.3 图单纯形算法的计算复杂性分析  第4章 网络的最小阻塞流问题    4.1 求解网络最小流的分支定界法    4.2 求解网络最小流的双向增流算法    4.3 求解网络最小流的图单纯形算法    4.4 关于最小流性质的讨论    4.5 求解网络无环最小流的近似算法    4.6 最小流算法的计算机实现  第5章 交通网络随机流仿真研究    5.1 随机流动仿真模型的建立    5.2 交通网络随机阻塞流仿真软件设计    5.3 仿真结果的分析中篇 阻塞流理论在交通网络设计与运行控制中的应用  第6章 阻塞流理论在交通网络设计与运行控制中的应用    6.1 交通网络防阻塞设计的基本准则    6.2 最小流控制    6.3 最大流控制方法  第7章 随机流动网络防阻塞优化设计和改造研究    7.1 随机流动网络防阻塞优化设计的一般模型    7.2 交通网络防阻塞的优化改造    7.3 基于评价指标对随机流动网络优化改造及运行的仿真研究  第8章 考虑拥堵的最短时间流问题及其算法研究    8.1 考虑路段拥堵的最短时间流问题    8.2 考虑弧段阻塞的最小风险时间流问题下篇 阻塞流理论在一般图中构造哈密顿圈上的应用研究  第9章 阻塞流理论在一般图中构造哈密顿圈上的应用研究    9.1 有向网络中哈密顿轨构造问题的网络流模型    9.2 在有向网络中构造无环最小支撑流的方法    9.3 在一般图中构造哈密顿圈的实证研究  第10章 一般象棋盘中的马步哈密顿圈问题及其实证研究    10.1 前言    10.2 象棋盘中的马步哈密顿圈问题研究的基本理论    10.3 广义象棋盘中的马步哈密顿圈问题及其实证研究    10.4 有洞棋盘的马步哈密顿圈问题及其实证研究    10.5 正方棋盘中广义马步哈密顿圈问题的若干研究结果    10.6 大型象棋盘中的马步哈密顿圈实证解  第11章 广义哈密顿圈问题及其构造算法研究    11.1 广义哈密顿圈问题的界定及其研究的意义    11.2 多哈密顿轨问题的支撑流模型及其构造算法  第12章 马步哈密顿圈(骑士巡游)在图像置乱加密技术上的应用    12.1 基于传统骑士巡游路线的置乱算法    12.2 改进算法1——改变骑士巡游矩阵    12.3 改进算法2——分块分层置乱的算法    12.4 改进算法3——骑士巡游路线与Arnold置乱相结合的算法参考文献

章节摘录

　　4.SOA在实用中缩短运算时间的方法　　在上面SoA的理论研究中，证明了该算法的时问复杂性为O（n3m）.固然它相当于O（n5）的多项式时间，但当n较大时也需要很长的运算时间。因此，研究缩短运算时间的方法就有十分重要的实用意义，在大量的实证研究中发现，如果某一般图是哈密顿图，其中，哈密顿圈一般都有很多个，用SOA仅仅构造出其中的某一个。因此，在SOA中，原始基本流的不同、最小支撑流流谱的不同、顶点编号方法的不同等，虽然它们都不会影响算法的有效性（指如果图中存在哈密顿圈，则用它一定可以构造出其中某一个哈密顿圈），但运算的时间可能不同，结果（指哈密顿圈）也不一定相同，这种特点提供了可以缩短SOA运算时间的组合并行算法。　　1）组合算法　　因为SOA是结构化方法、计算时间主要与网络（或图）的结构有关，因此在算法的第二步（2）产生不同的引导单位流时，会产生不同的流谱结构，这使得对不同的结构图来说，使用不同的程序（指产生的引导单位流不同）计算时间也有所不同，例如，在后面构造22个金字塔图中哈密顿圈的实证例子中，采用程序CGHP运算的总时间为3074分57秒，采用程序CHPB则用4356分57秒，而采用组合算法选取它们之中的最小值，总时间为2406分27秒.这种实证结果表明，可以设计不同的产生单位最小流流谱的程序，同时并行使用，以便达到以最短时间达到计算要求的效果.这种缩短运算时间的方法可称为SOA的组合算法。　　2）去边并行算法　　在原图上去掉不同的边后产生不同的子图，对每一个子图运用同一个程序在单独的计算机上运行，多机同时并行工作，以最早得到结果的时间为准。　　在原图中去掉一定的边的作用是　　（1）如果去掉的边是在原图某最小流流谱中的一个环上，则该环就在子图的流谱上消失，而产生一个新的流谱；　　（2）如果去掉的边是在基本流上，那么当基本流改变时，环流布局就会改变，因而也会产生新的流镨；　　（3）如果去掉的边既不在环上，也不在基本上，但在SOA中的（3）寻找调整闭链时，也有可能会走不同的路线，而产生不同的最小流流谱.因此每次去掉一条不同的边可以产生m个不同的流谱（其中包括可能无解的情况）。

用户评论 (总计1条)

•   书中可能有交通流的相关理论比较需要