算法设计策略

这里介绍了一般的算法设计策略，阐述各方法的理论基础、主要思想及其适用范围。同时针对一些具体问题来讲述如何用这些一般的理论以及各种抽象数据类型对问题进行抽象描述，并用最有效的方式设计出解决问题的高效算法。它们将生动地再现计算机程序设计方法学的理论、抽象和设计三个过程，而且，通过对算法正确性的证明和复杂性的分析，深化对大问题的复杂性、概念和形式模型、效率和抽象的层次、折衷和结论等在计算机学科中重复出现的概念的理解。

必须强调指出，对于某些问题(如NP--完全问题)而言，用这里的方法和任何已知的方法都不可能设计出有效的算法。对于这种问题，人们常常考虑利用具体输入的某些特点来设计有效算法或设计求问题近似解的有效算法。这一部分内容我们将在高级专题中讨论。

在对有关算法进行形式描述时我们采用类Pascal的伪代码，并作了一些简化，略去不言而喻的一些说明，如函数、形参、变量等类型说明。

这里主要讨论的算法设计策略有：

• 递归技术 —— 最常用的算法设计思想，体现于许多优秀算法之中
• 分治法 —— 分而制之的算法思想，体现了一分为二的哲学思想
• 模拟法 —— 用计算机模拟实际场景，经常用于与概率有关的问题
• 贪心算法 —— 采用贪心策略的算法设计
• 状态空间搜索法 —— 被称为“万能算法”的算法设计策略
• 随机算法 —— 利用随机选择自适应地决定优先搜索的方向
• 动态规划 —— 常用的最优化问题解决方法