《離散最最佳化算法》是2012年科學出版社出版的圖書，作者是劉振宏、馬紹漢。
基本介紹
- 書名：離散最最佳化算法
- ISBN：9787030359490
- 頁數：233
- 定價：45.00元
- 出版時間：2012-11
內容簡介,編輯推薦,目錄,
內容簡介
《中創軟體叢書:離散最最佳化算法》共八章，前四章介紹最最佳化算法的經典內容，後四章包含了最最佳化算法近年來的發展，如逆最最佳化問題和近似算法。書中還講述了作者在組合最佳化領域所做的創造性的工作。為便於消化和理解書中的內容，每章末附有習題和參考文獻。
編輯推薦
《離散最最佳化算法》的目的是向廣大讀者介紹離散最最佳化的若干算法。算法是計算機能夠理解的語言，它是由有限個規則組成的有限長的序列。每個規則對應於一個或多個明確的不含歧義的操作。當作用於按問題要求輸入的有關數據後，則輸出問題的解，或者對此輸入無解。算法是對問題而言的，是用於求解問題的。因此，不同類型的問題就有不同的算法，即使同一個問題也可能有不同的算法。本書介紹最最佳化問題的算法，因為最最佳化問題是人們普遍關注的。
目錄
第一章 線性規劃
1.1 線性規劃的基本概念
1.2 單純形算法
1.3 線性規劃的對偶理論
1.4 對偶單純形算法
1.5 原始一對偶算法
1.6 單純形算法是非多項式算法
1.7 線性規劃問題的多項式時間算法
習題
參考文獻
第二章 整數線性規劃
2.1 引言
2.2 分數對偶割平面算法
2.3 整數對偶割平面算法
2.4 混合整數規劃的割平面算法
2.5 分支估界算法
2.6 0-1規劃的隱數法（implicit entimeration）
習題
參考文獻
第三章 網路規劃
3.1 圖的搜尋算法
3.1.1 無向圖的深探法（DFS）
3.1.2 無向圖的廣探法（BFS）
3.2 網路流模型及解的整數性
3.3 網路中的最短路
3.3.1 非負權網路的最短路算法
3.3.2 無負迴路網路中的最短路算法
3.3.3 所有點對之間的最短路算法
3.4 網路中的最大流
3.4.1 最大流的Ford-Fulkerson算法
3.4.2 最大流的Dinits算法
3.4.3 容量具有上下界的最大流算法
3.4.4 可行性定理及其組合套用
3.5 最小費用流
3.5.1 模型Ⅱ的相繼最短路算法
3.5.2 最小費用循環流的平均圈算法
習題
參考文獻
第四章 樹與擬陣
4.1 樹的基本性質
4.2 樹的中心與重心
4.3 無向網路中的最優生成樹
4.4 有向樹
4.5 擬陣的基本概念與性質
4.5.1 擬陣的定義與例子
4.5.2 擬陣的～些基本性質
4.6 擬陣與Greedy算法
4.7 擬陣的最大交
4.8 最大權交的算法
習題
參考文獻
第五章 動態規劃
5.1 網路中兩點間的最優路問題
5.2 用動態規劃方法解某些非線性規劃
5.3 用動態規劃方法解某些整數規劃
5.4 生產計畫與資源分配問題
5.4.1 生產計畫問題
5.4.2 資源分配問題
5.5 排序問題
5.5.1 排序問題
5.5.2 貨郎問題
5.6 矩陣鏈與公共子序列
5.6.1 矩陣鏈中矩陣相乘的順序問題
5.6.2 最長公共子序列問題
習題
參考文獻
第六章 逆最最佳化問題
6.1 逆線性規劃的一般模型
6.2 在範數l1下式（6.1.5）和式（6.1.6）的解
6.2.1 給定的可行解x0為0-1的解
6.2.2 在範數l1下模型LP2的解
6.3 在範數l∞下式（6.1.5）和式（6.1.6）的解
6.4 組合最佳化的逆問題一般模型
6.5 各種逆最最佳化問題的歸結
6.6 瓶頸擴張問題的一例
習題
參考文獻
第七章 算法、複雜性與NP-完全理論
7.1 問題、算法與複雜性
7.2 多項式算法P類和NP類
7.3 多項式變換與NPC類
7.4 NP-完全問題的證明舉例
7.5 關於NP-完全性的另一些概念
7.5.1 Co-NP類
7.5.2 NP-hard類
7.5.3 偽多項式算法與強NP-完全性
習題
參考文獻
第八章 近似算法及其分類
8.1 近似算法的基本概念
8.2 非空閒策略
8.3 Greedy算法
8.4 局部搜尋
8.5 基於線性規劃的近似算法
8.6 基於動態規劃的近似算法
8.7 絕對近似類
8.8 相對近似類
8.9 PTAS類與FPTAS類
8.10 隨機近似算法
8.11 近似算法的機率分析
習題
參考文獻
1.1 線性規劃的基本概念
1.2 單純形算法
1.3 線性規劃的對偶理論
1.4 對偶單純形算法
1.5 原始一對偶算法
1.6 單純形算法是非多項式算法
1.7 線性規劃問題的多項式時間算法
習題
參考文獻
第二章 整數線性規劃
2.1 引言
2.2 分數對偶割平面算法
2.3 整數對偶割平面算法
2.4 混合整數規劃的割平面算法
2.5 分支估界算法
2.6 0-1規劃的隱數法（implicit entimeration）
習題
參考文獻
第三章 網路規劃
3.1 圖的搜尋算法
3.1.1 無向圖的深探法（DFS）
3.1.2 無向圖的廣探法（BFS）
3.2 網路流模型及解的整數性
3.3 網路中的最短路
3.3.1 非負權網路的最短路算法
3.3.2 無負迴路網路中的最短路算法
3.3.3 所有點對之間的最短路算法
3.4 網路中的最大流
3.4.1 最大流的Ford-Fulkerson算法
3.4.2 最大流的Dinits算法
3.4.3 容量具有上下界的最大流算法
3.4.4 可行性定理及其組合套用
3.5 最小費用流
3.5.1 模型Ⅱ的相繼最短路算法
3.5.2 最小費用循環流的平均圈算法
習題
參考文獻
第四章 樹與擬陣
4.1 樹的基本性質
4.2 樹的中心與重心
4.3 無向網路中的最優生成樹
4.4 有向樹
4.5 擬陣的基本概念與性質
4.5.1 擬陣的定義與例子
4.5.2 擬陣的～些基本性質
4.6 擬陣與Greedy算法
4.7 擬陣的最大交
4.8 最大權交的算法
習題
參考文獻
第五章 動態規劃
5.1 網路中兩點間的最優路問題
5.2 用動態規劃方法解某些非線性規劃
5.3 用動態規劃方法解某些整數規劃
5.4 生產計畫與資源分配問題
5.4.1 生產計畫問題
5.4.2 資源分配問題
5.5 排序問題
5.5.1 排序問題
5.5.2 貨郎問題
5.6 矩陣鏈與公共子序列
5.6.1 矩陣鏈中矩陣相乘的順序問題
5.6.2 最長公共子序列問題
習題
參考文獻
第六章 逆最最佳化問題
6.1 逆線性規劃的一般模型
6.2 在範數l1下式（6.1.5）和式（6.1.6）的解
6.2.1 給定的可行解x0為0-1的解
6.2.2 在範數l1下模型LP2的解
6.3 在範數l∞下式（6.1.5）和式（6.1.6）的解
6.4 組合最佳化的逆問題一般模型
6.5 各種逆最最佳化問題的歸結
6.6 瓶頸擴張問題的一例
習題
參考文獻
第七章 算法、複雜性與NP-完全理論
7.1 問題、算法與複雜性
7.2 多項式算法P類和NP類
7.3 多項式變換與NPC類
7.4 NP-完全問題的證明舉例
7.5 關於NP-完全性的另一些概念
7.5.1 Co-NP類
7.5.2 NP-hard類
7.5.3 偽多項式算法與強NP-完全性
習題
參考文獻
第八章 近似算法及其分類
8.1 近似算法的基本概念
8.2 非空閒策略
8.3 Greedy算法
8.4 局部搜尋
8.5 基於線性規劃的近似算法
8.6 基於動態規劃的近似算法
8.7 絕對近似類
8.8 相對近似類
8.9 PTAS類與FPTAS類
8.10 隨機近似算法
8.11 近似算法的機率分析
習題
參考文獻
