简要
本篇主要记录三种求最优解的算法:动态规划(dynamic programming),贪心算法和平摊分析.
动态规划
1.动态规划是通过组合子问题的解而解决整个问题的.分治法算法是指将问题划分成一些独立的子问题, 递归地求解各个子问题,然后合并子问题的解而得到原问题的解.与此不同,动态规划适用于子问题不是独立的情况,也就是各个子问题包含公共的子子问题.在这种情况下,若用分治法则会做许多不必要的工作,即重复地求解公共的子子问题.
动态规划算法的设计可以分为以下四个步骤:
1.描述最优解的结构
2.递归定义最优解的值
3.按自底向上的方式计算最优解的值
4.由计算出的结果构造一个最优解
能否运用动态规划方法的标志之一:一个问题的最优解包含了子问题的一个最优解.这个性质为最优子结构.
适合采用动态规划的最优化问题的两个要素:最优子结构和重叠子问题
贪心算法
1.贪心算法是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生出一个全局最优解.
2.贪心算法的每一次操作都对结果产生直接影响,而动态规划不是.贪心算法对每个子问题的解决方案做出选择,不能回退;动态规划则会根据之前的选择结果对当前进行选择,有回退功能.动态规划主要运用于二维或三维问题,而贪心一般是一维问题.
3.贪心算法要经过证明才能运用到算法中.
平摊分析
(未完-待续)