精华内容
下载资源
问答
  • 贪心算法动态规划算法区别 两者所解决问题性质 动态规划 最优子结构 重叠子问题 贪心算法 最优子结构 贪心选择性质 相同点 动态规划贪心算法都满足最优子结构性质。 最优子结构 原问题的最优解解一定包括子...

    贪心算法与动态规划算法区别

    两者所解决问题性质

    动态规划

    • 最优子结构
    • 重叠子问题

    贪心算法

    • 最优子结构
    • 贪心选择性质

    相同点

    动态规划和贪心算法都满足最优子结构性质。

    最优子结构

    原问题的最优解解一定包括子问题的最优解

    证明(反证法)

    假设:原问题的最优解不包括子问题的最优解

    原问题可分为Q1和Q2两个子问题,他们的对应的可行解和最优解分别为a1、s1;a2、s2

    可知,原问题的解w1=s1+a2w_1=s_1+a_2,又因为w2=s1+s2w_2=s_1+s_2的解优于w1w_1

    所以假设错误,原命题正确

    不同点

    动态规划—重叠子问题

    动态规划是一种自底向上的求解方式,将子问题的解存储在表中,当出现重复子问题时,进行查表操作,避免重复的计算,极大提高算法的效率。是一种以空间换时间的方式,最典型个人感觉为斐波那契数列求解。

    贪心算法—贪心选择性质

    贪心算法是一种自顶向下的解决方案,通过当前阶段的评价准则,得到局部最优解,不断减小问题规模,得到最终解。是一种局部最优解组合替代整体最优解的方案。但有些时候计算得到的最终解并非整体最优解。


    因为博主写也只是在学习过程中做个人总结,所以难免可能会有错误的地方,欢迎大家一起交流、讨论。如果有幸解决了您的一些疑问,本人不胜感激!

    展开全文
  • 文章目录一,三种算法的基本思想分治法动态规划贪心算法二,三种算法的对比分治与动态规划。贪心与动态规划。三,三种算法的基本题型(不断更新中。。。)分治法动态规划贪心 一,三种算法的基本思想 分治法 分治法...

    一,三种算法的基本思想

    分治法

    分治法的基本思想是将一个规模为n的问题分解为k个规模较小的问题,这些子问题互相独立且与原问题相同(所以可以递归,递归地解这些子问题,然后将各个子问题的解合并得到原问题的解。

    动态规划

    动态规划算法和分治法相似的地方是它也是将待求解问题分成若干子问题,然后从这些子问题的解得到原问题的解。但与分治法不同的是,适合动态规划法解的题,经分解得到的子问题往往不是相互独立的若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。
      
      
    能用动态规划解的问题有如下三个性质:
     
     
     1. 最优子结构性质
      当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。
     
     
     2. 无后效性
      将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结这就是无后向性,又称为无后效性。

    3. 重叠子问题
      在用递归算法自顶向下解此问题时,每次产生的子问题并不总是新的子问题,**有些子问题被反复计算过多次。**动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其保存在一个表格中,当再次需要解此问题时,只是简单地用常数时间看一下结果。

    贪心算法

    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
      贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
      因此贪心算法具有最优子结构性质和贪心选择性质。
      1.最优子结构(同上)
      2.贪心选择性质
       所谓贪心的选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这也是贪心算法和动态规划算法的主要区别。在动态规划算法中,每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后,才能做出选择。而在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择正是由于这种区别,动态规划算法通常以自底向上的方式解决个子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式做出相继的贪心选择,每做一次贪心选择就将所求问题简化为规模更小的子问题。
       贪心算法的示例也有很多,比如数据结构中的Prim算法、Dijkstra算法和Huffman算法等。

    二,三种算法的对比

    分治与动态规划。

    分治和动态规划都是将问题分解为子问题,然后合并子问题的解得
    到原问题的解。但是不同的是,分治法分解出的子问题是不重叠的,因此分治法解决的问题不拥有重叠子问题,而动态规划解决的问题拥有重叠子问题。例如,归并排序和快速排序都
    是分别处理左序列和右序列,然后将左右序列的结果合并,过程中不出现重叠子问题,因此
    它们使用的都是分治法。另外,分治法解决的问题不一定是最优化问题,而动态规划解决的
    问题一定是最优化问题。

    贪心与动态规划。

    贪心和动态规划都要求原问题必须拥有最优子结构。

    二者的区别于,贪心法采用的计算方式类似千上面介绍的”自顶向下”,但是并不等待子问题求解完毕再选择使用哪一个,而是通过一种策略直接选择一个子问题去求解,没被选择的子问题就去求解了,直接抛弃。也就是说,它总是只在上一步选择的基础上继续选择,因此整个过以一种单链的流水方式进行,显然这种所谓“最优选择”的正确性需要用归纳法证明例对数塔问题而言,贪心法从最上层开始,每次选择左下和右下两个数字中较大的一个,一到最底层得到最后结果,显然这不一定可以得到最优解。而动态规划不管是采用自底向上是自顶向下的计算方式,都是从边界开始向上得到目标问题的解。也就是说,它总是会考所有子问题,并选择继承能得到最优结果的那个,对暂时没被继承的子问题,由千重叠子题的存在,后期可能会再次考虑它们,因此还有机会成为全局最优的一部分,不需要放弃所以贪心是一种壮士断腕的决策,只要进行了选择,就不后悔;动态规划则要看哪个选择到了最后,暂时的领先说明不了什么。

    三,三种算法的基本题型(不断更新中。。。)

    分治法

    输油管道问题
    邮局选址

    动态规划

    数塔问题
    最大连续字段和
    最长非递减子序列
    最长公共子序列
    最长回文串

    贪心

    展开全文
  • 动态规划贪心算法比较

    千次阅读 2018-05-13 09:21:22
    动态规划贪心算法比较动态规划动态规划一般分为线性动规、区域动规、树形动规、背包动规四类动态规划程序设计师是对解最优化问题的一种途径、一种方法,而不是一种特殊的算法,并不是一个标准的数学表达式和明确...

    动态规划和贪心算法比较

    动态规划:

    动态规划一般分为线性动规、区域动规、树形动规、背包动规四类

    动态规划程序设计师是对解最优化问题的一种途径、一种方法,而不是一种特殊的算法,并不是一个标准的数学表达式和明确清晰的解题方法。往往针对一种最优化问题,问题的性质不同,确定优化的条件也不同,所以就有不同的动态规划解题方法。

     

    基本思想:

    动态规划通常求解具有某种最优性质问题,找到最优解。动态规划与分支法类似,器基本思想也是将待求解问题分解若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

    与分治法不同的是,动态规划求解的问题,经分解得到的子问题不是相互独立的;而分治法求解的问题,分解得到的子问题数目太多,有些问题被重复计算量很多次。

    如果我们能够保存已解决的子问题的答案,而在需要时找到此答案,这样就可以避免大量的重复计算,节省时间。这样就可以使用一个表记录所有已解的子问题的答案,不管子问题以后是否被用到,只要他被计算过,就将其结果填入表汇总,这就是动态规划的基本思路。

    基本概念:

    多阶段决策问题:

    如果一类活动过程可以分为若干互相联系的阶段,在每一个阶段都需要作出决策(采取措施),一个阶段的决策会影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。

     

    经典例题有:

    1.硬币找零

      扩展1:单路取苹果

      扩展2:装配线调度

    2.字符串相似度/编辑距离(edit distance

      应用1:子串匹配

      应用2:最长公共子序列

    3.最长公共子序列(Longest Common Subsequence,lcs)

      扩展1:输出所有lcs

      扩展2:通过LCS获得最长递增自子序列

    4.最长递增子序列(Longest Increasing Subsequence,lis

      扩展:求解lis的加速

    5.最大连续子序列和/

      扩展1:正浮点数数组求最大连续子序列积

      扩展2:任意浮点数数组求最大连续子序列积

    6.矩阵链乘法

      扩展:矩阵链乘法的备忘录解法(伪码)

    7.0-1背包问题

    8.有代价的最短路径

    9.瓷砖覆盖(状态压缩DP

    10.工作量划分

    11.三路取苹果

     

    贪心算法:

    贪心算法greedy algorithm是指在对问题求解是,总是做出在当前最好的选择,也就是说,不从整体最优上加以考虑,他所做出仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广范的许多问题他也能产生整体最优解或者是整体最优解的近似解

    基本概念:

    贪心算法是一种对某些问题求最优解问题的更简单、更迅速的技术。使用此算法的特点是一步步地进行,对当前情况作出最优选择,,而不考虑各种可能的整体情况;

    它省去了为找最优解要穷尽所有可能而必须消耗的大量时间,采用自顶向上,以迭代的方法作出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过进一步贪心选择可得到问题的最优解,每一步能够保证局部最优,但是不一定是整体最优

    经典例题:

    0-1背包问题

    活动安排

    最优装船问题

    均分纸牌

    最大整数

    找零钱问题

    贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

    贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式

     

    动态规划和贪心算法的异同:

    动态规划和贪心算法都是一种递推算法

    均有局部最优解来推导全局最优解

    不同点:

    贪心算法:

    1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留。

    2.贪心法正确的条件是:每一步的最优解一定包含上一步的最优解。

     

    动态规划算法:

    1.全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解

    2.动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解

    3.边界条件:即最简单的,可以直接得出的局部最优解


    展开全文
  • 动态规划贪心算法的区别   (转自)http://hi.baidu.com/35661327/blog/item/d5463e17f1e8d011972b439c.html   动态规划贪心算法的区别 2009-07-27 13:18 动态规划贪心算法的区别...

    动态规划和贪心算法的区别


     

    (转自)http://hi.baidu.com/35661327/blog/item/d5463e17f1e8d011972b439c.html

     

    动态规划和贪心算法的区别
    2009-07-27 13:18
    动态规划和贪心算法的区别
    动态规划和贪心算法都是一种递推算法 
    均有局部最优解来推导全局最优解 

    不同点: 
    贪心算法: 
    1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留。 
    2.由(1)中的介绍,可以知道贪心法正确的条件是:每一步的最优解一定包含上一步的最优解。 

    动态规划算法: 
    1.全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 
    2.动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解 
    3.边界条件:即最简单的,可以直接得出的局部最优解
    ==============================================================================
    贪心算法与动态规划 
    贪心法的基本思路:   
        
    从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。   
    该算法存在问题:   
    1.   不能保证求得的最后解是最佳的;   
    2.   不能用来求最大或最小解问题;   
    3.   只能求满足某些约束条件的可行解的范围。实现该算法的过程:   
    从问题的某一初始解出发;
       
    while   能朝给定总目标前进一步   do   
    求出可行解的一个解元素;   
    由所有解元素组合成问题的一个可行解 

    贪心算法最经典的例子,给钱问题。   
    比如中国的货币,只看元,有1元2元5元10元20、50、100   
        
    如果我要16元,可以拿16个1元,8个2元,但是怎么最少呢?   
    如果用贪心算,就是我每一次拿那张可能拿的最大的。   
    比如16,我第一次拿20拿不起,拿10元,OK,剩下6元,再拿个5元,剩下1元   
    也就是3张   10、5、1。   
        
    每次拿能拿的最大的,就是贪心。   
        
    但是一定注意,贪心得到的并不是最优解,也就是说用贪心不一定是拿的最少的张数   
    贪心只能得到一个比较好的解,而且贪心算法很好想得到。   
    再注意,为什么我们的钱可以用贪心呢?因为我们国家的钱的大小设计,正好可以使得贪心算法算出来的是最优解(一般是个国家的钱币都应该这么设计)。如果设计成别的样子情况就不同了   
    比如某国的钱币分为   1元3元4元   
    如果要拿6元钱   怎么拿?贪心的话   先拿4   再拿两个1     一共3张钱   
    实际最优呢?   两张3元就够了   



    求最优解的问题,从根本上说是一种对解空间的遍历。最直接的暴力分析容易得到,最优解的解空间通常都是以指数阶增长,因此暴力穷举都是不可行的。
    最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,如上面的分析,这是不可行的。
    贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即,组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树(原问题作根),则,我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说,可以简单的用一个值(最优值)代表整个子树,而不用去求出这个子树所可能代表的所有值。
    动态规划方法代表了这一类问题的一般解法。我们自底向上(从叶子向根)构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。动态规划的代价就取决于可选择的数目(树的叉数)和子问题的的数目(树的节点数,或者是树的高度?)。
    贪心算法是动态规划方法的一个特例。贪心特在,可以证明,每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。通常这个值都是对于当前的问题情况下,显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。这样,与动态规划相比,它的代价只取决于子问题的数目,而选择数目总为1。
    展开全文
  • 动态规划 贪心算法分治法 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的问题,这些子问题互相独立且与原问题相同(所以可以递归)。递归地解这些子问题,然后将各个子问题的解合并得到原问题的解。...
  • 动态规划贪心算法的区别 2009-07-27 13:18 动态规划贪心算法的区别 动态规划贪心算法都是一种递推算法  均有局部最优解来推导全局最优解  不同点:  贪心算法:  1.贪心算法中,作出的...
  • 动态规划贪心算法都是一种递推算法,均由局部最优解来推导全局最优解 。 贪心算法 不断贪心地选取当前最优策略的算法设计方法。 1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导...
  • 动态规划贪心算法都是一种递推算法 均有局部最优解来推导全局最优解 不同点: 贪心算法: 1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解...
  • 动态规划贪心算法的区别

    万次阅读 2015-12-11 18:34:22
    本来这次是该总结动态规划的,但在学习过程中发现动态规划和上一节的贪心算法有很大联系,而在算法设计过程中主要是对两种算法的选择,所以决定这次以对比的方式做总结,既可以更深入地了解动态规划,又可以对贪心...
  • 相同点: 都具有最优子结构性质。 不同点: 贪心算法具有贪心选择性质; 动态规划算法具有子问题重叠性,子问题空间小;...可用贪心算法时,动态规划方法可能不适用; 可用动态规划方法时,贪心算法可能不适用。 ...
  • 一般实际生活中我们遇到的算法分为四类:  一>判定性问题  二>最优化问题  三>构造性问题  四>计算性问题 而今天所要总结的算法就是着重解决 最优化问题  ...动态规划 贪心算法 适用类型 通用问题
  • 贪心算法动态规划算法比较

    千次阅读 2018-08-09 16:22:20
    动态规划贪心算法都是一种递推算法 均用局部最优解来推导全局最优解 不同点: 贪心算法: 1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最...
  • 一般实际生活中我们遇到的算法分为四类:  一>判定性问题  二>最优化问题  三>构造性问题  四>计算性问题 而今天所要总结的算法就是着重解决 最优化问题  ...动态规划 贪心算法
  • 动态规划贪心算法

    千次阅读 2014-04-30 21:11:52
    动态规划 动态规划(dynamic programming)与fenzhi
  • 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱,希望找零的钞票尽可能少,零钱种类和数量限定 找钱问题满足最优子结构 最快找零(贪心):为得到最小的找零次数,每次最大程度低减少零额 ...
  • 贪心算法动态规划

    2016-09-10 23:31:53
    这是贪心算法可行的第一个基本要素,也是贪心算法动态规划算法的主要区别。在动态规划算法中,每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后,才能作出选择。而在贪心算法中,仅在当前状态...
  • 动态规划贪心算法的区别与联系

    万次阅读 多人点赞 2016-05-01 02:22:50
    ——证明了的贪心算法、没有证明的贪心算法动态规划、暴力搜索的区别。 今天来谈谈经典的算法设计思路问题,涉及搜索(Searching),动态规划(DP, Dynamic Programming),贪心算法(GA, Greedy Algorithm)……至于...
  • 利用动态规划求解最优问题的步骤: (1)证明该问题具有最优子结构性质; (2)根据最优子结构性质,写出最优值的递归表达式; (3)根据递归式,说明该问题具有重叠子结构性质; (4)采用自底向上的方式计算,...
  • 一般实际生活中我们遇到的算法分为四类: 一>判定性问题 二>最优化问题 三>构造性问题 四>计算性问题 ...动态规划 贪心算法 适用类型 通用问题 优化问题 优化问题
  • 这篇文章主要用来记录我对《算法导论》 贪心算法一章中的“活动选择问题”的动态规划求解和贪心算法求解 的思路和理解。 主要涉及到以下几个方面的内容: ①什么是活动选择问题---粗略提下,详细请参考《算法...
  • 动态规划贪心算法的区别 动态规划贪心算法都是一种递推算法  均有局部最优解来推导全局最优解  不同点:  贪心算法:  1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解...
  • 本来这次是该总结动态规划的,但在学习过程中发现动态规划和上一节的贪心算法有很大联系,而在算法设计过程中主要是对两种算法的选择,所以决定这次以对比的方式做总结,既可以更深入地了解动态规划,又可以对贪心...
  • 从最短路径谈动态规划贪心算法

    千次阅读 2018-01-20 23:58:24
    一言以蔽之:动态规划,从全局最优考虑;最短路径,从当前最优考虑。 先考虑下面的图 可以很容易地看出,如果使用贪心算法,从a到e的路线将是:a->b->c->d->e,而采用动态的规划的路线则是:a->c->e。 贪心...
  • 动态规划算法与贪心算法之课程安排问题 动态规划算法之课程安排 问题:教务处给某一个教室安排课程,有很多老师都想来这个教室教授他们各自的课。假如第ii位老师讲的第AiA_i门课程,课程开始时间SiS_i,结束时间为...
  • 动态规划贪心算法

    2020-02-22 08:39:47
    动态规划(Dynamic programming,简称DP);核心思想是把原问题分解成子问题进行求解,也就是分治的思想。 那么什么问题适合用动态规划呢?我们通过一个现实中的例子,来理解这个问题。大家可能在公司里面都有一定的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,644
精华内容 39,857
关键字:

动态规划贪心算法