首页 > 代码库 > 分治法、动态规划、贪心算法区别
分治法、动态规划、贪心算法区别
1.分治法
算法思想:将原问题划分成若干个规模较小而结构与原问题相似的子问题,递归的解决这些子问题,然后再合其结果,就得到原问题的解
特征:
- 该问题的规模缩小到一定的程度就很容易解决
- 该问题可以分解为若干个规模较小的相同问题,即改问题具有最优子结构性质
- 利用该问题分解出的子问题的解可以合并为该问题的解;
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题
2.动态规划
算法思想:与分治法相似,也是通过组合子问题的解而解决整个问题。区别是,动态规划适用于分解得到的子问题往往不是相互独立的。在这种情况下如果采用分治法,有些子问题会被重复计算多次,动态规划通过记录已解决的子问题,可以避免重复计算。
步骤:
- 描述最优解的结构
- 递归定义最优解的值
- 按自底向上的方式计算最优解的值
- 由计算出的结果构造一个最优解的值
要素:最优子结构、重叠子问题
动态规划通常用于求解最优化问题,在这类问题中可能有多个可行解,最终得到的是其中一个最优解。
3.贪心算法
算法思想:通过做一系列的选择来给出某一问题的最优解,对算法中的每一个决策点,做一个当时(看起来)是最优的选择。这种启发式的策略并不是总能产生出最优解。
步骤:
将优化问题转化成这样的一个问题,即先做出选择,在解决剩下的一个子问题
证明原问题总是有一个最优解是做贪心选择得到的,从而说明贪心选择的安全性
说明在作出贪心选择后,剩余的子问题具有这样一个性质。即如果将问题的最优解和我们所做的贪心选择联合起来,可以得出原问题的一个最优解。
要素:贪心选择性质、最优子结构性质
贪心选择性质:一个全局最优解可以通过局部最(贪心)选择来达到。
在动态规划中,每一步都要做出选择,但这些选择依赖于子问题的解。因此,解动态规划问题一般是自底向上,从小到大。在贪心算法中,我们所做的选择总是当前看似最佳的选择,然后再解决之后所出现的子问题。贪心算法所做的当前选择可能依赖于已作出的选择,但不依赖于做出的选择或子问题的解。贪心策略是自顶向下的,不断的将给定的问题规约为更小的问题。
分治法、动态规划、贪心算法区别
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。