網(wǎng)絡流算法

定　價：￥99.00

作　者：	[美]大衛(wèi)·P. 威廉姆森(David P. Williamson)
出版社：	機械工業(yè)出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

ISBN：	9787111701071	出版時間：	2022-03-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字數(shù)：

內(nèi)容簡介

　　網(wǎng)絡流理論在理論計算機科學、運籌學和離散數(shù)學等學科中均有應用，可用于貨物運輸建模和計算機視覺圖像分割等眾多問題。本書主要源于康奈爾大學的網(wǎng)絡流算法課程講義，包含出版年代較早的經(jīng)典書籍中未能涵蓋的新研究成果。本書采用簡潔且統(tǒng)一的視點，討論解決網(wǎng)絡流問題的多種組合算法、多項式算法及其分析，涵蓋流、小代價流、廣義流、多物流和全局小割集等，還介紹了關于計算電流的新研究成果及其在經(jīng)典問題上的應用。本書可作為面向研究生的網(wǎng)絡流算法教材，也適合該領域的研究人員參考。

作者簡介

　　：作者簡介：大衛(wèi)·P. 威廉姆森（David P. Williamson）康奈爾大學運籌學和信息工程學院教授，ACM會士，SIAM會士。他在離散優(yōu)化方面的研究獲得了多個獎項，包括2000年由美國數(shù)學協(xié)會和數(shù)學規(guī)劃協(xié)會贊助的Fulkerson獎。他與David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge， 2011）獲得了2013年的INFORMS Lanchester獎。他在多個編委會任職，曾任SIAM Journal on Discrete Mathematics的主編。：譯者簡介：吳向軍博士，中山大學副教授。主要研究方向為人工智能和算法設計等，近年來主要從事智能規(guī)劃領域的研究和規(guī)劃系統(tǒng)的設計與開發(fā)。

圖書目錄

譯者序
前言
致謝
第 1 章預備知識：短路徑算法 1
1.1 無負權邊：Dijkstra 算法 2
1.2 有負權邊：Bellman-Ford算法 5
1.3 負權回路的檢測算法 9
練習 16
章節(jié)后記 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
章節(jié)后記 59
第 3 章全局小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 隨機合并算法 72
3.4 Gomory-Hu 樹 76
練習 83
章節(jié)后記 85
第 4 章其他流算法 88
4.1 阻塞流算法 88
4.2 單位容量圖的阻塞流 90
4.3 Goldberg-Rao 算法 92
練習 96
章節(jié)后記 97
版權聲明 97
第 5 章小代價環(huán)流算法 99
5.1 化條件 101
5.2 Wallacher 算法 104
5.3 小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 網(wǎng)絡單純形 124
5.7 應用: 帶時限的流問題 126
練習 130
章節(jié)后記 136
第 6 章廣義流算法 139
6.1 化條件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 負代價 GAP 檢測 151
6.4 有損圖、Truemper 算法和收益度量 155
6.5 誤差度量 161
練習 163
章節(jié)后記 164
第 7 章多物流算法 166
7.1 化條件 166
7.2 雙物流問題 168
7.3 預備知識：乘權算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
練習 184
章節(jié)后記 185
第 8 章電流算法 187
8.1 化條件 187
8.2 無向圖的流問題 196
8.3 圖的稀疏化 199
8.4 簡易 Laplacian 求解器 204
練習 210
章節(jié)后記 212
版權聲明 213
第 9 章開放問題 214
參考文獻 216