网络流算法 pdf下载

网络流理论在理论计算机科学、运筹学和离散数学等学科中均有应用，可用于货物运输建模和计算机视觉图像分割等众多问题。本书主要源于康奈尔大学的网络流算法课程讲义，包含出版年代较早的经典书籍中未能涵盖的新研究成果。本书采用简洁且统一的视点，讨论解决网络流问题的多种组合算法、多项式算法及其分析，涵盖大流、小代价流、广义流、多物流和全局小割集等，还介绍了关于计算电流的新研究成果及其在经典问题上的应用。本书可作为面向研究生的网络流算法教材，也适合该领域的研究人员参考。

---作者简介---
大卫·P. 威廉姆森（David P. Williamson） 康奈尔大学运筹学和信息工程学院教授，ACM会士，SIAM会士。他在离散优化方面的研究获得了多个奖项，包括2000年由美国数学协会和数学规划协会赞助的Fulkerson奖。他与David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge, 2011）获得了2013年的INFORMS Lanchester奖。他在多个编委会任职，曾任SIAM Journal on Discrete Mathematics的主编。

---译者简介---
吴向军 博士，中山大学副教授。主要研究方向为人工智能和算法设计等，近年来主要从事智能规划领域的研究和规划系统的设计与开发。

译者序
前言
致谢
第 1 章 预备知识：最短路径算法 1
1.1 无负权边：Dijkstra 算法 2
1.2 有负权边：Bellman-Ford算法 5
1.3 负权回路的检测算法 9
练习 16
章节后记 17
第 2 章 最大流算法 19
2.1 最优化条件 21
2.2 应用：汽车共享问题 27
2.3 应用：棒球队淘汰问题 28
2.4 应用：最密子图问题 33
2.5 最大改进增广路径算法 37
2.6 容量度量算法 40
2.7 最短增广路径算法 42
2.8 推送–重标算法 44
练习 54
章节后记 59
第 3 章 全局最小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 随机合并算法 72
3.4 Gomory-Hu 树 76
练习 83
章节后记 85
第 4 章 其他最大流算法 88
4.1 阻塞流算法 88
4.2 单位容量图的阻塞流 90
4.3 Goldberg-Rao 算法 92
练习 96
章节后记 97
版权声明 97
第 5 章 最小代价环流算法 99
5.1 最优化条件 101
5.2 Wallacher 算法 104
5.3 最小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 网络单纯形 124
5.7 应用: 带时限的最大流问题 126
练习 130
章节后记 136
第 6 章 广义流算法 139
6.1 最优化条件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 负代价 GAP 检测 151
6.4 有损图、Truemper 算法和收益度量 155
6.5 误差度量 161
练习 163
章节后记 164
第 7 章 多物流算法 166
7.1 最优化条件 166
7.2 双物流问题 168
7.3 预备知识：乘权算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
练习 184
章节后记 185
第 8 章 电流算法 187
8.1 最优化条件 187
8.2 无向图的最大流问题 196
8.3 图的稀疏化 199
8.4 简易 Laplacian 求解器 204
练习 210
章节后记 212
版权声明 213
第 9 章 开放问题 214
参考文献 216

拾人花卉，系之一束；他供鲜花，我献彩带。
——Montaigne

网络流方面的任何新书似乎都应说明其存在的合理性，因为该领域的权威著作早已出版。我所参考的书籍《网络流：理论、算法和应用》(Network Flows: Theory, Algorithms, and Applications) 已于 1993 年出版。该书作者为 Ahuja、Magnanti 和 Orlin[4]，他们是网络流算法领域理论研究和实践应用的先驱。我用该书作者姓名的首字母 AMO 来代表此书。20 世纪 80 年代末至 90 年代初是研究网络流问题的组合算法和多项式算法的黄金时期。AMO 不仅讨论了当时已完成的大部分研究，还给出了网络流领域的广泛综述，其内容贯穿网络流理论研究和实际应用。既然如此，为何还需写此书？我有下面三方面的理由。
第一：关注点问题。我在写另一领域的严谨性书籍 [206] 时意识到，书籍内容很难兼顾“准确严谨” 和 “简洁明了”。AMO 无疑是前者，本书的目标是后者。本书主要关注网络流问题的组合算法、多项式算法及其分析。在康奈尔大学运筹学和信息工程学院任教期间，我教过几次网络流算法方面的研究生课程，本书内容源于对这些课程内容的提炼。该课程主要面向运筹学和计算机科学系的学生，也有电气和土木工程系的部分学生。从教学观点来看，需做点取舍，以保证本书的大部分内容可在一学期内讲完。
此外，由于本书是课堂教学的成果，其涵盖的知识点是一次授课所能讲完的内容。因此，太长或太复杂而无法在一次授课中讲完的知识点，本书都不涵盖。我不太关注网络流理论中的某些领域，比如没有多项式运行时间的网络流应用和算法等。对于本书未涉及的某些网络流理论部分，感兴趣的读者可参阅 AMO。
第二：提供一些 AMO 没有涉及的知识。对最大流问题和最小代价环流问题，虽然本书所提的算法 AMO 也有涉及，但本书给出了一些重要的特殊情形。如前所述，虽然 20 世纪 80 年代末至 90 年代初是研究网络流算法的黄金时代，但该领域在过去 25 年里的研究成果是 AMO 无法涵盖的。
1998 年，Goldberg 和 Rao 所发表的论文 [98] 就是一个著名的研究成果。对最大流问题，他们给出了至今为止在理论上仍被认为最快的算法。1991 年，Wallacher[201] 关于最小代价环流问题的算法是另一个研究成果，该算法具有相当简单的分析。此外，AMO 出版时，针对某些流问题，一些多项式算法正好脱颖而出。显然，AMO 无法涵盖这些算法。
我主要思考的是全局最小割集、广义最大流和多物流等问题的算法。近年来，内点方法在网络流问题的特殊应用中产生了一些快速算法，但这些算法不是组合算法，因此，它们不在本书的选取范围内。本书还包含了一些与电流经典主题相关的成果。
第三：情不自禁。我的主要研究兴趣是组合算法和多项式算法，但在网络流领域，除有一项研究成果外 [173]，几乎一无所获。所以，作为一位公正的旁观者，我可以说，该领域是一个优美且存在一些有用算法思想的领域，这些算法思想以一种令人愉悦的方式相互支持着。
用前面引述的 Montaigne 的话来说，写本书的目的就是做选择和重组，尽我所能地展现一些算法及其分析的美妙之处。希望读者和我一样欣赏这最终呈现的花束。

David P. Williamson
纽约，伊萨卡
2019 年 1 月