《算法设计》课后习题答案

这本《算法设计》教材具有以下突出的优点：

1. 以各种算法设计技术（如贪心法、分治策略、动态规划、网络流、近似算法、随机算法等）为主线来组织素材，深入分析了各种设计技术的适用条件和局限性，突出了算法设计的思想和分析的基本原则，为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和方法.

2. 本教材内容非常丰富，不但深入系统地阐述了算法设计与分析的理论，而且给出了大量的典型范例和参考文献.这些范例有的有重要的应用背景，有的与计算机科学技术的新发展密切相关.每个问题的叙述完全按照人们解决实际问题的思路进行：首先提出问题，然后考虑如何抽象出合理的数学模型，接着探讨有效的算法设计技术，给出算法的形式描述，并对算法的正确性和效率进行论证和分析，最后将有关的结果加以拓广.这不但介绍了算法设计与分析的系统方法，对如何设计正确的高效的算法有着重要指导意义，而且对如何面对实际问题从事科学研究也有着很好的启迪作用.

3. 如何确定问题的计算难度，如何处理难解的问题是计算机科学工作者经常面临的问题.本教材用相当大的篇幅（第8~12章）比较系统全面地介绍NP完全性（以及PSPACE完全性）和处理NP难问题的方法.这些材料过去多以专著形式出现，在算法教材中通常只有蜻蜓点水式的少量介绍.本教材打破了这种惯例，按照“本科生可以接受的”设计目标把这些材料纳入本科生算法教材，这是极其有益的尝试，希望能促进国内算法教学水平的提升.

4. 这本教材以算法为主线来处理算法与数据结构的关系.它先对所涉及的数据结构做了简要介绍，然后结合算法设计技术对如何选择数据结构进行了深入的分析.这种安排突出了算法设计的中心思想，避免了与数据结构课程在内容上的重复，更加适合于国内的教学计划.

5. 本教材的叙述风格和选材非常适合教学.首先，内容由浅入深，由具体到抽象，从算法设计技术与分析方法自然过渡到计算复杂性理论.教师可以根据不同的教学要求选择适当的模块进行组合.其次，算法描述采用伪码，避免了繁琐的程序设计语言等实现细节，使学生能够站在更高的抽象层次上，加深对问题本身和算法设计思想的理解.第三，对与算法有关的数学基础做了适当的铺垫和介绍，有利于学生自学.第四，选配了大量难度适当的练习，并给出求解范例.

本书适合作为计算机科学与技术专业本科高年级学生或研究生的算法设计与分析课程教材.对于在不同领域使用计算机求解实际问题的科学技术人员，它也是一本有益的参考书.

本书包含13章，前7章主要涉及算法的设计与分析技术，后6章涉及计算复杂性以及相关的难解问题的算法设计技术.前7章由屈婉玲完成，后6章及后记由张立昂完成.在翻译过程中，我们按照中文书籍的编辑习惯对原著做了一点技术处理.比如加小节编号；把定理（原著中加灰底色的部分）与命题、事实、推论等不同的成分加以区分，并按章统一编号；按照中文汉语拼音字母顺序重新改写了关键词索引.由于时间与水平所限，译文中难免存在某些问题，恳请读者批评指正.

目录

