搜索
动态规划和贪心算法的区别动态规划法的基本思路：动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。此算法常用于求解某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案，消除递归过程中产生的大量重叠子问题。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。贪心算法的基本思想：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，贪心算法所得出的解是一系列局部最优的选择。把求解的问题分成若干个子问题，对每一子问题求解，得到子问题的局部最优解，把子问题的解局部最优解合成原来解问题的一个解。为了解决问题，需要寻找一个构成解的候选对象集合，起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。由以上可知：在贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。并且，每一步的最优解一定包含上一步的最优解。而在动态规划算法中，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解。也就是说，把一个复杂问题分解成一块一块的小问题，每一个问题得到最优解，再从这些最优解中获取更优的答案。