算法分析與設計實踐
王小明,張立臣
商品描述
算法無處不在，算法思維已成為當今人類的基本思維方式之一。本書以經典算法為主線，首先系統介紹算法的基本概念、設計策略與設計方法，將課程思政元素融入算法知識體系，註重基礎性；然後介紹不確定問題求解中的經典概率算法和群體智能算法，強調高階性；最後介紹計算復雜性基本理論，並設計了復雜問題求解算法的工程實踐應用案例，突出挑戰性。
目錄大綱
目錄
第1章 算法概述 1
1.1 什麽是算法 1
1.2 為什麽學習算法 4
1.3 如何表示算法 5
1.4 如何評價算法 8
1.4.1 算法評價指標 8
1.4.2 算法的漸進時間復雜度 11
1.4.3 算法時間復雜度分析舉例 12
1.4.4 大O表示法的若乾特點 13
1.4.5 算法空間復雜度分析方法 15
1.5 算法、程序、數據、數據結構、軟件之間的關系 16
1.6 算法、電腦、人三者之間的關系 17
習題 18
第2章 經典算法設計策略與方法 19
2.1 算法設計策略知識導圖 19
2.2 算法設計七步曲 20
2.3 迭代策略與算法設計方法 24
2.3.1 順序遞推算法策略與設計方法 25
2.3.2 倒序遞推算法策略與設計方法 28
2.4 蠻力策略與算法設計方法 30
2.5 分治策略與算法設計方法 37
2.6 遞歸策略與算法設計方法 45
2.7 貪心策略與算法設計方法 48
2.8 動態規劃策略與算法設計方法 54
2.9 圖搜索策略與算法設計方法 63
2.9.1 廣度優先搜索策略 64
2.9.2 深度優先搜索策略 75
2.9.3 隊列制導搜索策略 81
2.9.4 棧制導搜索策略 89
2.9.5 優先隊列分支限界搜索策略 92
習題 100
第3章 概率算法設計策略與方法 101
3.1 概率算法概述 101
3.2 數值概率算法 102
3.2.1 數值概率算法的基本思想 102
3.2.2 用隨機投點法計算圓周率 103
3.2.3 用隨機投點法計算定積分 106
3.3 蒙特卡羅算法 108
3.3.1 蒙特卡羅算法的基本思想 108
3.3.2 主元素存在性判定問題 109
3.3.3 素數判定問題 112
3.4 舍伍德算法 117
3.4.1 舍伍德算法的基本思想 118
3.4.2 線性時間選擇問題 118
3.4.3 搜索有序表 122
3.5 拉斯維加斯算法 125
3.5.1 拉斯維加斯算法的基本思想 125
3.5.2 n皇後問題 126
3.5.3 整數因子分割問題 130
習題 132
第4章 計算復雜性理論初步 133
4.1 NP完全性 133
4.1.1 P和NP 133
4.1.2 NPC問題 134
4.1.3 常見的NPC問題 135
4.1.4 NPC問題證明 137
4.2 NP難與NP難問題 139
習題 141
第5章 近似算法設計策略與方法 142
5.1 近似算法策略設計與近似算法的性能 142
5.1.1 近似算法策略設計思想 142
5.1.2 近似算法的性能評價 143
5.2 頂點覆蓋問題的近似算法 145
5.3 旅行商問題近似算法 153
5.4 最小集合覆蓋問題的近似
算法 162
習題 169
第6章 智能算法設計策略與方法 170
6.1 啟發式搜索算法 170
6.1.1 爬山算法 170
6.1.2 模擬退火算法 174
6.2 群體智能算法 177
6.2.1 遺傳算法 177
6.2.2 蟻群算法 182
6.2.3 粒子群優化算法 188
6.3 神經網絡算法 193
6.3.1 深度學習算法 194
6.3.2 強化學習算法 201
習題 206
第7 章 算法策略綜合應用與實踐 208
7.1 求解0-1背包問題 208
7.2 求解最短路徑問題的算法
綜合應用與實踐 226
習題 245
參考文獻 247
第1章 算法概述 1
1.1 什麽是算法 1
1.2 為什麽學習算法 4
1.3 如何表示算法 5
1.4 如何評價算法 8
1.4.1 算法評價指標 8
1.4.2 算法的漸進時間復雜度 11
1.4.3 算法時間復雜度分析舉例 12
1.4.4 大O表示法的若乾特點 13
1.4.5 算法空間復雜度分析方法 15
1.5 算法、程序、數據、數據結構、軟件之間的關系 16
1.6 算法、電腦、人三者之間的關系 17
習題 18
第2章 經典算法設計策略與方法 19
2.1 算法設計策略知識導圖 19
2.2 算法設計七步曲 20
2.3 迭代策略與算法設計方法 24
2.3.1 順序遞推算法策略與設計方法 25
2.3.2 倒序遞推算法策略與設計方法 28
2.4 蠻力策略與算法設計方法 30
2.5 分治策略與算法設計方法 37
2.6 遞歸策略與算法設計方法 45
2.7 貪心策略與算法設計方法 48
2.8 動態規劃策略與算法設計方法 54
2.9 圖搜索策略與算法設計方法 63
2.9.1 廣度優先搜索策略 64
2.9.2 深度優先搜索策略 75
2.9.3 隊列制導搜索策略 81
2.9.4 棧制導搜索策略 89
2.9.5 優先隊列分支限界搜索策略 92
習題 100
第3章 概率算法設計策略與方法 101
3.1 概率算法概述 101
3.2 數值概率算法 102
3.2.1 數值概率算法的基本思想 102
3.2.2 用隨機投點法計算圓周率 103
3.2.3 用隨機投點法計算定積分 106
3.3 蒙特卡羅算法 108
3.3.1 蒙特卡羅算法的基本思想 108
3.3.2 主元素存在性判定問題 109
3.3.3 素數判定問題 112
3.4 舍伍德算法 117
3.4.1 舍伍德算法的基本思想 118
3.4.2 線性時間選擇問題 118
3.4.3 搜索有序表 122
3.5 拉斯維加斯算法 125
3.5.1 拉斯維加斯算法的基本思想 125
3.5.2 n皇後問題 126
3.5.3 整數因子分割問題 130
習題 132
第4章 計算復雜性理論初步 133
4.1 NP完全性 133
4.1.1 P和NP 133
4.1.2 NPC問題 134
4.1.3 常見的NPC問題 135
4.1.4 NPC問題證明 137
4.2 NP難與NP難問題 139
習題 141
第5章 近似算法設計策略與方法 142
5.1 近似算法策略設計與近似算法的性能 142
5.1.1 近似算法策略設計思想 142
5.1.2 近似算法的性能評價 143
5.2 頂點覆蓋問題的近似算法 145
5.3 旅行商問題近似算法 153
5.4 最小集合覆蓋問題的近似
算法 162
習題 169
第6章 智能算法設計策略與方法 170
6.1 啟發式搜索算法 170
6.1.1 爬山算法 170
6.1.2 模擬退火算法 174
6.2 群體智能算法 177
6.2.1 遺傳算法 177
6.2.2 蟻群算法 182
6.2.3 粒子群優化算法 188
6.3 神經網絡算法 193
6.3.1 深度學習算法 194
6.3.2 強化學習算法 201
習題 206
第7 章 算法策略綜合應用與實踐 208
7.1 求解0-1背包問題 208
7.2 求解最短路徑問題的算法
綜合應用與實踐 226
習題 245
參考文獻 247
