目錄
第1章 算法概述 1
1.1 什么是算法 1
1.2 為什么學(xué)習(xí)算法 4
1.3 如何表示算法 5
1.4 如何評(píng)價(jià)算法 8
1.4.1 算法評(píng)價(jià)指標(biāo) 8
1.4.2 算法的漸進(jìn)時(shí)間復(fù)雜度 11
1.4.3 算法時(shí)間復(fù)雜度分析舉例 12
1.4.4 大O表示法的若干特點(diǎn) 13
1.4.5 算法空間復(fù)雜度分析方法 15
1.5 算法、程序、數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、軟件之間的關(guān)系 16
1.6 算法、計(jì)算機(jī)、人三者之間的關(guān)系 17
習(xí)題 18
第2章 經(jīng)典算法設(shè)計(jì)策略與方法 19
2.1 算法設(shè)計(jì)策略知識(shí)導(dǎo)圖 19
2.2 算法設(shè)計(jì)七步曲 20
2.3 迭代策略與算法設(shè)計(jì)方法 24
2.3.1 順序遞推算法策略與設(shè)計(jì)方法 25
2.3.2 倒序遞推算法策略與設(shè)計(jì)方法 28
2.4 蠻力策略與算法設(shè)計(jì)方法 30
2.5 分治策略與算法設(shè)計(jì)方法 37
2.6 遞歸策略與算法設(shè)計(jì)方法 45
2.7 貪心策略與算法設(shè)計(jì)方法 48
2.8 動(dòng)態(tài)規(guī)劃策略與算法設(shè)計(jì)方法 54
2.9 圖搜索策略與算法設(shè)計(jì)方法 63
2.9.1 廣度優(yōu)先搜索策略 64
2.9.2 深度優(yōu)先搜索策略 75
2.9.3 隊(duì)列制導(dǎo)搜索策略 81
2.9.4 棧制導(dǎo)搜索策略 89
2.9.5 優(yōu)先隊(duì)列分支限界搜索策略 92
習(xí)題 100
第3章 概率算法設(shè)計(jì)策略與方法 101
3.1 概率算法概述 101
3.2 數(shù)值概率算法 102
3.2.1 數(shù)值概率算法的基本思想 102
3.2.2 用隨機(jī)投點(diǎn)法計(jì)算圓周率 103
3.2.3 用隨機(jī)投點(diǎn)法計(jì)算定積分 106
3.3 蒙特卡羅算法 108
3.3.1 蒙特卡羅算法的基本思想 108
3.3.2 主元素存在性判定問題 109
3.3.3 素?cái)?shù)判定問題 112
3.4 舍伍德算法 117
3.4.1 舍伍德算法的基本思想 118
3.4.2 線性時(shí)間選擇問題 118
3.4.3 搜索有序表 122
3.5 拉斯維加斯算法 125
3.5.1 拉斯維加斯算法的基本思想 125
3.5.2 n皇后問題 126
3.5.3 整數(shù)因子分割問題 130
習(xí)題 132
第4章 計(jì)算復(fù)雜性理論初步 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
習(xí)題 141
第5章 近似算法設(shè)計(jì)策略與方法 142
5.1 近似算法策略設(shè)計(jì)與近似算法的性能 142
5.1.1 近似算法策略設(shè)計(jì)思想 142
5.1.2 近似算法的性能評(píng)價(jià) 143
5.2 頂點(diǎn)覆蓋問題的近似算法 145
5.3 旅行商問題近似算法 153
5.4 最小集合覆蓋問題的近似
算法 162
習(xí)題 169
第6章 智能算法設(shè)計(jì)策略與方法 170
6.1 啟發(fā)式搜索算法 170
6.1.1 爬山算法 170
6.1.2 模擬退火算法 174
6.2 群體智能算法 177
6.2.1 遺傳算法 177
6.2.2 蟻群算法 182
6.2.3 粒子群優(yōu)化算法 188
6.3 神經(jīng)網(wǎng)絡(luò)算法 193
6.3.1 深度學(xué)習(xí)算法 194
6.3.2 強(qiáng)化學(xué)習(xí)算法 201
習(xí)題 206
第7 章 算法策略綜合應(yīng)用與實(shí)踐 208
7.1 求解0-1背包問題 208
7.2 求解最短路徑問題的算法
綜合應(yīng)用與實(shí)踐 226
習(xí)題 245
參考文獻(xiàn) 247