• 周三. 12 月 11th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

动态规划 VS 贪心算法

admin

11 月 28, 2021
分治:将问题划分为互不相交的子问题递归求解。
动规:应用于子问题重叠的情况。求解过程中将子问题的解记录在表格中。
 
动态规划主要用于求解最优化问题。
求解步骤:
  1. 找到最优子结构。最优子结构性质:问题的最优解由相关的子问题的最优解组合而成,而这些子问题可以独立求解。
  2. 递归地定义最优解的值。
  3. 自底向上地计算最优解的值。
  4. 得到最优解。
ps:
* 子问题可以与原问题求解形式一样但规模更小。
* 自顶向下的递归方法:总是重复求解相同的子问题。
* 动态规划方法:仔细安排求解顺序,对每个子问题只求解一次,并将结果保存。
* 动态规划方法有两种等价实现:1. 带备忘的自顶向下法(递归求解)。2. 自底向上法(循环求解)。pps: 第一种其实就是记忆化搜索。
* 子结构要求子问题无关的。 
 
子问题图
可以看作自顶向下递归调用树的“简化版”。即原递归调用树种的相同子问题合并为子问题图中的单一节点。相同的所有边都从父节点指向子节点。
当思考动态规划问题时,要弄清楚涉及的子问题及子问题之间的依赖关系。
用点表示子问题,用有向边<x, y> 表示求解子问题 x 的最优解需要用到子问题 y 的最优解。
自底向上动态规划算法是按“逆拓扑序”来处理子问题图中的顶点。即:对于任何子问题,只有它以来的所有子问题均已求解完成,才会求解它。
 
适合用动态规划方法求解的最优化问题
1. 包含最优子结构。
2. 子问题重叠。
 
发掘最优子结构的通用模式
1.证明问题的最优解的第一个组成部分是做出一个选择。做出这个选择会产生一个或多个待解决的子问题。
2.对于给定问题,在其可能的第一步选择中,假定已知哪种选择会得到最优解。
3.给定可获得最优解的选择后,你确定这次选择会产生哪些子问题。
4.反证法可证明:作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解。
 
对于不同问题,最优子结构的不同体现在:
1.原问题的最优解中数涉及多少个子问题,以及
2.在确定最优解使用哪些子问题时,需要考虑多少种选择。
 
动态规划方法中,通常自底向上地使用最优子结构。即:先求子问题的最优解,然后求原问题的最优解。在求解原问题过程中,需要在涉及的子问题中做出选择,选择能得到原问题最优解的子问题。
 
贪心 VS 动态规划
贪心:先做出贪心的选择得到子问题(当时看是最优的选择),然后求解子问题。(先选择再求解子问题)
动规:求出每个子问题的最优解,然后选择能得到原问题最优解的子问题。(先求解子问题再选择)
 
子问题无关 VS 重叠子问题
子问题无关:最优子结构中要求子问题无关,即:每个子问题可以独立求解;同一个原问题的一个子问题的解不影响另一个子问题的解。
重叠子问题:向下求解原问题的最优解的过程中,会重复求解某同一个子问题。即:求解某个子问题的子子问题与其他子问题的子子问题一样。
e.g: 
 
 

发表回复