为了适应培养我国21世纪计算机各类人才的需要,结合我国高等学校教育工作的现状,立足培养学生能跟上国际计算机科学技术的发展水平,更新教学内容和教学方法,提高教学质量,本书以算法设计策略为知识单元,系统地介绍计算机算法的设计方法与分析技巧,以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。另有配套的《算法设计与分析(第4版)习题解答》,对本书的全部习题做了详尽的解答。
本书内容丰富,观点新颖,理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材,而且也适合广大工程技术人员和自学读者学习参考。

第5章回溯法回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。回溯法求问题的所有解时,要回溯到根,且根结点的所有子树都被搜索遍才结束。回溯法求问题的一个解时,只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法,它适用于求解组合数较大的问题。
5.1回溯法的算法框架[*4/5]5.1.1问题的解空间用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少应包含问题的一个(*优)解。例如,对于有n种可选择物品的01背包问题,其解空间由长度为n的01向量组成。该解空间包含对变量的所有01赋值。当n=3时,其解空间是:
{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}
定义了问���的解空间后,还应将解空间很好地组织起来,使得能用回溯法方便地搜索整个解空间。通常将解空间组织成树或图的形式。
例如,对于n=3时的01背包问题,可用完全二叉树表示其解空间,如图51所示。
图5101背包问题的解空间树
解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶的任一路径表示解空间中的一个元素。例如,从根结点到结点H的路径相应于解空间中元素(1,1,1)。5.1.2回溯法的基本思想
确定了解空间的组织结构后,回溯法从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。在当前扩展结点处,搜索向纵深方向移至一个新结点。这个新结点成为新的活结点,并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至*近的活结点处,并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。
例如,对于n=3时的01背包问题,考虑下面的具体实例: w=[16,15,15],p=[45,25,25],c=30。从图51的根结点开始搜索解空间。开始时,根结点是**的活结点,也是当前扩展结点。在这个扩展结点处,可以沿纵深方向移至结点B或结点C。假设选择先移至结点B。此时,结点A和结点B是活结点,结点B成为当前扩展结点。由于选取了w1,故在结点B处剩余背包容量是r=14,获取的价值为45。从结点B处,可以移至结点D或E。由于移至结点D至少需要w2=15的背包容量,而现在仅有的背包容量是r=14,故移至结点D导致不可行解。搜索至结点E不需要背包容量,因而是可行的。从而选择移至结点E。此时,E成为新的扩展结点,结点A,B和E是活结点。在结点E处,r=14,获取的价值为45。从结点E处,可以向纵深移至结点J或K。移至结点J导致不可行解,而移向结点K是可行的,于是移向结点K,它成为新的扩展结点。由于结点K是叶结点,故得到一个可行解。这个解相应的价值为45。xi的取值由根结点到叶结点K的路径**确定,即x=(1,0,0)。由于在结点K处已不能再向纵深扩展,所以结点K成为死结点。返回到结点E处。此时在结点E处也没有可扩展的结点,它也成为死结点。
回溯法第 5 章算法设计与分析(第4版)接下来又返回到结点B处。结点B同样也成为死结点,从而结点A再次成为当前扩展结点。结点A还可继续扩展,从而到达结点C。此时,r=30,获取的价值为0。从结点C可移向结点F或G。假设移至结点F,它成为新的扩展结点。结点A,C和F是活结点。在结点F处,r=15,获取的价值为25。从结点F,向纵深移至结点L处,此时,r=0,获取的价值为50。由于L是叶结点,而且是迄今为止找到的获取价值*高的可行解,因此记录这个可行解。结点L不可扩展,又返回到结点F处。按此方式继续搜索,可搜索遍整个解空间。搜索结束后找到的*好解是相应01背包问题的*优解。
再看一个用回溯法解旅行售货员问题的例子。
旅行售货员问题的提法是: 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,*后回到驻地的路线,使总的路程(或总旅费)*短(或*小)。
问题刚提出时,不少人都认为这个问题很简单。后来,在实践中才逐步认识到,这个问题只是叙述简单,易于理解,而其计算复杂性却是问题输入规模的指数函数,属于相当难解的问题之一。事实上,它是NP完全问题。这个问题可以用图论语言形式描述。
设G=(V,E)是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题要在图G中找出费用*小的周游路线。
图52是一个4顶点无向带权图。顶点序列1,2,4,3,1;1,3,2,4,1和1,4,3,2,1是该图中3条不同的周游路线。
旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图G的一条周游路线。图53是当n=4时解空间的示例。其中,从根结点A到叶结点L的路径上边的标号组成一条周游路线1,2,3,4,1。从根结点到叶结点O的路径表示周游路线1,3,4,2,1。图G的每一条周游路线都恰好对应于解空间树中一条从根结点到叶结点的路径。因此,解空间树中叶结点个数为(n-1)!。

