首页 > 笔记 > 贪心理解

贪心理解


网上找到,感觉很有道理

贪心是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心则是每次可以找到最优的独立子问题。

贪心和动归不是互斥的,而是包含的,贪心更快,但约束更强,适应范围更小。动归和bfs的关系也是一样的。展开一点讲,在求解最优化问题时,有多个解。而求解的过程类似一个树,我们称之为求解树。

一般的求解树真的是一棵树,所以我们只能用bfs来搜索,顶多剪枝。有些特殊的求解树,中间很多结点是重合的,结点个数比所有搜索分支的个数少很多个数量级。这类问题较特殊,我们可以保存中间的搜索过程。而记忆化搜索和动态规划本质上就是一个东西,快就快在可以不用重复计算很多中间结果(所谓的最优子问题)。

还有一些特殊的求解树,更特殊,它们不止有很多重复结点,而且每次选择分支的时候,我们可以证明只要选择一个分支,这个分支的解就一定比其他选择更优。这类问题就是贪心了,所以bfs,dp,贪心三个方法都是解决最优化问题的方法,根据问题的不同,约束越大的问题可以用越快的方法,越慢的方法可以解决的问题越普适。

换一种思路动态规划的状态转移函数,可以抽象成这样一种函数:

$$f(x)=g(f(x_1), f(x_2), f(x_3), … f(x_n))$$

其中f就是我们说的独立问题,每个f都有一个唯一值,也就是没有后效性。

贪心也是这个函数,但可以证明:

$$f(xi) >= f(x_1|x_2|…|x_n)$$

那么我们就不用再去计算除了f(xi)以外的任何子状态了,所以就更快而标准的bfs,虽然也有f(x)=g(f(x1), f(x2), f(x3), … f(xn)但是因为对于任意的f(x),它的子问题f(xi)的输入状态xi都不同(换一种思路也可以说f(xi)在不同的路径下值都不同,本质上是我们怎么定义xi,到底是狭义的参数还是广义的状态),所以无法使用内存去换取时间,就只能去遍历所有状态了。


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×