Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 算法设计策略
发信站: 哈工大紫丁香 (2002年03月22日14:43:09 星期五), 站内信件

算法设计策略
这里介绍了一般的算法设计策略，阐述各方法的理论基础、主要思想及其适用范围。同
时针对一些具体问题来讲述如何用这些一般的理论以及各种抽象数据类型对问题进行抽
象描述，并用最有效的方式设计出解决问题的高效算法。它们将生动地再现计算机程序
设计方法学的理论、抽象和设计三个过程，而且，通过对算法正确性的证明和复杂性的
分析，深化对大问题的复杂性、概念和形式模型、效率和抽象的层次、折衷和结论等在
计算机学科中重复出现的概念的理解。
必须强调指出，对于某些问题(如NP--完全问题)而言，用这里的方法和任何已知的方法
都不可能设计出有效的算法。对于这种问题，人们常常考虑利用具体输入的某些特点来
设计有效算法或设计求问题近似解的有效算法。这一部分内容我们将在高级专题中讨论
。
在对有关算法进行形式描述时我们采用类Pascal的伪代码，并作了一些简化，略去不言
而喻的一些说明，如函数、形参、变量等类型说明。
这里主要讨论的算法设计策略有：
递归技术 —— 最常用的算法设计思想，体现于许多优秀算法之中
分治法 —— 分而制之的算法思想，体现了一分为二的哲学思想
模拟法 —— 用计算机模拟实际场景，经常用于与概率有关的问题
贪心算法 —— 采用贪心策略的算法设计
状态空间搜索法 —— 被称为“万能算法”的算法设计策略
随机算法 —— 利用随机选择自适应地决定优先搜索的方向
动态规划 —— 常用的最优化问题解决方法


--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]