1.贪婪算法
一、
贪婪算法的优点是简单直观，易于实现。缺点是在解决问题的策略上目光短浅。这种算法每当遇到满足问题条件的候选解时就认为这个解是正确的，因此利用它解决的问题是十分有限的。
二、
利用贪婪算法解决的问题有以下几个特征：
1. 该问题至少有一个最优的解决方案
2. 随着问题的求解将建立另外两个集合，一个集合（a）有已经被选出的并符合问题要求的候选解组成，另一个集合（b）由己经被选出并不符合问题要求的候选解组成。
3. 集合a最终要包含问题的解答，在集合a中未出现解答时，问题的候选解集 合中至少还要剩余一个候选解。
2.分治法
一、
分治法是一种自上而下的算法，他把问题划分成一个个的子问题，通过对子问题的求解实现对原问题的求解。
分治法的应用范围很广泛，很多很复杂的问题都可以得到清晰快速的解决。但分治法更难理解，难以把握，除非对问题有精辟透彻的分析，否则难以用分治法解决问题。分治法的一个缺点是效率不高，如果对原问题进行不恰当的分解会进一步降低分治法的效率。总之分治法是一种技巧很高的算法。
二、
采用分治法对问题求解有一个通用的模板，描述如下：
function DivideToConquer (x) {
if (x 足够小且足够简单）{ 处理 x, return }
else{
把问题分解成子问题 x 1 , x 2 , x 3 ... x n
for（ int i = 0; i < n; i ++) {
处理 xi ，即 DivideToConquer (xi) ;
}
}
注意以上只是用分治法解决问题的一般模型
三、
利用分治法解决的问题有以下几个特征：
1. 整个问题可以分解为两个或多个较小的问题
2. 对每个子问题的求解类似于对整个问题的求解
3.如果子问题规模仍相当大而不可以对子问题方便求解，那么再对子问题应用分治法
3.动态规划
一、
动态规划是一种自底向上的设计方法，动态规划的思想方法是避免对同样的问题进行两次求解
二、
利用动态规划的思想解决的问题有以下几个特征：
1. 算法要解决大量重复的工作，计算大量重复的数值
2. 至少有一些新的数值可以通过已经计算出的数值组合出来
3. 问题要具有一定的规模，这样动态规划算法的好处才可以凸显出来
4. 使用分治法划分子问题时，子问题之间的关系界限不清，相互交叉。一个子问题的求解与多个已经解决的子问题有关
三、
动态规划法虽然可以提高程序运行的效率，但他是以牺牲算法的可读性为代价的，因为通常利用动态规划法写出的算法都比较复杂。动态规划法的另一个缺点是他有时不得不解决一些无关的子问题，因为动态规划无法知道这些子问题的解在之后是否会用到。而这两个缺点是分治法没有的。
动态规划法与分治法最大的区别在于动态规划法所划分的子问题之间联系比较密切，子问题与子问题的界限不是很清楚，往往在解决了一个子问题的同时也在某种程度上解决了另一个子问题。利用动态规划法处理问题产生的子问题的数目较多，而分治法所划分的子问题之间联系甚少，子问题与子问题之间界限清晰，解决子问题对解决另一子问题没有任何影响，相对产生的子问题数目较少。
网友评论