贪心法与动态规划

第8章贪心法与动态规划(2)石志国大纲◎贪心法的基本概念，以及使用贪心法解决问题：哈夫曼编码、单源最短路径、最小生成树、背包问题◎动态规划的基本概念，以及使用动态规划解决问题：多源最短路径、背包问题、图像压缩和最长公共子序列问题。问题提出

动态规划是解决多阶段决策最优化问题的一种方法。如图所示的一个线路网络，两点之间的连线上的数字表示两个点之间的距离，要求求出一条从A到E的路径，使得总距离最小。问题提出从图可以看出，从A到E可以划分为5个阶段，除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，B1和B2为终点，这里就存在两种情况供选择。同理，在第2和第3阶段都存在多种情况供选择。现在的问题是：如何在每个阶段都作出一个恰当的决策，使由这些决策组成的一个决策序列所构成的一条线路的总距离最短。问题提出一个容易想到的方法是愚公移山的想法(exhaustivesearch)，即穷举法。将从A到E的所有可能路线的距离都计算出来，然后两两互相比较，找出最短路线。其缺点是计算比较复杂。问题提出实际上，求从A到E的最短距离问题，可以转化为两个性质完全相同，但规模较小的子问题即分别从B1、B2到E的最短路径问题，这时，从A到E的最短距离(记为SD(A))问题可以表示为：

