现在的位置: 首页 > 综合 > 正文

贪心算法 摘记

2018年01月19日 ⁄ 综合 ⁄ 共 1012字 ⁄ 字号 评论关闭

源自网络与书籍   自己学习 算法摘记

一、基本概念:
 
     所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解
     贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
  

二、贪心算法的基本思路:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解
    4.把子问题的解局部最优解合成原来解问题的一个解。
 

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。

这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 

对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 

3、贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质,这是2类算法的一个共同点。但是,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。

0-1背包问题:

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i

背包问题:

0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1 <= i <= n

2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。

问题二、 哈夫曼编码

问题三、单源最大路径

抱歉!评论已关闭.