贪心算法是动态规划算法的一个特例,对于某些问题来说,我们不必像动态规划算法那样考虑所有的情况,只需每一步找局部最有解即可,这样最终会得到全局最有解。

能用贪心算法求解的问题一定可以用动态规划求解,问题的难点在于什么情况下可以用贪心算法。

活动选择问题

假设现在有n个活动,它们共同竞争同一个教室,我们知道它们的开始时间和结束时间,我们想尽可能安排最多的活动。

活动编号 1 2 3 4 5 6 7 8 9 10
开始时间 1 3 0 5 3 5 6 8 8 2
结束时间 4 5 6 7 9 9 10 11 12 14

动态规划

使用动态规划的思想先写出原问题的最优子问题的递推式,设c[ i , j ]表示包含活动i~j的最优解,则其可以递归的表示为更小的子集。

c[ i , j ] = c [ i , k ] + c [ k , j ] + 1

其中k可以通过遍历的方式确定,即:

c [ i , j ] = \left\{ \begin{array} { ll} 
{ 0 } &{若S _ { i j } = \varnothing}\\ 
{ \max _ { k \in S_{ij} } \{ c [ i , k ] + c [ k , j ] + 1 \} }&{若S _ { i j } \neq \varnothing} \end{array} \right.

然后根据这个递推式写出程序。

贪心算法

从直观上,应该每次选择最早结束的活动,以便留更多的时间给余下的活动,这样的话总体参与的活动数量是最多的。所以只需不停的选择最终结束的活动,直到没有活动可选,这就是贪心算法。

与动态规划的不同点是,贪心算法没有考虑不是最早结束的活动的组合。

贪心算法解决的问题,类似于攒钱,每一步都是在前一步的基础上慢慢建立起来的,所以一开始领先,会一直保持领先,每次只需找到局部最优解,最终会是全局最优解。

动态规划算法解决的问题,像是走迷宫,可能一开始看似走了一条阳光大道,可能下一条路就是泥泞的沼泽。而一开始看似走了一条山路,可能翻过这座山就到达了终点。所以动态规划算法必须考虑所有的情况,以找出全局最优的线路。

从上面的比喻可以看出,适用于动态规划的问题,每一步的选择会影响下一步的选项,而适用贪心算法的问题则不存在不同的选择会影响下一步选项的情况。

posted @ 2019-02-22 11:08:30
评论加载中...

发表评论