简述贪心,递归,动态规划,及分治算法之间的区别和联系
联系:都是问题求解之时的一种算法。
区别:
一、作用不同
1、贪心算法:把子问题的解局部最优解合成原来解问题的一个解。
2、递归算法:问题解法按递归算法实现。如Hanoi问题;数据的结构形式是按递归定义的。如二叉树、广义表等。
3、动态规划:动态规划算法通常用于求解具有某种最优性质的问题。
4、分治算法:可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。
二、方法不同
1、贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
2、递归算法:通过重复将问题分解为同类的子问题而解决问题。
3、动态规划:将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。
4、分治算法:将一个规模为N的问题分解为K个规模较小的子问题。
三、特点不同
1、贪心算法:根据题意选取一种量度标准。
2、递归算法:递归就是在过程或函数里调用自身。
3、动态规划:虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
4、分治算法:原问题可以分解为多个子问题;原问题在分解过程中,递归地求解子问题;在求解并得到各个子问题的解后。