贪心算法与动态规划的区别与联系
发布时间：2024-12-31 14:32:14来源：
一、贪心算法
定义与基本原理
贪心算法是一种在每一步选择中都采取当前状态下的最优决策（即贪心策略），从而希望导致全局最优解的算法。它在对问题求解时，总是做出在当前看来是最好的选择。例如，在找零问题中，如果有 10 元、5 元、1 元的硬币，要找给顾客 18 元，贪心算法会优先选择面值最大的硬币，先拿 10 元，再拿 5 元，最后拿 3 个 1 元。
特点
局部最优选择：贪心算法侧重于局部最优解，它不考虑整体的最优解结构。在上述找零问题中，每一步都选择能使当前找零金额最大程度减少的硬币，而不考虑这种选择对后续步骤是否最优。
无后效性：贪心算法的每一个决策只依赖于当前状态，而不依赖于之前的决策序列。也就是说，做出当前决策后，不会对之前的选择产生影响。在找零过程中，一旦选择了一枚硬币，后续的选择不会改变之前硬币的选择情况。
简单高效：贪心算法通常比较简单，实现起来比较容易，并且在某些特定问题上具有较高的时间效率。因为它不需要像动态规划那样存储大量的中间状态，计算量相对较小。例如，在活动安排问题中，贪心算法可以通过按照活动结束时间排序后简单地选择活动，时间复杂度为，其中是活动的数量。
适用场景
贪心算法适用于具有最优子结构性质和贪心选择性质的问题。最优子结构性质是指一个问题的最优解包含其子问题的最优解。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。例如，在哈夫曼编码问题中，每次选择频率最低的两个节点合并成一个新节点，通过这样的贪心选择可以构建出最优的前缀码，这个问题满足最优子结构和贪心选择性质。
二、动态规划
定义与基本原理
动态规划是一种用于解决优化问题的算法策略，它通过将一个复杂的问题分解为一系列相互关联的子问题，并存储子问题的解来避免重复计算。例如，在计算斐波那契数列时，动态规划可以通过记录已经计算过的数列项的值，避免重复计算，提高效率。
特点
分解问题：动态规划的关键在于将原问题分解为子问题，这些子问题通常具有重叠的部分。以计算斐波那契数列为例，，计算就需要先计算和，这两个子问题又会有各自的子问题，而且在计算过程中有很多子问题是重复的。
存储子问题的解：为了避免重复计算子问题，动态规划会使用一个表格（如数组）或者其他数据结构来存储子问题的解。在斐波那契数列计算中，可以使用一个数组来存储已经计算出的数列项的值，这样当需要再次使用某个值时，直接从数组中获取，而不需要重新计算。
递推关系：动态规划通过建立子问题之间的递推关系来求解问题。通常是从最基础的子问题开始，逐步求解更大的子问题，直到得到原问题的解。在背包问题中，有一个递推关系用于计算在不同背包容量和物品情况下的最大价值。
适用场景
动态规划适用于具有重叠子问题和最优子结构性质的问题。重叠子问题是指在解决问题的过程中，会多次计算相同的子问题。最优子结构性质与贪心算法中的类似，即问题的最优解可以从子问题的最优解构造出来。例如，最长公共子序列问题，通过比较两个序列的子序列来找到最长的公共部分，这个问题有重叠子问题（在计算不同位置的子序列时会重复计算部分子序列）和最优子结构（最长公共子序列的最优解可以从子序列的最优解得到）。
三、区别
决策方式
贪心算法：在每一步都做出局部最优决策，不考虑整体情况，也不会回溯。它只关注当前的最优选择，希望通过一系列局部最优解来达到全局最优。
动态规划：考虑整个问题的最优解结构，通过对所有可能的子问题进行求解，并根据子问题之间的关系来构建原问题的最优解。它会综合考虑多种情况，不是只看局部最优。
对子问题的处理
贪心算法：通常不会保存子问题的解，因为它不依赖于之前的子问题状态，每个决策都是独立的，只要满足贪心策略即可。
动态规划：会存储子问题的解，以避免重复计算。由于子问题之间存在重叠，存储子问题的解可以大大提高计算效率。
最优解的保证程度
贪心算法：并不一定能保证得到全局最优解。只有在问题具有贪心选择性质和最优子结构性质时，贪心算法才能得到最优解。例如，在旅行商问题（TSP）中，贪心算法（如最近邻算法）通常不能得到全局最优解，因为它只考虑当前最近的城市，而忽略了后续的整体路径情况。
动态规划：只要问题具有重叠子问题和最优子结构性质，并且递推关系正确，动态规划一定能得到全局最优解。因为它通过对所有子问题的最优解进行组合来构建全局最优解。
四、联系
都用于求解优化问题
贪心算法和动态规划都是用于解决优化问题的算法策略，它们的目的都是在给定的约束条件下，找到问题的最优解，如在资源分配、路径规划等领域都有应用。
都可能依赖最优子结构性质
当问题具有最优子结构性质时，贪心算法和动态规划都可以发挥作用。不过贪心算法是通过贪心选择来利用最优子结构，而动态规划是通过分解问题、存储子问题解和建立递推关系来利用最优子结构。例如，在最短路径问题中，迪杰斯特拉算法（贪心算法）和弗洛伊德 - 沃肖尔算法（动态规划）都利用了最短路径问题的最优子结构性质，只是实现方式不同。
（责编： admin1）
免责声明：本文为转载，非本网原创内容，不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
