哈飞扬 / 算法分析 / 分治法,动态规划,贪心算法比较

0 0

   

分治法,动态规划,贪心算法比较

2013-06-18  哈飞扬

一般实际生活中我们遇到的算法分为四类:

       一>判定性问题

       二>最优化问题

       三>构造性问题

       四>计算性问题

而今天所要总结的算法就是着重解决  最优化问题 

《算法之道》对三种算法进行了归纳总结,如下表所示:

标准分治

动态规划

贪心算法

适用类型

通用问题

优化问题

优化问题

子问题结构

每个子问题不同

很多子问题重复(不独立)

只有一个子问题             

最优子结构

不需要

必须满足

必须满足

子问题数

全部子问题都要解决

全部子问题都要解决

只要解决一个子问题

子问题在最优解里

全部

部分

部分

选择与求解次序

先选择后解决子问题

先解决子问题后选择

先选择后解决子问题

 

分治算法特征:

    1)规模如果很小,则很容易解决。//一般问题都能满足

    2)大问题可以分为若干规模小的相同问题。//前提

    3)利用子问题的解,可以合并成该问题的解。//关键

    4)分解出的各个子问题相互独立,子问题不再包含公共子问题。 //效率高低

【一】动态规划:

       依赖:依赖于有待做出的最优选择

       实质:就是分治思想和解决冗余(各子问题不相互独立,各子问题包含公共的子子问题,对每个子子问题只求解一次,将其结果保存在一张表中,避免重新计算)。

       自底向上(每一步,根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解)

       特征:动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值,而且同时求出了到中间状态的最优值。

       缺点:空间需求大。
 
       此算法的应用:装配线,矩阵乘法,最长公共子序列,构造最优的二叉查找树。

【二】贪心算法:

       依赖:依赖于当前已经做出的所有选择(所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生一个全局最优解)。

       自顶向下(就是每一步,根据策略得到一个当前最优解。传递到下一步,从而保证每一步都是选择当前最优的。最后得到结果)
 
       对许多优化问题来说,采用动态规划方法决定最佳选择有点“杀猪用牛刀”了。
 
       贪心算法对大多数优化问题来说能产生最优解,但也不一定总是这样,(所以再用贪心算法之前,先考虑动态规划方法,然后证明总能用贪心得到最优解)。
 
       此算法的应用:最小生成树,最短路径,数据压缩--哈夫曼编码

【三】分治算法:

        实质:递归求解(各子问题要互相独立)

        缺点:如果子问题不独立,需要重复求公共子问题。
 

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多