算法設計與分析（計算思維——神秘的算法）

第1 章 算法復雜性及其分析············································································.1
1.1 概述····································································································.1
1.2 RAM 模型·····························································································.4
1.3 算法及其復雜性測度···············································································10
1.4 RAM 模型的簡化····················································································15
1.4.1 直線式程序模型············································································15
1.4.2 判定樹模型··················································································17
1.4.3 算法描述語言···············································································18
本章小結·······································································································18
習題·············································································································19
第2 章 分治與遞歸··························································································23
2.1 階乘函數······························································································24
2.2 裴波那契（Fibonacci）數列·······································································25
2.3 組合問題······························································································25
2.4 漢諾塔問題···························································································25
2.5 二分查找······························································································27
2.6 大整數乘法···························································································29
2.7 矩陣乘積的Strassen 算法··········································································32
2.8 常見的遞歸形式·····················································································34
2.8.1 多變元遞歸··················································································34
2.8.2 多步遞歸·····················································································34
2.8.3 嵌套遞歸·····················································································34
2.8.4 聯立遞歸·····················································································35
2.9 遞歸方程求解的遞推求和方法···································································36
2.10 遞歸方程求解的生成函數求和方法····························································39
2.10 大數據中的分治和遞歸算法·····································································43
習題·············································································································44
第3 章 貪心算法······························································································47
3.1 找零錢問題···························································································47
3.2 銷售問題······························································································48
3.3 最小生成樹··························································································.51
3.4 單源最短路徑·······················································································.53
3.5 旅行商問題··························································································.55
3.6 機器任務調度問題·················································································.57
習題3 ·········································································································.60
第4 章 動態規劃····························································································.62
4.1 射氣球································································································.63
4.2 動態規劃在最短路徑中的應用··································································.64
4.3 矩陣連乘積問題····················································································.67
4.4 求最長公共子序列·················································································.70
4.5 凸多邊形的最優三角形剖分·····································································.72
4.5 多邊形遊戲··························································································.74
4.7 旅行商問題··························································································.77
4.8 總結···································································································.79
習題4 ·········································································································.80
第5 章 回溯法································································································.82
5.1 回溯法算法思想····················································································.82
5.1.1 回溯法的解題步驟·········································································.82
5.1.2 回溯法的算法框架·········································································.85
5.1.3 回溯法的復雜度分析······································································.86
§5.2 0-1 背包問題························································································.87
§5.3 裝載問題·····························································································.90
§5.3 子集和數問題·······················································································.94
§5.5 皇後問題·····························································································.96
§5.6 旅行售貨員問題····················································································.99
§5.7 運動員最佳匹配問題··············································································101
第6 章 分支限界法·························································································104
§6.1 分支限界法的基本思想···········································································104
6.1.1 分支限界法的解題步驟···································································104
6.1.2 分支限界法的復雜度分析································································106
6.1.3 分支限界法與回溯法的區別·····························································106
§6.2 0-1 背包問題························································································107
§6.3 最小耗費搜索法····················································································112
§6.3 旅行商售貨員問題·················································································115
§6.4 任務分配問題·······················································································118
目 錄
VII
第7 章 NP 完全問題·····················································································.121
§7.1 確定型圖靈機·····················································································.121
§7.2 圖靈機模型和RAM 模型的關系······························································.128
§7.3 非確定型圖靈機··················································································.130
§7.4 P 和NP 問題類····················································································.134
§7.5 NP 完全性和COOK 定理·······································································.136
§7.6 若幹NP 完全問題及證明·······································································.141
§7.7 Co-NP 類問題·····················································································.145
本章小結····································································································.146
習題··········································································································.147
第8 章 隨機化算法·······················································································.148
8.1 隨機化算法的基本思想···········································································.148
8.1.1 什麼是隨機化算法········································································.148
8.1.2 概率論公理·················································································.149
8.1.3 隨機化算法的分類········································································.151
8.2 隨機數································································································.153
8.2.1 線性同余生成器（LCGs）······························································.154
8.3 隨機化算法··························································································.156
8.3.1 數值隨機化算法···········································································.156
8.3.2 舍伍德算法·················································································.161
8.3.3 拉斯維加斯算法···········································································.169
8.3.4 蒙特卡羅算法··············································································.176
小結··········································································································.183
第9 章 智能算法···························································································.184
§9.1 遺傳算法···························································································.184
§9.1.1 遺傳算法基本思想······································································.184
§9.1.2 遺傳算法的實現·········································································.187
9.1.3 多目標遺傳算法···········································································.188
9.2 粒子群算法··························································································.190
9.2.1 粒子群算法基本思想·····································································.190
9.2.2 改進粒子群算法···········································································.193
9.3 分布估計算法·······················································································.195
9.3.1 分布估計算法基本思想··································································.195
9.3.2 基於EDA 的收斂性分析及多分布估計算法········································.195
9.4 差分進化算法·······················································································.196
9.4.1 差分進化算法基本思想··································································.196
9.4.2 差分進化算法流程及應用·······························································.199
算法設計與分析
VIII
9.5 模擬退火算法·························································································201
9.5.1 模擬退火算法基本思想···································································201
9.5.2 基於模擬退火算法的應用································································203
9.6 貪心算法·····························································································204
9.6.1 貪心算法基本思想·········································································204
9.6.2 基於貪心算法的旅行商問題·····························································206
9.7 禁忌搜索算法·························································································206
9.7.1 禁忌搜索算法基本思想···································································206
9.7.2 禁忌搜索算法的構成要素································································207
9.7.3 禁忌搜索算法的算法流程································································208
9.8 最小二乘法、A*算法···············································································209
9.8.1 最小二乘法基本思想······································································209
9.8.2 A*算法基本思想············································································210
9.9 神經網絡、深度學習與強化學習·································································211
9.9.1 神經網絡算法基本思想···································································211
9.9.2 深度學習基本思想·········································································215
9.9.3 強化學習基本思想·········································································216
小結···········································································································217