算法设计

　　这本《算法设计》教材具有以下突出的优点：1. 以各种算法设计技术（如贪心法、分治策略、动态规划、网络流、近似算法、随机算法等）为主线来组织素材，深入分析了各种设计技术的适用条件和局限性，突出了算法设计的思想和分析的基本原则，为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和方法.2. 本教材内容非常丰富，不但深入系统地阐述了算法设计与分析的理论，而且给出了大量的典型范例和参考文献.这些范例有的有重要的应用背景，有的与计算机科学技术的新发展密切相关.每个问题的叙述完全按照人们解决实际问题的思路进行：首先提出问题，然后考虑如何抽象出合理的数学模型，接着探讨有效的算法设计技术，给出算法的形式描述，并对算法的正确性和效率进行论证和分析，最后将有关的结果加以拓广.这不但介绍了算法设计与分析的系统方法，对如何设计正确的高效的算法有着重要指导意义，而且对如何面对实际问题从事科学研究也有着很好的启迪作用.3. 如何确定问题的计算难度，如何处理难解的问题是计算机科学工作者经常面临的问题.本教材用相当大的篇幅（第8~12章）比较系统全面地介绍NP完全性（以及PSPACE完全性）和处理NP难问题的方法.这些材料过去多以专著形式出现，在算法教材中通常只有蜻蜓点水式的少量介绍.本教材打破了这种惯例，按照“本科生可以接受的”设计目标把这些材料纳入本科生算法教材，这是极其有益的尝试，希望能促进国内算法教学水平的提升.4. 这本教材以算法为主线来处理算法与数据结构的关系.它先对所涉及的数据结构做了简要介绍，然后结合算法设计技术对如何选择数据结构进行了深入的分析.这种安排突出了算法设计的中心思想，避免了与数据结构课程在内容上的重复，更加适合于国内的教学计划.5. 本教材的叙述风格和选材非常适合教学.首先，内容由浅入深，由具体到抽象，从算法设计技术与分析方法自然过渡到计算复杂性理论.教师可以根据不同的教学要求选择适当的模块进行组合.其次，算法描述采用伪码，避免了繁琐的程序设计语言等实现细节，使学生能够站在更高的抽象层次上，加深对问题本身和算法设计思想的理解.第三，对与算法有关的数学基础做了适当的铺垫和介绍，有利于学生自学.第四，选配了大量难度适当的练习，并给出求解范例.本书适合作为计算机科学与技术专业本科高年级学生或研究生的算法设计与分析课程教材.对于在不同领域使用计算机求解实际问题的科学技术人员，它也是一本有益的参考书.本书包含13章，前7章主要涉及算法的设计与分析技术，后6章涉及计算复杂性以及相关的难解问题的算法设计技术.前7章由屈婉玲完成，后6章及后记由张立昂完成.在翻译过程中，我们按照中文书籍的编辑习惯对原著做了一点技术处理.比如加小节编号；把定理（原著中加灰底色的部分）与命题、事实、推论等不同的成分加以区分，并按章统一编号；按照中文汉语拼音字母顺序重新改写了关键词索引.由于时间与水平所限，译文中难免存在某些问题，恳请读者批评指正.

　　JonKleinberg是康奈尔大学计算机科学教授.1996年获麻省理工学院博士学位.荣获美国国家科学基金会（NSF）事业（Career）奖，海军研究局（（ONR）青年调查研究员（YoungInvestigator）奖，IBM杰出创新（OutstandingInnovation）奖，国家科学院主动研究（InitiativesinResearch）奖，Packard基金会和Sloan基金会的研究基金，以及康奈尔大学工程学院与计算机科学系的教学奖..Kleinberg的研究集中在算法，特别是与网络结构与信息.信息科学的应用.优化.数据挖掘以及计算生物学有关的算法.他在网络分析中使用集线器和授权的工作对形成最新一代因特网搜索引擎的基础起了很大的作用...EvaTardos是康奈尔大学计算机科学教授.1984年获匈牙利布达佩斯Eotos大学博士学位.她是美国艺术与科学院成员和ACM会员，荣获美国国家科学基金会（NSF）总统青年调查研究员（PresidentialYoungInvestigator）奖，Fulkerson奖，Guggenheim基金会，Packard基金会和Sloan基金会的研究基金，以及康奈尔大学工程学院与计算机科学系的教学奖.Tardos的研究兴趣集中在图和网络问题的算法设计与分析.她由于在网络流算法和网络问题的近似算法方面的工作而闻名.最近的工作主要是算法博弈论，这是一个与设计自私用户使用的系统和算法有关的新兴领域....

第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