动态规划法同样，计算SD(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题SD(Ci)(i=1,2,3)，而求SD(Ci)又可以归结为求SD(D1)和SD(D2)两个子问题。由于SD(D1)和SD(D2)是已知的，因此，可以从这两个值开始，逆向递归计算出SD(A)的值。最终，可以得到从A到E的最短路径。上述求解的方法称为动态规划法(DynamicProgramming)。2动态规划法概述动态规划是美国数学家R．Bellman等人于1951年在研究多阶段决策过程的优化问题时所创立的一种用于解决此类过程优化问题的新方法。（1）基本思想在现实生活中，有一类问题可以将其活动过程分解成若干个相互联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。在每个阶段所作的决策选择依赖于当前状态，又影响它以后的发展。当各个阶段决策确定后，就组成一个决策序列，从而就确定了整个过程的一条活动路线。这种将一个问题看作是一个前后相互关联且具有链状结构的多阶段过程称为多阶段决策过程。如图所示。其中，“状态”是指各决策阶段开始时的客观条件。（1）基本思想在多阶段决策过程中，某一阶段会存在多个决策序列，如果在进行决策时遵循如下原则：求解过程为自底向上（即从终点到起点），每一步的选择总是依赖于上一步的选择，且此步仅仅把不可能的决策序列排除在外。则这种解决多阶段决策的最优化的过程称为动态规划法。动态规划法适用方法动态规划法主要适用于最优化问题的求解。这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个最优值的解的话，它只取其中的一个。与分治法和贪心法联系与区别动态规划法与分治法和贪心法类似，它也是将原问题分解为若干个更小的、相似的子问题，并通过求解子问题产生一个全局最优解。与分治法和贪心法不同之处在于：①使用贪心法时，当前的选择可能要依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法是自顶向下(即从起点到终点)，一步一步地作出贪心选择。当然，如果当前的选择可能要依赖于子问题的解时，则难以通过局部的贪心策略达到全局最优解。②使用分治法时，由原问题分解出的各子问题通常是相互独立的，即不包含公共的子问题，因此一旦递归地求出各子问题的解后，便可自下而上地将各子问题的解合并成问题的解。如果各子问题不是相互独立的，则分治法要做许多不必要的工作，重复地求解公共的子问题。③动态规划允许由原问题分解出的子问题之间相互依赖。每一个子问题只求解一次，并将结果保存起来，避免每次碰到此子问题时都要重复计算。（2）适用条件适用动态规划的问题通常应满足如下3点：①最优化原理（最优子结构性质）如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优化原理。所谓最优原理是指无论前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。②无后效性应用动态规划法的一个重要条件就是将各阶段按照一定的次序排列好，阶段i的状态只能由阶段i+1的状态来确定，与其它状态没有关系，尤其是与未发生的状态没有关系。换言之，每个状态都是“过去历史的一个完整总结”。这就是无后效性。③子问题的重叠性子问题重叠性是指在利用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题可能会被重复计算多次。动态规划法正是利用子问题的这种重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在起来，当再次需要计算已经计算过的子问题时，只是简单地查看一下以往的计算结果，从而获得较高的解题效率。子问题的重叠性并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其它算法相比就无优势可言了。（3）解决问题的步骤利用动态规划法求解问题的算法通常包含如下几个步骤：①分析对原始的问题进行分析，找出问题的最优解的结构特征。②分解将所给问题按时间或空间特征分解成若干相互关联的阶段，并确定出计算局部最优解的递推关系，这是利用动态规划法解决问题的关键和难点所在。需要注意的是，分解后的各个阶段一定是有序的或者是可排序的，即无后向性。否则问题就无法用动态规划求解。阶段之间相互联系方式是通过状态和状态转移体现的。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来的，这种“变化”称为状态转移。状态转移是导出状态的途径，也是联系各阶段的方式。③解决对于每个阶段通过自底向上的方法求得局部问题的最优解。由于这一步骤通常是通过递推实现的，因此，需要一个递推的终止条件或边界条件。④合并将各个阶段求出的的解合并为原问题的解，即构造一个最优解。步骤①～③是动态规划法的基本步骤。在只需要求出最优值的情形下，步骤④可以省略。若需要求出问题的一个最优解，则必须执行步骤④。此时，在步骤③中计算最优值时，通常需记录更多的信息，以便在步骤④中，根据所记录的信息，快速地构造出一个最优解。动态规划的主要难点动态规划的主要难点在于理论上的设计，特别是递推关系的建立，一旦设计完成，实现部分就会非常简单。整个求解过程就可以使用一个最优决策表的二维数组来描述，其中，行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值，如最短路径，最长公共子序列，最大价值等。填表的过程就是根据递推关系从1行1列开始，以行或者列优先的顺序，依次填写表格。最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。总之，动态规划算法的关键在于解决冗余，是一个以空间换时间的技术，所以它的空间复杂度要大于其它的算法。应用举例-多源最短路径

1）问题描述所谓多源最短路径问题就是指对于一个给定的非负有向网图，求出任意两个结点之间的最短路径。目前，对于多源最短路径问题更直接的做法是使用Warshall-Floyd算法。其中，Warshall算法是一个用于求图的传递闭包的算法。而求任意两个顶点之间的最短路径的Floyd(弗洛伊德)算法与Warshall算法非常相似，所以通常称Floyd算法为Warshall-Floyd算法。应用举例-多源最短路径对于一个n×n的矩阵，Floyd算法使用的迭代矩阵序列如下：D0，D1，…，Dn-1迭代的初始值D0是图的邻接矩阵，然后逐步尝试在原来的路径中加入其它的结点作为中间点，如果加入新结点后求得的路径比原来的路径短，则以此新路径替代原来的路径。然后再加入一个顶点，继续进行迭代。依次类推，直到经过n次比较后，就可以求得两个顶点之间的最短路径。例如，假设Dk-1中第i行第j列的值为dijk-1，增加顶点vk后，需要进行dijk-1与dikk-1+dkjk-1的大小比较，取它们中的小者为dijk，即有如下迭代公式：dijk=min{dijk-1,dikk-1+dkjk-1}0≤k≤n-1（6-1）程序实例输入顶点个数:(最大输入数为:5)5依次输入顶点名:ABCDE输入边数:7按"headtailweight"的方式输入边信息：AB10AD30AE100BC50CE10DC20DE60图中所有边如下:(A,B,10)(A,D,30)(A,E,100)(B,C,50)(C,E,10)(D,C,20)(D,E,60)最小路径值:60路径:0324图像压缩

1）问题描述在计算机中，图像常用像素点的灰度值来表示，假如一幅图像用一个mXm的像素阵列表示，每个像素都用一个字节来存储，则总的存储空间为8m2位。为了减少所需的存储空间，通常采用变长模式存储，即不同像素用不同位数来存储。图像压缩问题就是要寻找一个方案，通过对给定的图像像素点进行合理的分割，针对不同的子段采用不同存储位技术即变长模式，使得整个图像所占用的存储空间最小。图像压缩2）算法实现比如：表示一幅图像的像素点灰度值序列为{p1，p2，…，pn}，其中pi表示第i个像素点的灰度值。灰度值的范围为0-255。假设将像素点序列{p1，p2，…，pn}分割为m个连续子段S1，S2，…，Sm。其中，像素段Si中包含有L[i]个像素，且该段中每个像素都用b[i]位来表示。如果b[i]和L[i]取值范围分别限制为：1≤b[i]≤8，1≤L[i]≤255，则需要3位表示b[i]，8位表示L[i]。此时像素段Si所需存储空间为：L[i]*b[i]+11位。其中11为每个像素段的头信息，用于存储段的长度以及该段中每个像素所占用的位数。另外还可以通过将某些相邻段合并的方式来减少空间消耗。如当像素段

i

和i-1合并后，像素段长应为L[i]+L[i-1]。合并后像素段中的每个像素的存储位数应设为max{b[i]，b[i-1]}

位。图像压缩令s[k]为前k个像素段的最优合并所需要的空间。定义s[0]=0。则第i(i＞0)个像素段与其前面第i-