个人技术笔记

动态规划、分治法与贪心算法的区别

发布时间：2015-11-19  栏目：软件算法  评论：0 Comments

分治法与动态规划的相同点：
分治法与动态规划，二者要求原问题具有最优子结构，都是将问题分而治之分解成若干个规模较小的子问题；

不同点：
动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分；
算法的应用：装配线，矩阵乘法，最长公共子序列，构造最优的二叉树
分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。

例如：在求解斐波那契数列过程中，求解fibonacci(5)求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)时,需要求解fibonacci(3).
在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),即使求解fibonacci(4)子问题的时候已经求解过,也就是说,求解了二次子问题fibonacci(3).

贪心算法：依赖于当前已经做出的所有选择，采用自顶向下(每一步根据策略得到当前一个最优解，保证每一步都是选择当前最优的)的解决方法。
贪心算法的应用：最小生成树，最短路径，数据压缩–哈夫曼编码

动态规划例题：
m*n的矩阵，求从左下角点到右上角点所有路径总数

留下评论

You must be logged in to post a comment.