贪心算法和动态规划以及分治法的区别？ 贪心算法和动态规划.pdf

贪心算法、动态规划和分治法的区别 贪心算法是指在当前看来是最好的结果，不考虑整体情况，只关心局部最优解。它从上往下，从顶部一步步最优，得到最后的结果，但不能保证全局最优解。贪心策略的选择也影响到结果。 动态规划则是将问题分解成子问题，这些子问题可能有重复，可以记录下前面的子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。 分治法（divide-and-conquer）则是将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。分治模式在每一层递归上都有三个步骤：分解（Divide）：将原问题分解成一系列子问题；解决（conquer）：递归地解各个子问题若子问题足够小，则直接求解；合并（Combine）：将子问题的结果合并成原问题的解。 以下是贪心算法、动态规划和分治法的区别： 1. 贪心算法：局部最优解，不保证全局最优解；动态规划：全局最优解，但需要记录前面的结果防止重复计算；分治法：将原问题划分成子问题，递归地解决子问题，然后合并结果。 2. 贪心算法：从上往下，从顶部一步步最优；动态规划：从下到上，一步一步找到全局最优解；分治法：将原问题划分成子问题，递归地解决子问题，然后合并结果。 3. 贪心算法：不能保证全局最优解；动态规划：保证全局最优解；分治法：可以保证全局最优解。 4. 贪心算法：不需要记录前面的结果；动态规划：需要记录前面的结果防止重复计算；分治法：不需要记录前面的结果。 5. 贪心算法：适用于一些简单的问题；动态规划：适用于一些复杂的问题；分治法：适用于一些可以划分成子问题的问题。 贪心算法、动态规划和分治法都是重要的算法思想，但它们之间有着明显的区别。贪心算法适用于一些简单的问题，但不能保证全局最优解；动态规划可以保证全局最优解，但需要记录前面的结果防止重复计算；分治法则是将原问题划分成子问题，递归地解决子问题，然后合并结果，可以保证全局最优解。