• 目录 CONTEHTS
• 第1章引言： 某些典型的问题1
• 1.1第一个问题：稳定匹配1
• 1.2五个典型问题9
• 带解答的练习14
• 练习16
• 注释和进一步的阅读20
• 第2章算法分析基础21
• 2.1计算可解性21
• 2.2增长的渐近阶25
• 2.3用表和数组实现稳定匹配算法31
• 2.4一般运行时间的概述34
• 2.5更复杂的数据结构：优先队列41
• 带解答的练习48
• 练习49
• 注释和进一步的阅读51
• 第3章图53
• 3.1基本定义与应用53
• 3.2图的连通性与图的遍历56
• 3.3用优先队列与栈实现图的遍历62
• 3.4二分性测试：宽度优先搜索的一个
• 应用68
• 3.5有向图中的连通性70
• 3.6有向无圈图与拓扑排序72
• 带解答的练习76
• 练习78
• 注释和进一步的阅读81
• 第4章贪心算法82
• 4.1区间调度： 贪心算法领先83
• 4.2最小延迟调度： 一个交换论证89
• 4.3最优高速缓存： 一个更复杂的交换
• 论证94
• 4.4一个图的最短路径98
• 4.5最小生成树问题101
• 4.6实现Kruskal算法： UnionFind数据
• 结构108
• 4.7聚类113
• 4.8Huffman码与数据压缩115
• *4.9最小费用有向树：一个多阶段贪心
• 算法126
• 带解答的练习131
• 练习134
• 注释和进一步的阅读145
• 第5章分治策略147
• 5.1第一个递推式：归并排序算法147
• 5.2更多的递推关系151
• 5.3计数逆序155
• 5.4找最接邻近的点对158
• 5.5整数乘法163
• 5.6卷积与快速傅里叶变换165
• 带解答的练习171
• 练习173
• 注释和进一步的阅读175
• 第6章动态规划177
• 6.1带权的区间调度： 一个递归过程177
• 6.2动态规划原理： 备忘录或者子问题
• 迭代182
• 6.3分段的最小二乘： 多重选择184
• 6.4子集和与背包： 加一个变量188
• 6.5RNA二级结构： 在区间上的动态
• 规划192
• 6.6序列比对196
• 6.7通过分治策略在线性空间的序列
• 比对201
• 6.8图中的最短路径206
• 6.9最短路径和距离向量协议211
• *6.10图中的负圈214
• 带解答的练习218
• 练习222
• 注释和进一步的阅读237
• 〖1〗 算 法 设 计〖1〗 目录第7章网络流239
• 7.1最大流问题与FordFulkerson
• 算法240
• 7.2网络中的最大流与最小割246
• 7.3选择好的增广路径250
• *7.4前向流推动最大流算法254
• 7.5第一个应用：二分匹配问题262
• 7.6在有向与无向图中的不交路径266
• 7.7对最大流问题的推广270
• 7.8调查设计274
• 7.9航线调度276
• 7.10图像分割280
• 7.11项目选择283
• 7.12棒球排除286
• *7.13进一步的方向：对匹配问题增加
• 费用289
• 带解答的练习294
• 练习297
• 注释和进一步的阅读318
• 第8章NP与计算的难解性320
• 8.1多项式时间归约321
• 8.2使用“零件”的归约：可满足性
• 问题325
• 8.3有效证书和NP的定义328
• 8.4NP完全问题330
• 8.5排序问题335
• 8.6划分问题340
• 8.7图着色343
• 8.8数值问题347
• 8.9coNP及NP的不对称性350
• 8.10难问题的部分分类352
• 带解答的练习354
• 练习357
• 注释和进一步的阅读372
• 第9章PSPACE：一个超出NP的
• 问题类3739.1PSPACE373
• 9.2PSPACE中的难问题374
• 9.3在多项式空间中解量化问题和博弈
• 问题376
• 9.4在多项式空间内求解规划问题378
• 9.5证明问题是PSPACE完全的382
• 带解答的练习384
• 练习386
• 注释和进一步的阅读387
• 第10章扩展易解性的界限388
• 10.1找小的顶点覆盖389
• 10.2在树上解NP难问题391
• 10.3圆弧集着色395
• *10.4图的树分解401
• *10.5构造树分解409
• 带解答的练习413
• 练习415
• 注释和进一步的阅读418
• 第11章近似算法419
• 11.1贪心算法与最优值的界限：负载均衡
• 问题419
• 11.2中心选址问题423
• 11.3集合覆盖：一般的贪心启发式
• 方法428
• 11.4定价法：顶点覆盖432
• 11.5用定价法最大化：不交路径
• 问题436
• 11.6线性规划与舍入：对顶点覆盖的
• 应用441
• *11.7再论负载均衡：一个更高级的LP
• 应用445
• 11.8任意好的近似：背包问题450
• 带解答的练习454
• 练习455
• 注释和进一步的阅读461
• 第12章局部搜索462
• 12.1最优化问题的地形图462
• 12.2Metropolis算法与模拟退火
• 算法466
• 12.3局部搜索对Hopfield神经网络的
• 应用469
• 12.4局部搜索对最大割近似的应用472
• 12.5选择邻居关系475
• 12.6用局部搜索分类476
• 12.7最佳响应动态过程与Nash
• 平衡点482
• 带解答的练习489
• 练习491
• 注释和进一步的阅读493
• 第13章随机算法494
• 13.1第一个应用：消除争用495
• 13.2求完全最小割498
• 13.3随机变量及其期望502
• 13.4关于MAX 3SAT的随机近似
• 算法506
• 13.5随机分治策略：求中位数与快速
• 排序509
• 13.6散列法：字典的随机实现514
• 13.7求最邻近点对：一个随机方法519
• 13.8随机超高速缓存525
• 13.9Chernoff界531
• 13.10负载均衡532
• 13.11包路由选择534
• 13.12背景：某些基本概率定义539
• 带解答的练习544
• 练习547
• 注释和进一步的阅读554
• 后记： 永不停止运行的算法556
• 索引563