求最优解算法学习

简要

本篇主要记录三种求最优解的算法:动态规划(dynamic programming),贪心算法和平摊分析.

动态规划

1.动态规划是通过组合子问题的解而解决整个问题的.分治法算法是指将问题划分成一些独立的子问题, 递归地求解各个子问题,然后合并子问题的解而得到原问题的解.与此不同,动态规划适用于子问题不是独立的情况,也就是各个子问题包含公共的子子问题.在这种情况下,若用分治法则会做许多不必要的工作,即重复地求解公共的子子问题.

动态规划算法的设计可以分为以下四个步骤:

1.描述最优解的结构 2.递归定义最优解的值 3.按自底向上的方式计算最优解的值 4.由计算出的结果构造一个最优解

能否运用动态规划方法的标志之一:一个问题的最优解包含了子问题的一个最优解.这个性质为最优子结构.

适合采用动态规划的最优化问题的两个要素:最优子结构和重叠子问题

贪心算法

1.贪心算法是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生出一个全局最优解.

2.贪心算法的每一次操作都对结果产生直接影响,而动态规划不是.贪心算法对每个子问题的解决方案做出选择,不能回退;动态规划则会根据之前的选择结果对当前进行选择,有回退功能.动态规划主要运用于二维或三维问题,而贪心一般是一维问题.

3.贪心算法要经过证明才能运用到算法中.

平摊分析

(未完-待续)