目录CONTENTS
第1章算法引论1
1.1算法与程序1
1.2表达算法的抽象机制1
1.3描述算法3
1.4算法复杂性分析10
小结13
习题14
第2章递归与分治策略16
2.1递归的概念16
2.2分治法的基本思想21
2.3二分搜索技术23
2.4大整数的乘法23
2.5Strassen矩阵乘法24
2.6棋盘覆盖26
2.7合并排序28
2.8快速排序30
2.9线性时间选择33
2.10*接近点对问题35
2.11循环赛日程表43
小结44
习题44
第3章动态规划50
3.1矩阵连乘问题50
3.2动态规划算法的基本要素55
3.3*长公共子序列58
3.4凸多边形*优三角剖分61
3.5多边形游戏64
3.6图像压缩67
3.7电路布线69
3.8流水作业调度72
3.90\|1背包问题75
3.10*优二叉搜索树80
小结83
习题83
目录算法设计与分析(第4版)第4章贪心算法85
4.1活动安排问题85
4.2贪心算法的基本要素88
4.2.1贪心选择性质88
4.2.2*优子结构性质89
4.2.3贪心算法与动态规划算法的差异89
4.3*优装载91
4.4哈夫曼编码92
4.4.1前缀码93
4.4.2构造哈夫曼编码93
4.4.3哈夫曼算法的正确性95
4.5单源*短路径96
4.5.1算法基本思想97
4.5.2算法的正确性和计算复杂性98
4.6*小生成树99
4.6.1*小生成树性质99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多机调度问题104
4.8贪心算法的理论基础106
4.8.1拟阵106
4.8.2带权拟阵的贪心算法107
4.8.3任务时间表问题109
小结113
习题113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1问题的解空间115
5.1.2回溯法的基本思想116
5.1.3递归回溯117
5.1.4迭代回溯118
5.1.5子集树与排列树119
5.2装载问题120
5.3批处理作业调度126
5.4符号三角形问题128
5.5n后问题130
5.601背包问题133
5.7*大团问题136
5.8图的m着色问题138
5.9旅行售货员问题140
5.10圆排列问题142
5.11电路板排列问题144
5.12连续邮资问题147
5.13回溯法的效率分析149
小结152
习题152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2单源*短路径问题156
6.3装载问题158
6.4布线问题166
6.501背包问题170
6.6*大团问题175
6.7旅行售货员问题178
6.8电路板排列问题181
6.9批处理作业调度184
小结189
习题189
第7章概率算法190
7.1随机数191
7.2数值概率算法193
7.2.1用随机投点法计算π值193
7.2.2计算定积分194
7.2.3解非线性方程组195
7.3舍伍德算法197
7.3.1线性时间选择算法198
7.3.2跳跃表200
7.4拉斯维加斯算法205
7.4.1n后问题206
7.4.2整数因子分解209
7.5蒙特卡罗算法211
7.5.1蒙特卡罗算法的基本思想211
7.5.2主元素问题213
7.5.3素数测试214
小结217
习题217
第8章NP完全性理论与近似算法221
8.1P类与NP类问题221
8.1.1非确定性图灵机222
8.1.2P类与NP类语言222
8.1.3多项式时间验证224
8.2NP完全问题225
8.2.1多项式时间变换225
8.2.2Cook定理226
8.3一些典型的NP完全问题229
8.3.1合取范式的可满足性问题230
8.3.23元合取范式的可满足性问题230
8.3.3团问题231
8.3.4顶点覆盖问题232
8.3.5子集和问题233
8.3.6哈密顿回路问题235
8.3.7旅行售货员问题238
8.4近似算法的性能238
8.5顶点覆盖问题的近似算法240
8.6旅行售货员问题近似算法241
8.6.1具有三角不等式性质的旅行售货员问题242
8.6.2一般的旅行售货员问题243
8.7集合覆盖问题的近似算法244
8.8子集和问题的近似算法246
8.8.1子集和问题的指数时间算法247
8.8.2子集和问题的完全多项式时间近似格式247
小结250
习题250
第9章串与序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索与AC自动机260
9.2后缀数组与*长公共子串266
9.2.1后缀数组的基本概念266
9.2.2构造后缀数组的倍前缀算法267
9.2.3构造后缀数组的DC3分治法270
9.2.4*长公共前缀数组与*长公共扩展算法274
9.2.5*长公共子串算法276
9.3序列比较算法277
9.3.1编辑距离算法277
9.3.2*长公共单调子序列280
9.3.3有约束*长公共子序列281
小结284
习题285
第10章算法优化策略288
10.1算法设计策略的比较与选择288
10.1.1*大子段和问题的简单算法288
10.1.2*大子段和问题的分治算法289
10.1.3*大子段和问题的动态规划算法291
10.1.4*大子段和问题与动态规划算法的推广291
10.2动态规划加速原理294
10.2.1货物储运问题294
10.2.2算法及其优化295
10.3问题的算法特征298
10.3.1贪心策略298
10.3.2对贪心策略的改进299
10.3.3算法三部曲299
10.3.4算法实现300
10.3.5算法复杂性305
10.4优化数据结构306
10.4.1带权区间*短路问题306
10.4.2算法设计思想306
10.4.3算法实现方案308
10.4.4并查集311
10.4.5可并优先队列314
10.5优化搜索策略318
小结324
习题324
第11章在线算法设计325
11.1在线算法设计的基本概念325
11.2页调度问题327
11.3势函数分析329
11.4k服务问题330
11.4.1竞争比的下界330
11.4.2平衡算法331
11.4.3对称移动算法332
11.5Steiner树问题334
11.6在线任务调度336
11.7负载平衡337
小结338
习题338
词汇索引340
参考文献345