简述贪心,递归,动态规划,及分治算法之间的区别和联系

 我来答
小溪趣谈电子数码
高粉答主

2020-07-02 · 专注解答各类电子数码疑问
小溪趣谈电子数码
采纳数:2103 获赞数:584799

向TA提问 私信TA
展开全部

联系:都是问题求解之时的一种算法。

区别:

一、作用不同

1、贪心算法:把子问题的解局部最优解合成原来解问题的一个解。

2、递归算法:问题解法按递归算法实现。如Hanoi问题;数据的结构形式是按递归定义的。如二叉树、广义表等。

3、动态规划:动态规划算法通常用于求解具有某种最优性质的问题。

4、分治算法:可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。

二、方法不同

1、贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。

2、递归算法:通过重复将问题分解为同类的子问题而解决问题。

3、动态规划:将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。

4、分治算法:将一个规模为N的问题分解为K个规模较小的子问题。

三、特点不同

1、贪心算法:根据题意选取一种量度标准。

2、递归算法:递归就是在过程或函数里调用自身。

3、动态规划:虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。

4、分治算法:原问题可以分解为多个子问题;原问题在分解过程中,递归地求解子问题;在求解并得到各个子问题的解后。

tangtangtrav
推荐于2017-10-09 · TA获得超过610个赞
知道小有建树答主
回答量:417
采纳率:0%
帮助的人:295万
展开全部
递归,简单的重复,计算量大。
分治,解决问题独立,分开计算,如其名。
动态规划算法通常以自底向上的方式解各子问题,
贪心算法则通常以自顶向下的方式进行;
动态规划能求出问题的最优解,贪心不能保证求出问题的最优解
本回答被提问者和网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式