掃一掃
關(guān)注中圖網(wǎng)
官方微博
本類五星書更多>
-
>
宇宙、量子和人類心靈
-
>
氣候文明史
-
>
南極100天
-
>
考研數(shù)學(xué)專題練1200題
-
>
希格斯:“上帝粒子”的發(fā)明與發(fā)現(xiàn)
-
>
神農(nóng)架疊層石:10多億年前遠(yuǎn)古海洋微生物建造的大堡礁
-
>
聲音簡史
排序與時序最優(yōu)化引論 版權(quán)信息
- ISBN：9787030631978
- 條形碼：9787030631978 ; 978-7-03-063197-8
- 裝幀：平裝-膠訂
- 冊數(shù)：暫無
- 重量：暫無
- 所屬分類：>>
排序與時序最優(yōu)化引論 本書特色
線性模型的一階可解性從可分離系數(shù)的排序規(guī)則開始，發(fā)展為梯度遞增的凸性規(guī)則，再到擬陣與獨立系統(tǒng)，從而概括一大類經(jīng)典問題。二階可解性是借助限位結(jié)構(gòu)，將求解途徑納入基于交錯鏈變換的匹配型算法。可解性的另一線索是從局部的偏序關(guān)系擴(kuò)張為整體的全序關(guān)系，即偏序集的線性擴(kuò)張方法。進(jìn)而，一旦遇到劃分結(jié)構(gòu)，便進(jìn)入難解性境地。證明NP-困難性的方法，是運用模擬、強(qiáng)迫及變尺度的技巧，構(gòu)造時序問題的劃分模型。在判定NP-困難性之后，精確算法主要是隱枚舉，即動態(tài)規(guī)劃與分枝定界。運用動態(tài)規(guī)劃建立偽多項式時間算法，為近似算法做準(zhǔn)備。難解性問題的*終歸宿是近似算法設(shè)計與分析，其中性能比分析的主導(dǎo)思想是運用均值下界及關(guān)鍵工件進(jìn)行結(jié)構(gòu)松弛，任意精度逼近是運用伸縮尺度方法。*后，概述空間模式的順序優(yōu)化，包括車行路線、電路布線、矩陣運算、DNA基因序列重構(gòu)等。
排序與時序最優(yōu)化引論 內(nèi)容簡介
本書從結(jié)構(gòu)性質(zhì)與方法途徑的觀點來論述時序優(yōu)化的基本理論。一階可解性是指線性生成的貪婪算法。其內(nèi)在依據(jù)是獨立性, 從可分離系數(shù)的排序規(guī)則到梯度遞增的凸性, 再到擬陣與獨立系統(tǒng), 可概括一大類經(jīng)典問題。二階可解性是藉助限位結(jié)構(gòu), 將眾多模型納入組合*優(yōu)化中的二部圖匹配型算法。可解性的另一線索是從局部的偏序關(guān)系擴(kuò)張為整體的全序關(guān)系, 即偏序集的線性擴(kuò)張方法。進(jìn)而, 一旦遇到劃分結(jié)構(gòu), 便進(jìn)入難解性境地。證明NP-困難性的方法, 是運用模擬、強(qiáng)迫及變尺度的技巧, 構(gòu)造時序問題的劃分模型。在判定問題的NP-困難性之后, 精確算法只有動態(tài)規(guī)劃與分枝定界。
排序與時序最優(yōu)化引論 目錄
目錄
《運籌與管理科學(xué)叢書》序
前言
第1章 緒論 1
1.1 學(xué)科的定位 1
1.1.1 組合*優(yōu)化 1
1.1.2 時序性組合*優(yōu)化 2
1.1.3 歷史注記 5
1.2 基本概念 6
1.2.1 工件-機(jī)器模型 6
1.2.2 數(shù)學(xué)模型中的機(jī)程方案 8
1.2.3 有向圖與無向圖 14
1.2.4 偏序關(guān)系與偏序集 17
1.2.5 數(shù)據(jù)結(jié)構(gòu)中的順序表示 18
1.2.6 模型的分類 20
1.3 選題線索概覽 21
1.3.1 時序問題的組合特性 21
1.3.2 可解性與難解性 23
1.3.3 難易程度的層次分類 25
1.3.4 結(jié)構(gòu)性質(zhì)提要 26
1.3.5 選題范圍的約定 27
習(xí)題1 28
第2章 獨立性與貪婪型算法 31
2.1 可分離性結(jié)構(gòu) 31
2.1.1 可分離系數(shù)的分配問題 31
2.1.2 貪婪型算法的一般形式 34
2.1.3 可分離費用的時序問題 36
2.2 可分離系數(shù)的推廣——凸性排序原理 44
2.2.1 局部交換性條件 44
2.2.2 凸性的解釋 47
2.2.3 工件的獨立相鄰關(guān)系 48
2.2.4 加權(quán)總完工時間問題 51
2.2.5 二機(jī)器流水作業(yè)問題 55
2.2.6 二機(jī)器自由作業(yè)問題 59
2.3 獨立系統(tǒng)上的貪婪算法 62
2.3.1 獨立系統(tǒng)與擬陣 62
2.3.2 擬陣算法應(yīng)用于排序問題 65
2.3.3 單機(jī)延誤數(shù)問題的貪婪算法 66
2.3.4 有到達(dá)期的延誤數(shù)問題 71
2.3.5 有截止期的延誤數(shù)問題 74
2.4 后向貪婪算法 77
2.4.1 一般**費用模型 77
2.4.2 有截止期的**費用問題 78
2.4.3 有到達(dá)期的**費用問題 78
習(xí)題2 81
第3章 限位結(jié)構(gòu)與分配型算法 84
3.1 工件與位置的可匹配性 84
3.1.1 二部圖的匹配算法 84
3.1.2 匹配算法應(yīng)用于時序問題 86
3.1.3 凸二部圖 89
3.1.4 區(qū)間圖 92
3.1.5 連續(xù)型匹配問題的Hall型定理 93
3.1.6 連續(xù)型匹配問題迭代方法 95
3.2 工件與機(jī)器的相容關(guān)系 98
3.2.1 有機(jī)器限位約束的平行機(jī)問題 98
3.2.2 具有一般目標(biāo)函數(shù)的模型 103
3.2.3 具有凸性約束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中斷的平行機(jī)問題 108
3.3.2 可中斷的自由作業(yè)問題 113
3.3.3 分配型線性規(guī)劃方法的應(yīng)用 117
3.4 連貫加工的位置約束 120
3.4.1 凸二部圖與凸子集族的刻畫 120
3.4.2 有連貫加工約束的時序問題 127
習(xí)題3 135
第4章 偏序結(jié)構(gòu)與線性擴(kuò)張算法 138
4.1 *優(yōu)性條件中的偏序關(guān)系 138
4.1.1 局部優(yōu)先關(guān)系擴(kuò)充為*優(yōu)順序 138
4.1.2 二機(jī)器流水作業(yè)問題的偏序與半序 139
4.1.3 二機(jī)器流水作業(yè)問題的*優(yōu)性準(zhǔn)則 142
4.1.4 總延誤問題中的優(yōu)先關(guān)系 146
4.1.5 總延誤問題的偏序擴(kuò)張 150
4.1.6 總延誤問題的分解原理 153
4.2 有偏序約束的單機(jī)問題 157
4.2.1 有序列平行偏序約束的問題 158
4.2.2 有樹型偏序約束的問題 164
4.2.3 有一般偏序約束的單位工時問題 166
4.3 有偏序約束的多臺機(jī)器問題 168
4.3.1 有樹型約束的平行機(jī)問題 168
4.3.2 有一般偏序約束的平行機(jī)問題 173
4.3.3 有序列平行偏序約束的流水作業(yè)問題 178
4.4 偏序集的鏈分解 182
4.4.1 Dilworth定理 182
4.4.2 *小機(jī)器數(shù)平行作業(yè)問題 184
4.5 跳躍數(shù)與調(diào)整時間排序 185
4.5.1 跳躍數(shù)問題 185
4.5.2 具有調(diào)整時間的排序問題 188
習(xí)題4 190
第5章 劃分結(jié)構(gòu)與難解性判定 192
5.1 計算復(fù)雜性的基本概念 192
5.1.1 多項式時間算法 192
5.1.2 P 類及NP類問題 195
5.1.3 NP-完全問題及NP-困難問題 196
5.1.4 基本的NP-完全及NP-困難問題 198
5.1.5 基本證明方法I:模擬變換法 200
5.1.6 基本證明方法II:強(qiáng)制壓迫法 203
5.2 常義NP-困難問題 206
5.2.1 以劃分問題為參照問題 206
5.2.2 以背包問題為參照問題 208
5.3 強(qiáng)NP-困難問題 210
5.3.1 純組合的參照問題 211
5.3.2 以3-劃分問題為參照問題 217
5.4 變尺度的不等式設(shè)計方法 222
5.4.1 單機(jī)總延誤問題 223
5.4.2 公共工期的加權(quán)總延誤問題 231
5.4.3 可中斷問題舉例 236
習(xí)題5 238
第6章 遞推結(jié)構(gòu)與隱枚舉搜索 241
6.1 動態(tài)規(guī)劃的遞推方法 241
6.1.1 *優(yōu)化原理 241
6.1.2 含參變量的序列極值方法 244
6.1.3 獨立決策過程的貪婪算法 245
6.1.4 不定期過程方法 246
6.1.5 同順序mn排序問題 251
6.2 偽多項式時間算法的建立 255
6.2.1 背包問題 255
6.2.2 單機(jī)加權(quán)延誤數(shù)問題 256
6.2.3 兩臺平行機(jī)的加權(quán)總完工時間問題 258
6.2.4 公共工期的加權(quán)總延誤問題 260
6.2.5 單機(jī)總延誤問題 262
6.3 分批排序問題的動態(tài)規(guī)劃方法 263
6.3.1 加權(quán)總完工時間的分批排序 263
6.3.2 **延遲的分批排序 267
6.3.3 延誤數(shù)的分批排序 271
6.4 分枝定界方法 273
6.4.1 *優(yōu)化原理的另一應(yīng)用 273
6.4.2 三臺機(jī)器的流水作業(yè)問題 276
6.5 啟發(fā)式算法 281
6.5.1 局部鄰域搜索法 281
6.5.2 汽輪機(jī)葉片排序問題 283
6.5.3 電網(wǎng)機(jī)組檢修調(diào)度 286
習(xí)題6 288
第7章 結(jié)構(gòu)松弛與近似算法 290
7.1 近似算法的逼近程度衡量 290
7.1.1 近似算法的性能比 290
7.1.2 性能比分析方法: 均值下界與關(guān)鍵工件 292
7.1.3 工件陸續(xù)到達(dá)情形的動態(tài)分析方法 299
7.1.4 線性規(guī)劃松弛方法 306
7.2 任意精度逼近理論 312
7.2.1 多項式時間逼近方案 312
7.2.2 偽多項式時間算法的舍入變換 315
7.2.3 運用枚舉搜索的逼近方法 322
7.2.4 運用劃分范圍的逼近方法 329
7.3 不可近似性分析 334
7.3.1 性能比的下界 334
7.3.2 排除PTAS的可能性 337
習(xí)題7 338
第8章 空間模式的序結(jié)構(gòu)優(yōu)化問題 340
8.1 遍歷性與巡回路線*優(yōu)化 340
8.1.1 遍歷性問題 340
8.1.2 運輸與車輛調(diào)度 341
8.1.3 中國郵遞員問題 344
8.1.4 車行路由問題 345
8.2 稀疏矩陣計算的順序優(yōu)化 349
8.2.1 稀疏矩陣的存儲方式 350
8.2.2 稀疏矩陣的消去與填充 354
8.2.3 圖的排序與標(biāo)號問題 356
8.2.4 研究課題概述 364
8.3 電路布線與順序嵌入 371
8.3.1 網(wǎng)絡(luò)嵌入的一般模型 371
8.3.2 線性順序嵌入 373
8.3.3 循環(huán)順序嵌入 375
8.3.4 二維網(wǎng)格嵌入 377
8.3.5 書式嵌入 379
8.4 走向更寬闊的時空優(yōu)化領(lǐng)域 380
8.4.1 序貫決策*優(yōu)化 380
8.4.2 DNA基因組序列排序問題 382
8.4.3 移位寄存器設(shè)計 385
8.4.4 頻道分配問題 386
8.4.5 競賽排名問題 387
8.4.6 從路嵌入到樹嵌入 388
習(xí)題8 391
參考文獻(xiàn) 393
時序優(yōu)化問題分類索引 406
I.單機(jī)模型 406
II.平行機(jī)模型 408
III.串聯(lián)機(jī)模型 409
IV.其他序結(jié)構(gòu)優(yōu)化模型 410
索引 412
《運籌與管理科學(xué)叢書》已出版書目 418
《運籌與管理科學(xué)叢書》序
前言
第1章 緒論 1
1.1 學(xué)科的定位 1
1.1.1 組合*優(yōu)化 1
1.1.2 時序性組合*優(yōu)化 2
1.1.3 歷史注記 5
1.2 基本概念 6
1.2.1 工件-機(jī)器模型 6
1.2.2 數(shù)學(xué)模型中的機(jī)程方案 8
1.2.3 有向圖與無向圖 14
1.2.4 偏序關(guān)系與偏序集 17
1.2.5 數(shù)據(jù)結(jié)構(gòu)中的順序表示 18
1.2.6 模型的分類 20
1.3 選題線索概覽 21
1.3.1 時序問題的組合特性 21
1.3.2 可解性與難解性 23
1.3.3 難易程度的層次分類 25
1.3.4 結(jié)構(gòu)性質(zhì)提要 26
1.3.5 選題范圍的約定 27
習(xí)題1 28
第2章 獨立性與貪婪型算法 31
2.1 可分離性結(jié)構(gòu) 31
2.1.1 可分離系數(shù)的分配問題 31
2.1.2 貪婪型算法的一般形式 34
2.1.3 可分離費用的時序問題 36
2.2 可分離系數(shù)的推廣——凸性排序原理 44
2.2.1 局部交換性條件 44
2.2.2 凸性的解釋 47
2.2.3 工件的獨立相鄰關(guān)系 48
2.2.4 加權(quán)總完工時間問題 51
2.2.5 二機(jī)器流水作業(yè)問題 55
2.2.6 二機(jī)器自由作業(yè)問題 59
2.3 獨立系統(tǒng)上的貪婪算法 62
2.3.1 獨立系統(tǒng)與擬陣 62
2.3.2 擬陣算法應(yīng)用于排序問題 65
2.3.3 單機(jī)延誤數(shù)問題的貪婪算法 66
2.3.4 有到達(dá)期的延誤數(shù)問題 71
2.3.5 有截止期的延誤數(shù)問題 74
2.4 后向貪婪算法 77
2.4.1 一般**費用模型 77
2.4.2 有截止期的**費用問題 78
2.4.3 有到達(dá)期的**費用問題 78
習(xí)題2 81
第3章 限位結(jié)構(gòu)與分配型算法 84
3.1 工件與位置的可匹配性 84
3.1.1 二部圖的匹配算法 84
3.1.2 匹配算法應(yīng)用于時序問題 86
3.1.3 凸二部圖 89
3.1.4 區(qū)間圖 92
3.1.5 連續(xù)型匹配問題的Hall型定理 93
3.1.6 連續(xù)型匹配問題迭代方法 95
3.2 工件與機(jī)器的相容關(guān)系 98
3.2.1 有機(jī)器限位約束的平行機(jī)問題 98
3.2.2 具有一般目標(biāo)函數(shù)的模型 103
3.2.3 具有凸性約束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中斷的平行機(jī)問題 108
3.3.2 可中斷的自由作業(yè)問題 113
3.3.3 分配型線性規(guī)劃方法的應(yīng)用 117
3.4 連貫加工的位置約束 120
3.4.1 凸二部圖與凸子集族的刻畫 120
3.4.2 有連貫加工約束的時序問題 127
習(xí)題3 135
第4章 偏序結(jié)構(gòu)與線性擴(kuò)張算法 138
4.1 *優(yōu)性條件中的偏序關(guān)系 138
4.1.1 局部優(yōu)先關(guān)系擴(kuò)充為*優(yōu)順序 138
4.1.2 二機(jī)器流水作業(yè)問題的偏序與半序 139
4.1.3 二機(jī)器流水作業(yè)問題的*優(yōu)性準(zhǔn)則 142
4.1.4 總延誤問題中的優(yōu)先關(guān)系 146
4.1.5 總延誤問題的偏序擴(kuò)張 150
4.1.6 總延誤問題的分解原理 153
4.2 有偏序約束的單機(jī)問題 157
4.2.1 有序列平行偏序約束的問題 158
4.2.2 有樹型偏序約束的問題 164
4.2.3 有一般偏序約束的單位工時問題 166
4.3 有偏序約束的多臺機(jī)器問題 168
4.3.1 有樹型約束的平行機(jī)問題 168
4.3.2 有一般偏序約束的平行機(jī)問題 173
4.3.3 有序列平行偏序約束的流水作業(yè)問題 178
4.4 偏序集的鏈分解 182
4.4.1 Dilworth定理 182
4.4.2 *小機(jī)器數(shù)平行作業(yè)問題 184
4.5 跳躍數(shù)與調(diào)整時間排序 185
4.5.1 跳躍數(shù)問題 185
4.5.2 具有調(diào)整時間的排序問題 188
習(xí)題4 190
第5章 劃分結(jié)構(gòu)與難解性判定 192
5.1 計算復(fù)雜性的基本概念 192
5.1.1 多項式時間算法 192
5.1.2 P 類及NP類問題 195
5.1.3 NP-完全問題及NP-困難問題 196
5.1.4 基本的NP-完全及NP-困難問題 198
5.1.5 基本證明方法I:模擬變換法 200
5.1.6 基本證明方法II:強(qiáng)制壓迫法 203
5.2 常義NP-困難問題 206
5.2.1 以劃分問題為參照問題 206
5.2.2 以背包問題為參照問題 208
5.3 強(qiáng)NP-困難問題 210
5.3.1 純組合的參照問題 211
5.3.2 以3-劃分問題為參照問題 217
5.4 變尺度的不等式設(shè)計方法 222
5.4.1 單機(jī)總延誤問題 223
5.4.2 公共工期的加權(quán)總延誤問題 231
5.4.3 可中斷問題舉例 236
習(xí)題5 238
第6章 遞推結(jié)構(gòu)與隱枚舉搜索 241
6.1 動態(tài)規(guī)劃的遞推方法 241
6.1.1 *優(yōu)化原理 241
6.1.2 含參變量的序列極值方法 244
6.1.3 獨立決策過程的貪婪算法 245
6.1.4 不定期過程方法 246
6.1.5 同順序mn排序問題 251
6.2 偽多項式時間算法的建立 255
6.2.1 背包問題 255
6.2.2 單機(jī)加權(quán)延誤數(shù)問題 256
6.2.3 兩臺平行機(jī)的加權(quán)總完工時間問題 258
6.2.4 公共工期的加權(quán)總延誤問題 260
6.2.5 單機(jī)總延誤問題 262
6.3 分批排序問題的動態(tài)規(guī)劃方法 263
6.3.1 加權(quán)總完工時間的分批排序 263
6.3.2 **延遲的分批排序 267
6.3.3 延誤數(shù)的分批排序 271
6.4 分枝定界方法 273
6.4.1 *優(yōu)化原理的另一應(yīng)用 273
6.4.2 三臺機(jī)器的流水作業(yè)問題 276
6.5 啟發(fā)式算法 281
6.5.1 局部鄰域搜索法 281
6.5.2 汽輪機(jī)葉片排序問題 283
6.5.3 電網(wǎng)機(jī)組檢修調(diào)度 286
習(xí)題6 288
第7章 結(jié)構(gòu)松弛與近似算法 290
7.1 近似算法的逼近程度衡量 290
7.1.1 近似算法的性能比 290
7.1.2 性能比分析方法: 均值下界與關(guān)鍵工件 292
7.1.3 工件陸續(xù)到達(dá)情形的動態(tài)分析方法 299
7.1.4 線性規(guī)劃松弛方法 306
7.2 任意精度逼近理論 312
7.2.1 多項式時間逼近方案 312
7.2.2 偽多項式時間算法的舍入變換 315
7.2.3 運用枚舉搜索的逼近方法 322
7.2.4 運用劃分范圍的逼近方法 329
7.3 不可近似性分析 334
7.3.1 性能比的下界 334
7.3.2 排除PTAS的可能性 337
習(xí)題7 338
第8章 空間模式的序結(jié)構(gòu)優(yōu)化問題 340
8.1 遍歷性與巡回路線*優(yōu)化 340
8.1.1 遍歷性問題 340
8.1.2 運輸與車輛調(diào)度 341
8.1.3 中國郵遞員問題 344
8.1.4 車行路由問題 345
8.2 稀疏矩陣計算的順序優(yōu)化 349
8.2.1 稀疏矩陣的存儲方式 350
8.2.2 稀疏矩陣的消去與填充 354
8.2.3 圖的排序與標(biāo)號問題 356
8.2.4 研究課題概述 364
8.3 電路布線與順序嵌入 371
8.3.1 網(wǎng)絡(luò)嵌入的一般模型 371
8.3.2 線性順序嵌入 373
8.3.3 循環(huán)順序嵌入 375
8.3.4 二維網(wǎng)格嵌入 377
8.3.5 書式嵌入 379
8.4 走向更寬闊的時空優(yōu)化領(lǐng)域 380
8.4.1 序貫決策*優(yōu)化 380
8.4.2 DNA基因組序列排序問題 382
8.4.3 移位寄存器設(shè)計 385
8.4.4 頻道分配問題 386
8.4.5 競賽排名問題 387
8.4.6 從路嵌入到樹嵌入 388
習(xí)題8 391
參考文獻(xiàn) 393
時序優(yōu)化問題分類索引 406
I.單機(jī)模型 406
II.平行機(jī)模型 408
III.串聯(lián)機(jī)模型 409
IV.其他序結(jié)構(gòu)優(yōu)化模型 410
索引 412
《運籌與管理科學(xué)叢書》已出版書目 418
展開全部
書友推薦
- >
隨園食單
- >
莉莉和章魚
- >
人文閱讀與收藏·良友文學(xué)叢書:一天的工作
- >
經(jīng)典常談
- >
【精裝繪本】畫給孩子的中國神話
- >
推拿
- >
詩經(jīng)-先民的歌唱
- >
史學(xué)評論
本類暢銷
