目 錄
第1部分 算法基礎(chǔ)
第1章 算法概述 3
第2章 遞歸與分治法 9
2.1 基本思想 9
2.2 遞歸算法 10
2.3 二分搜索技術(shù) 12
2.4 合并排序 14
2.5 快速排序 19
2.6 線性時(shí)間選擇 22
第3章 動(dòng)態(tài)規(guī)劃 28
3.1 基本思想 28
3.2 矩陣連乘 29
3.3 最長(zhǎng)公共子序列 36
3.4 最優(yōu)二叉搜索樹(shù) 40
3.5 電路布線 49
3.6 0-1背包 54
第4章 貪心算法 61
4.1 基本思想 61
4.2 活動(dòng)安排問(wèn)題 61
4.3 背包問(wèn)題 64
4.4 哈夫曼編碼 67
4.5 單源最短路徑 71
4.6 最小生成樹(shù) 75
第5章 回溯法 84
5.1 基本思想 84
5.2 裝載問(wèn)題 84
5.2 批處理作業(yè)調(diào)度 93
5.3 n皇后問(wèn)題 97
5.4 最大團(tuán)問(wèn)題 105
5.5 圖的m著色問(wèn)題 112
第6章 分支限界法 117
6.1 基本思想 117
6.2 裝載問(wèn)題 117
6.3 0-1背包 123
6.4 旅行商問(wèn)題 131
第2部分 算法實(shí)驗(yàn)
第1章 算法概述實(shí)驗(yàn) 143
實(shí)驗(yàn)1 算法概述 143
第2章 遞歸與分治法實(shí)驗(yàn) 145
實(shí)驗(yàn)1 二分搜索術(shù) 145
實(shí)驗(yàn)2 合并排序算法 146
實(shí)驗(yàn)3 快速排序算法 147
實(shí)驗(yàn)4 線性時(shí)間選擇算法 149
第3章 動(dòng)態(tài)規(guī)劃實(shí)驗(yàn) 151
實(shí)驗(yàn)1 矩陣連乘問(wèn)題 151
實(shí)驗(yàn)2 最長(zhǎng)公共子序列問(wèn)題 152
實(shí)驗(yàn)3 最優(yōu)二叉搜索樹(shù)問(wèn)題 154
實(shí)驗(yàn)4 電路布線問(wèn)題 156
實(shí)驗(yàn)5 0-1背包問(wèn)題 157
第4章 貪心算法實(shí)驗(yàn) 160
實(shí)驗(yàn)1 活動(dòng)安排問(wèn)題 160
實(shí)驗(yàn)2 背包問(wèn)題 162
實(shí)驗(yàn)3 哈夫曼編碼問(wèn)題 163
實(shí)驗(yàn)4 單源最短路徑問(wèn)題 164
實(shí)驗(yàn)5 最小生成樹(shù)問(wèn)題 166
第5章 回溯法實(shí)驗(yàn) 168
實(shí)驗(yàn)1 裝載問(wèn)題 168
實(shí)驗(yàn)2 批處理作業(yè)調(diào)度問(wèn)題 169
實(shí)驗(yàn)3 n皇后問(wèn)題 171
實(shí)驗(yàn)4 最大團(tuán)問(wèn)題 173
實(shí)驗(yàn)5 圖的m著色問(wèn)題 175
第6章 分支限界法實(shí)驗(yàn) 177
實(shí)驗(yàn)1 裝載問(wèn)題 177
實(shí)驗(yàn)2 0-1背包問(wèn)題 178
實(shí)驗(yàn)3 旅行商問(wèn)題 180
參考文獻(xiàn) 182