算法设计技巧与分析 (2008 年度畅销榜NO.542 )

本书是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。 \r\n 本书结构简明，内容丰富，适合于作为计算机学科以及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课教材。同时也可作为从事算法研究的一本好的入门书。

第一部分 基本概念和算法导引\r\n 第1章 算法分析基本概念\r\n 第2章 数学预备知识\r\n 第3章 数据结构\r\n 第4章 堆和不相交集数据结构\r\n第二部分 基于递归的技术\r\n 第5章 归纳法\r\n 第6章 分治\r\n 第7章 动态规划\r\n第三部分 最先割技术\r\n 第8章 念心算法\r\n 第9章 图的遍历\r\n第四部 问题复杂性\r\n 第10章 NP完全问题\r\n 第11章 计算机杂性引论\r\n 第12章 下界\r\n第五部分 克服困难性\r\n 第13章 回溯法\r\n 第14章 随机算法\r\n 第15章 近似算法\r\n第六部分 域指定问题的迭代改进\r\n 第16章 网络流\r\n 第17章 匹配\r\n第七部分 计算几何技术\r\n 第18章 几何扫描\r\n 第19章 Voronoi图解\r\n参考文献

早在上世纪60年代初期，最初的电子计算机用户开始注意程序的执行性能，自那时起，计算机算法领域就很活跃了。在那个年代，计算机的有限资源也促进了有效算法的设计。在这个领域中进行了广泛的研究以后，出现了大量解决不同问题的有效算法。属于一定问题类的不同问题之间的相似性产生了一般算法设计的技术，已经证明，本书所强调的大多数算法设计技术在解决许多问题中是有用的。涵盖顺序算法设计中的最普遍技术是本书的一个尝试。对于每一种技术用如下方法表述：首先，叙述这种技术可以应用的情境；其次，提取出它的技术特点；第三，如果可能的话和其他技术进行比较；最后也是最重要的，通过把它应用在几个实际问题中来举例说明这种技术。 虽然本书的主题是算法设计技术，但也强调了算法设计中另一个重要组成部分：算法分析。本书对大多数给出的算法进行了详细的分析。第2章含有在算法分析中有用的大多数数学工具，第11章是计算复杂性领域的一个导论，而第12章论述了在求解各种问题时建立下界的基础，这几章在有效算法的设计中是不可缺少的。 本书论述的重点是设计技术的实际应用，每一种技术通过提供适量的求解某些问题的算法来说明，这些问题通常出现在科学和工程的许多应用中。 算法的表现方式是直截了当的，并且使用了与结构化程序设计语言的语法相类似的伪代码。例如fi-then-else、for和while结构。在需要时伪代码中混有说明性文字，用说明性文字描述算法的一部分当然是有益的，它可以使读者花费最少的功夫来了解算法思想。但是有时候用伪代码会使算法变得更容易和更形式化。例如，赋值语句的功能是，对于1≤i≤n中的所有i，用每个A{i}代替每个刀“)。用for'''end for结构，或者用简洁的说明性文字，都不会比这个式子说得更清楚和更容易。 本书分为七个部分，每部分由几章组成，每章包含具有共同特征或相同主题的那些设计技术。第一部分是为本书的余下部分做准备的，它同时提供了后面章节需要的背景材料。第二部分致力于递归设计技术的研究，它是极其重要的，因为它强调了计算机科学领域中的一个基本工具：递归。第三部分涉及了两个直观和自然的设计技术：贪心算法和图的遍历。第四部分是有关研究“对于一个给定问题，或者对这个问题提供一个有效算法，或者证明它是难解的”所需要的那些技术。这部分包含了NP完全性、计算复杂性和下界。在第五部分，表述了对付困难问题的技术，这些技术包括回溯、随机化以及在合理的时间内寻找合理的可接受的近似解。在第六部分利用两个受到高度关注的重要问题：寻找最大网络流和在无向图中寻找最大匹配来介绍迭代改进的概念，以得出越来越有效的算法。最后，第七部分是一个相对较新的领域——计算几何的导论。在第18章中，用这个领域中的重要问题为例子，叙述了广泛使用的几何扫描技术。在第19章中，论述了Voronoi图解这个通用的工具，并且讲述了它的一些应用。 本书拟用做算法设计和分析领域的教科书，它包含了可作为两学期算法课程的内容，第1章到第10章提供了大学三四年级算法课程的核心材料，有些内容可以跳过，如合并查找算法的平摊分析、稠图情况下最短路径和最小生成树的线性时间算法。教师可能会发现，加上后面章节的一些材料，如回溯、随机算法、近似算法或几何扫描是有用的。余下的材料可作为研究生的算法课程内容。 本书所要求的预备知识已经减到最少，仅需要离散数学和数据结构的基本知识。 感谢KingFahdUniversityofPetroleum&Minerals(KFUPM，皇家法哈德石油矿业大学)的支持和对手稿准备提供的方便。本书的编写得到KFUPM的项目ies／algodthm／182的资助。我还要感谢那些认真阅读手稿各部分并且提出许多有益建议的人，包括一些在KFUPM学习算法课程的本科生和研究生。特别感谢S.Albassam，H.Almuallim和S.Ghanta的有价值的评注。M.H.Alsuwaiyel