高级搜索  |  搜索帮助
最近的浏览历史
购买此书的人还购买过
书  名:网络优化(第2版)(最优化基础——模型与方法系列教材)
  • 作  者: 谢金星、邢文训、王振波
  • 出版时间: 2009-07-01
  • 出 版 社: 清华大学出版社
  • 字  数: 245 千字
  • 印  次: 2-1
  • 印  张: 11
  • 开  本: 16开
  • ISBN: 9787302203254
  • 装  帧: 平装
  • 定  价:¥19.00
电子书价:¥13.30 折扣:70折 节省:¥5.70 vip价:¥13.30 电子书大小:8.54M
共有商品评论0条 查看评论摘要
内容简介
  本书系统介绍了网络优化的基本模型和基本算法,包括构造这些算法的基本思想以及相应算法在计算机上的一些具体实现技巧和复杂性分析.
全书由7章组成: 第1章为概论,第2章介绍关于算法的一些基本知识,第3章到第7章分别讨论树的问题、最短路问题、最大流问题、最小费用流问题和匹配问题.每章还安排了一些练习题.
本书可作为数学、应用数学、运筹学、管理科学、系统科学、信息科学、计算机科学与工程等专业的高年级大学生和研究生教材,也可供其他相关专业的学者和技术人员参考.
前言
  我们生活在一个网络社会中. 从某种意义上说,现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统. 网络优化就是研究如何有效地计划、管理和控制这个网络系统,使之发挥最大的社会和经济效益.
