算法在计算科学中扮演着重要角色。算法设计是计算机科学与技术专业的专业必修课，其目标是培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本技巧和方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，解决一些较综合的问题。

在学习本课程之前，学生已经学习了基本的数据结构知识，能熟练运用一门或多门编程语言，并具备了一定的编程经验。如何利用这些已学过的知识，对不同的实际问题设计出有效的算法，正是本课程所要达到的目的。

本课程特点是“问题模型化，求解算法化，设计最优化”，在掌握必要的算法设计技术和编程技巧的基础上，能够在实际工作中根据具体问题设计和优化算法。本书是针对这一特点并结合本课程组的教学经验编写的。

全书由10章构成，各章内容如下：

第1章 概论，介绍算法的概念、算法分析方法和基本的计算复杂性理论。

第2章 递归算法设计技术，介绍递归的概念、递推式的计算、递归算法设计方法和相关示例、递归算法到非递归算法的转化。

第3章 穷举法，介绍穷举法的特点、穷举法的基本应用示例和递归在穷举法中的应用示例。

第4章 分治法，介绍分治法的策略和求解过程，讨论采用分治法求解排序问题、查找问题、最大连续子序列和问题、大整数乘法问题和矩阵乘法问题的典型算法，并简要介绍了并行计算的概念。

第5章 贪心法，介绍贪心法的策略、求解过程和贪心法求解问题应具有的性质，讨论采用贪心法求解区间问题、背包问题、多机调度问题、哈夫曼编码和磁盘排序问题的典型算法。

第6章 动态规划，介绍动态规划的原理和求解步骤，讨论采用动态规划法求解整数拆分问题、最长公共子序列问题、0/1背包问题、最大连续子序列和问题和资源分配问题的典型算法。

第7章 回溯法，介绍解空间概念和回溯法算法框架，讨论采用回溯法求解0/1背包问题、子集和问题、排列和组合问题、迷宫问题、n皇后问题的典型算法。

第8章 分枝限界法，介绍分枝限界法的特点和设计思想，讨论采用队列式分枝限界法和采用优先队列式分枝限界法求解0/1背包问题的典型算法。

第9章 图搜索算法设计，介绍图的存储表示、图的两种基本的搜索算法，利用STL设计算法的基本知识，讨论了构造图最小生成树的两种算法、产生图最短路径的3种算法，并采用5种算法策略求解旅行推销员问题（TSP问题）以及求多段图的关键路径等典型算法； 最后介绍网络流的相关概念以及求最大流和最小费用最大流的算法。

第10章 几何计算，介绍几何计算中常用的矢量运算以及求解凸包问题、最近点对问题和最远点对问题的典型算法。

另有3个附录，附录A给出部分练习题的参考答案，附录B给出所有上机实验题的参考程序，附录C给出书中主要算法实现程序的清单。

本书的特点是内容丰富、由浅入深、循序渐进，在各章中，首先介绍一种算法设计策略的基本思想，然后从解决实际问题入手，由易到难地描述几个经典示例，使读者既能学到一些常用求解问题的算法，又能通过对算法策略的反复应用，掌握其核心思想，以便收到融会贯通之效。同时本书特别注重同一个问题的多种解法以及不同算法的比较，使读者更容易体会到每一种算法策略的设计特点和各自的优缺点。

书中绝大多数算法在VC++6.0中调试通过，本书的教学PPT和所有源程序可以从清华大学出版社网站免费下载。

本书的编写工作得到湖北省教育厅和武汉大学教学研究项目《计算机科学与技术专业课程体系改革》的大力支持，清华大学出版社魏江江主任也全力支持本书的编写工作，作者在此一并表示衷心感谢。

本书是课程组全体教师多年教学经验的总结和体现，尽管作者不遗余力，由于水平所限，仍存在错误和不足之处，敬请教师和同学们批评指正在此表示万分的感谢。

编者2015年3月