網(wǎng)絡(luò)流算法

定　價(jià)：￥99.00

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

購買這本書可以去

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

譯者序
前言
致謝
第 1 章預(yù)備知識：短路徑算法 1
1.1 無負(fù)權(quán)邊：Dijkstra 算法 2
1.2 有負(fù)權(quán)邊：Bellman-Ford算法 5
1.3 負(fù)權(quán)回路的檢測算法 9
練習(xí) 16
章節(jié)后記 17
第 2 章流算法 19
2.1 化條件 21
2.2 應(yīng)用：汽車共享問題 27
2.3 應(yīng)用：棒球隊(duì)淘汰問題 28
2.4 應(yīng)用：密子圖問題 33
2.5 改進(jìn)增廣路徑算法 37
2.6 容量度量算法 40
2.7 短增廣路徑算法 42
2.8 推送–重標(biāo)算法 44
練習(xí) 54
章節(jié)后記 59
第 3 章全局小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 隨機(jī)合并算法 72
3.4 Gomory-Hu 樹 76
練習(xí) 83
章節(jié)后記 85
第 4 章其他流算法 88
4.1 阻塞流算法 88
4.2 單位容量圖的阻塞流 90
4.3 Goldberg-Rao 算法 92
練習(xí) 96
章節(jié)后記 97
版權(quán)聲明 97
第 5 章小代價(jià)環(huán)流算法 99
5.1 化條件 101
5.2 Wallacher 算法 104
5.3 小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 網(wǎng)絡(luò)單純形 124
5.7 應(yīng)用: 帶時(shí)限的流問題 126
練習(xí) 130
章節(jié)后記 136
第 6 章廣義流算法 139
6.1 化條件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 負(fù)代價(jià) GAP 檢測 151
6.4 有損圖、Truemper 算法和收益度量 155
6.5 誤差度量 161
練習(xí) 163
章節(jié)后記 164
第 7 章多物流算法 166
7.1 化條件 166
7.2 雙物流問題 168
7.3 預(yù)備知識：乘權(quán)算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
練習(xí) 184
章節(jié)后記 185
第 8 章電流算法 187
8.1 化條件 187
8.2 無向圖的流問題 196
8.3 圖的稀疏化 199
8.4 簡易 Laplacian 求解器 204
練習(xí) 210
章節(jié)后記 212
版權(quán)聲明 213
第 9 章開放問題 214
參考文獻(xiàn) 216