网络优化是运筹学(Operations Research)中的一个经典和重要的分支,所研究的问题涉及物资管理、经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术、控制论及军事运筹学等诸多领域. 因此学习一些有关网络优化的基本知识, 对许多专业的学生和许多领域的科技人员、管理人员都是相当必要的.
本书系统介绍了网络优化的基本模型和基本算法. 在基本模型方面, 主要介绍树的问题(包括最小树、最小树形图、最大分枝)、最短路问题、最大流问题、最小费用流问题和匹配问题等. 在基本算法方面,由于处理上述这些问题的算法非常多,而且新算法还在不断涌现, 从大量算法中选择哪些典型算法进行介绍本身是见仁见智的事,我们只能有选择地介绍其中部分算法. 我们既介绍一些比较经典的算法,也介绍一些比较新颖、实用的算法.
本书由7章组成. 第1章为概论, 主要介绍图和网络的一些基本概念、图和网络在计算机上的表示方法,并初步介绍计算复杂性理论.第2章介绍关于算法的一些基本知识,包括计算复杂性理论、近似算法、整数规划、动态规划,以及一些常用的网络搜索算法等.第3章到第7章分别介绍树的问题、最短路问题、最大流问题、最小费用流问题和匹配问题,这是网络优化的基本内容.
本次成书过程中参考了大量国内外有关文献和教材,并对内容进行了进一步的筛选和扩充. 我们希望本书能适合于各个层次的读者阅读. 对于数学和计算机等理论性要求较高的专业的教学,最好能讲授本书全部或大部分内容,并要求读者在学习本课程之前已经掌握了线性规划的基础知识. 我们希望不仅能让这部分读者了解各种网络优化算法的基本思想和基本理论,而且能了解一些实现技巧并学会算法的复杂性分析方法. 在各章的练习题中,我们还配备了一定数量难度较高的题目作为对书中讲授内容的扩充.对于其他理论性要求不太高的专业的教学或不太关心算法复杂性的读者来说,可以在阅读中略去部分理论内容. 对于只想对网络优化有所了解或只希望从本书中查询一些具体算法的读者来说,完全可以略去全部的理论部分, 而只了解相应的模型和算法就可以了.
自2000年以来,笔者以本书为教材在清华大学讲授研究生课程“网络优化”.在此期间,得到多方面的反馈和宝贵意见.在此基础上,我们对本书的结构和内容进行了一些调整和修改.在第2版中增加了算法基础一章,介绍一些准备知识,包括复杂性理论、近似算法及一些常用的算法.第1版中的整数规划和动态规划两章不再作为单独的章节出现,一些相关的内容安排在算法基础一章.
最后,对我们家人的理解、耐心和支持表示由衷的谢意!由于我们的水平有限,恳请读者对本书的不足之处提出批评指正.
目录
序言I
前言III第1章 概论1
1.1 网络优化问题的例子1
1.2 图与网络2
1.2.1 有向图与网络的基本概念2
1.2.2 无向图与无向网络的基本概念5
1.3 图与网络的数据结构6
1.3.1 邻接矩阵表示法6
1.3.2 关联矩阵表示法7
1.3.3 弧表表示法7
1.3.4 邻接表表示法8
1.3.5 星形表示法8
1.4 计算复杂性的概念11
1.4.1 组合最优化问题11
1.4.2 多项式时间算法13
1.4.3 多项式问题16
练习题18第2章 算法基础19
2.1 NP,NPC和NP-hard概念19
2.1.1 问题、实例与输入规模19
2.1.2 判定问题21
2.1.3 非确定多项式问题类(NP)22
2.1.4 NP完全问题类(NPC)25
2.2 算法设计与分析29
2.2.1 贪婪算法30
2.2.2 动态规划31
2.2.3 线性规划方法--全幺模矩阵34
2.2.4 两分法36
2.2.5 网络搜索算法37
2.3 小结38
练习题38第3章 最小树与最小树形图41
3.1 树的基本概念41
3.2 最小树算法44
3.2.1 Kruskal算法44
3.2.2 Prim算法46
3.2.3 Sollin算法48
3.3 最小树形图49
3.4 最大分枝53
练习题56第4章 最短路问题58
4.1 最短路问题的数学描述58
4.2 无圈网络与正费用网络: 标号设定算法60
4.2.1 Bellman方程60
4.2.2 无圈网络61
4.2.3 正费用网络62
4.3 一般费用网络: 标号修正算法65
4.3.1 Bellman-Ford算法65
4.3.2 一般的标号修正算法67
4.3.3 Floyd-Warshall算法68
练习题70第5章 最大流问题73
5.1 最大流问题的数学描述73
5.1.1 网络中的流73
5.1.2 最大流问题76
5.1.3 增广路定理77
5.2 增广路算法79
5.2.1 Ford-Fulkerson标号算法79
5.2.2 残量网络81
5.2.3 最大容量增广路算法82
5.2.4 容量变尺度算法83
5.3 最短增广路算法83
5.3.1 距离标号84
5.3.2 最短增广路算法85
5.3.3 复杂度分析87
5.4 一般的预流推进算法88
5.4.1 一般的预流推进算法88
5.4.2 复杂度分析91
5.5 最高标号预流推进算法94
5.5.1 最高标号预流推进算法94
5.5.2 算法的复杂度分析94
5.6 单位容量网络上的最大流算法96
5.6.1 单位容量网络上的最大流算法97
5.6.2 单位容量简单网络上的最大流算法98
练习题98第6章 最小费用流问题102
6. 1 最小费用流问题的数学描述102
6. 1. 1 最小费用流问题102
6. 1. 2 最小费用流模型的特例及扩展104
6. 2 消圈算法与最小费用路算法106
6. 2. 1 消圈算法106
6. 2. 2 最小费用路算法108
6. 3 原始-对偶算法111
6. 3. 1 对偶问题及互补松弛条件111
6. 3. 2 原始-对偶算法112
6. 4 瑕疵算法115
6. 5 松弛算法122
6. 6 网络单纯形算法127
6. 6. 1 算法的一般思路128
6. 6. 2 处理退化的方法131
6. 6. 3 初始的基本可行解133
6. 6. 4 容量有界的情形133
练习题136第7章 匹配问题141
7. 1 匹配问题的数学描述141
7. 2 二部基数匹配问题144
7. 2. 1 增广路算法144
7. 2. 2 应用简单网络上的最大流算法147
7. 3 非二部基数匹配问题147
7. 4 二部赋权匹配问题151
7. 5 非二部赋权匹配问题152
练习题162索引及英文关键词165

参考文献170
Copyright(C)清华大学出版社有限公司,All Rights Reserved 京ICP备10035462号 联系我们