第1章 算法设计与分析基础 1
1.1算法概述 2
1.1.1什么是算法 2
1.1.2学习算法的重要性 6
1.2问题的求解过程 6
1.2.1问题及问题的求解过程 6
1.2.2算法设计与算法表示 7
1.2.3算法确认和算法分析 8
1.3算法的复杂性分析 8
1.3.1算法评价的基本原则 9
1.3.2影响程序运行时间的因素 10
1.3.3算法复杂度 11
1.3.4使用程序步分析算法 14
1.3.5渐近表示法 15
1.4算法设计中常见的重要问题类型 18
1.4.1排序问题 18
1.4.2查找问题 19
1.4.3图问题 19
1.4.4组合问题 20
1.4.5几何问题 20
1.4.6数值问题 21
1.4.7其他常见问题 21
1.5常用的算法设计方法 22
1.5.1数值计算算法 23
1.5.2非数值计算算法 24
1.6小结 28
练习题 29
第2章 递归算法 31
2.1递归算法的思想 32
2.1.1递归算法的特性 32
2.1.2递归算法的执行过程 32
2.1.3递推关系 33
2.2递归法应用举例 37
2.2.1汉诺塔问题 37
2.2.2斐波那契数列问题 39
2.2.3八皇后问题 40
2.3典型问题的C＋＋程序 43
2.4小结 48
练习题 48
第3章 分治算法 50
3.1分治算法的思想 51
3.2排序问题中的分治算法 52
3.2.1归并排序 53
3.2.2快速排序 55
3.3查找问题中的分治算法 57
3.3.1折半查找 57
3.3.2选择问题 59
3.4组合问题中的分治算法 60
3.4.1最大子段和问题 60
3.4.2棋盘覆盖问题 62
3.5典型问题的C＋＋程序 64
3.6小结 70
练习题 71
第4章 贪心算法 72
4.1贪心算法的思想 73
4.1.1问题的提出 73
4.1.2贪心算法设计思想 73
4.1.3贪心算法的基本要素 74
4.1.4贪心算法的求解过程 74
4.2组合问题中的贪心算法 75
4.2.1背包问题 75
4.2.2多机调度问题 77
4.3图问题中的贪心算法 78
4.3.1单源最短路径问题 78
4.3.2最小代价生成树 80
4.4典型问题的C＋＋程序 84
4.5小结 92
练习题 92
第5章动态规划算法 94
5.1动态规划算法的思想 95
5.2查找问题中的动态规划算法 97
5.2.1最优二叉搜索树 97
5.2.2近似串匹配问题 100
5.3图问题中的动态规划算法 102
5.3.1多段图问题 102
5.3.2每对结点间的最短距离 105
5.4组合问题中的动态规划算法 108
5.4.1 0/1背包问题 108
5.4.2最长公共子序列 112
5.4.3流水作业调度 115
5.5典型问题的C＋＋程序 120
5.6小结 125
练习题 126
第6章回溯算法 128
6.1回溯算法的思想 129
6.1.1基本概念 129
6.1.2基本思路 130
6.1.3回溯算法的适用条件 132
6.1.4回溯算法的效率估计 132
6.2组合问题中的回溯算法 133
6.2.1装载问题 133
6.2.2 0/1背包问题 134
6.2.3 n皇后问题 136
6.2.4图的m着色问题 139
6.2.5子集和数问题 141
6.3图问题中的回溯算法 143
6.3.1深度优先搜索 143
6.3.2货郎（TSP）问题 143
6.3.3最大团（MCP）问题 145
6.3.4哈密顿环问题 146
6.4算法效率的影响因素及改进途径 148
6.4.1影响算法效率的因素 148
6.4.2回溯算法的改进途径 148
6.5典型问题的C＋＋程序 148
6.6小结 165
练习题 165
第7章分支限界算法 167
7.1分支限界算法的思想 168
7.2求最优解的分支限界算法 170
7.2.1 FIFO分支限界算法 171
7.2.2 LC分支限界算法 172
7.3组合问题中的分支限界算法 173
7.3.1 0/1背包问题 173
7.3.2带限期的作业排序 175
7.4图问题中的分支限界算法 179
7.4.1旅行商问题 179
7.4.2单源点最短路径问题 182
7.5典型问题的C＋＋程序 184
7.6小结 188
练习题 188
附录 实验指导 190
实验一 递归与分治算法 191
1.1实验目的与要求 191
1.2实验课时 191
1.3实验原理 191
1.4实验题目 191
1.5思考题 192
实验二 贪心算法 192
2.1实验目的与要求 192
2.2实验课时 192
2.3实验原理 192
2.4实验题目 193
2.5思考题 194
实验三 动态规划算法 194
3.1实验目的与要求 194
3.2实验课时 195
3.3实验原理 195
3.4实验题目 195
3.5思考题 197
实验四 回溯算法 197
4.1实验目的与要求 197
4.2实验课时 197
4.3实验原理 197
4.4实验题目 198
4.5思考题 199
实验五 分支限界算法 199
5.1实验目的与要求 199
5.2实验课时 200
5.3实验原理 200
5.4实验题目 200
5.5思考题 203
参考文献 204