动态规划算法和贪心算法的比较与分析

动态规划算法和贪心算法的比较与分析1、最优化原理根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。解决这类问题的最优化原理:一个过程的最优决策具有这样的性质,即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略。简而言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。2、动态规划2.1动态规划算法动态规划是运筹学的一个分支，与其说它是一种算法，不如说它是一种思维方法更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先搜索算法，都渗透着动态规划的思想。还有许多数学问题，表面上看起来与动态规划风马牛不相及，但是其求解思想与动态规划是完全一致的。因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用。它必须对具体问题进行具体分析、处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。值得注意的是，用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的。最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都要满足两个条件:①问题中的状态必须满足最优化原理;②问题中的状态必须满足无后效性。所谓无后效性是指下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。2.2动态规划算法的基本要素(1)最优子结构。设计动态规划算法的第一步通常是刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。(2)重叠子问题。在用递归方法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时只是简单地用常数时间查看一下结果。2.3动态规划适于解决的问题适用动态规划的问题必须满足最优化原理和无后效性。(1)状态必须满足最优化原理。作为整个过程的最优策略具有如下性质:无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。(2)状态必须满足无后效性。所谓无后效性是指:“过去的决策只能通过当前状态影响未来的发展，当前的状态是对以往决策的总结”。它说明动态规划适于解决当前决策和过去状态无关的问题。状态出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策，这就是无后效性的内涵。2.4问题求解模式动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如下所示:初始状态→决策1→决策2→决策n→结束状态动态规划的设计有一定的模式，一般要经历以下4个步骤:(1)划分阶段。按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。(2)确定状态和状态变量。将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3)确定决策并写出状态转移方程。因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。(4)寻找边界条件。给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。用动态规划算法解决一个问题关键就是确定以上4个步骤。3、贪心算法3.1贪心算法的定义贪心算法是一种改进的分级处理方法。用贪心法设计算法的特点是一步一步地进行,根据某个优化测度,每一步都要保证能获得局部最优解。每步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完，或不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注:贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。)采用自顶向下的、以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。3.2贪心算法的基本要素贪心算法通过一系列的选择得到问题的解。它所做出的每一选择都是当前状态下局部最好选择，即贪心选择。可以用贪心算法求解的问题一般具有两个重要性质:(1)贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解能通过一系列局部最优的选择(即贪心选择)来达到。(2)最优子结构性质。与动态规划算法相同，最优子结构性质是一个问题可用贪心算法求解的关键特征。3.3贪心算法的实际应用(1)贪心法的基本思路。从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。(2)该算法存在的问题。1)不能保证求得的最后解是最佳的;2)不能用来求最大或最小解问题;3)只能求满足某些约束条件的可行解的范围。(3)实现该算法的过程。1)从问题的某一初始解出发;2)当能朝给定总目标前进一步时，求出可行解的一个解元素;3)由所有解元素组合成问题的一个可行解。4、动态规划算法与贪心算法4.1联系都是通过局部最优解得到整体最优解。4.2区别贪心算法是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法，贪心策略总是做出在当前看来最优的选择，并不是从总体上加以考虑，它所做的选择只是在某种意义上的局部最优解。它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，最终可得到问题的一个最优解。动态规划是在每一步判断的时候只须考虑与它有关的前一步的情况而与以前的各步的判断没有关系，解决这类问题的方法是:把问题化成多步判断的问题，在每步作出判断时，只考虑由初始决策所确定的当前状态。它采用自底向上的顺序，找到边界条件，将整个问题的最优解与问题的局部最优解用递推的等式联系起来，把边界条件代入递推等式逐步求得最优解。动态规划算法与贪心算法都要求问题具有最优子结构性质，这是二者的一个共同点。但是对于具有最优子结构的问题应该选择前者还后者来解决?下面通过两个经典的组合优化问题谈谈动态规划算法与贪心算法的主要差异。4.30-1背包问题与背包问题0-1背包问题:给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有两种选择:即装入背包或不装入背包。不能将物品i放入背包多次,也不能只装入部分的物品i。背包问题:与0-1背包问题类似，不同的是在选择物品i装入背包时，可选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。4.4动态规划算法与贪心算法的主要差异0-1背包问题和背包问题这两类问题都具有最优子结构性质。虽然它们极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值vi/wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去直到背包装满为止。这种贪心选择策略对0-1背包问题就不适用了。如图1(a)所示，其中有3种物品，背包的容量为50公斤。物品1重10公斤，价值60元;物品2重20公斤，价值100元;物品3重30公斤，价值120元。因此，物品1每公斤价值6元，物品2每公斤价值5元，物品3每公斤价值4元。若依贪心选择策略，应首选物品1装入背包，然而从图1(b)的各种情况可看出，最优的选择方案是选择物品2和物品3装入背包。首选物品1的2种方案都不是最优的。对于背包问题，贪心选择最终可得到最优解，其选择方案如图1(c)所示。对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的空间使每公斤背包空间的价值降低。在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再做出最好的选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。(a)(b)(c)图1两种算法解决背包问题5、结束语在动态规划算法中，每步所做出的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。贪心算法所做出的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法常以自底向上的方式解各子问题，而贪心算法则常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做出一次贪心选择就将所求问题简化为规模更小的子问题。和贪心算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心算法中，每用一次贪心准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。当一个问题具有最优子结构时，我们会想到用动态规划法去解它，但是有些问题存在着更简单、有效的方法，只要我们总是做出当前看来最好的选择就可以了。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与回溯法等比较，它的适用区域相对狭窄许多，因此正确地判断它的应用时机十分重要。