1、1 1第九章第九章 动态规划与贪心策略动态规划与贪心策略p动态规划思想p动态规划策略的应用p贪心策略的基本要p贪心策略的应用动态规划策略通常用于求解具有某种最优性质的问题。贪心算法则是仅在当前状态下做出的最好选择，即局部最优选择；然后再求解做出该选择后所产生的相应子问题的解。2 2动态规划n适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的；n基于动态规划法的算法设计通常按以下几个步骤进行：(1)找出最优解的性质，并描述其结构特征；(2)递归定义最优值；(3)以自底向上的方式计算最优值；(4)根据计算最优值时得到的信息构造一个最优解。通常在步骤(3)计算最优值时，需要记录更多的信
2、息，以便在步骤（4）中快速构造出一个最优解。3 3n动态规划算法的两个基本要素最优子结构性质和子问题重叠性质。计算计算A1:4A1:4的递归树的递归树 (1)最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。(2)重叠子问题：对每个子问题只解一次，然后将解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看所保存的结果即可。动态规划算法的基本要素4 4n是动态规划算法的一个变形。n备忘录方法的递归方式是自顶向下，动态规划算法则是自底向上。具体算法思想：备忘录方法 每一个子问题建立一个记录项，初始化时将其赋值为特定值，表示该子问题尚未求解。在求解过程中，
3、对每个待求解的子问题首先查看其相应的记录项，若记录项中存储的值是初始化的值，则表示该子问题第一次遇到，就需要计算该子问题的解，并存入相应的记录项，否则表示该子问题已经求解，即不必再计算该子问题。5 5int MemorizedMatrixChain(int n,int mn,int sn)for(int i=1;i=n;i+)for(int j=1;j 0)return mij;if(i=j)return 0;u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)t=LookupChain(i,k
4、)+LookupChain(k+1,j)+pi-1*pk*pj;if(t 0，那么mij中存储的值就是待求的值，直接返回此结果即可；否则通过递归算法自顶向下计算，并将计算结果存入mij后返回。n与动态规划算法一样，备忘录算法的复杂性是O(n3)。n当一个问题的所有子问题都至少需要求解一次时，则动态规划算法好于备忘录方法；当子问题空间中的部分子问题可以不必求解时，备忘录算法优于动态规划算法。备忘录算法分析矩阵连乘积的最优计算次序问题可用自顶向下的备忘录算法或自底向上的动态规划算法在O(n3)计算时间内求解。这两个算法都利用了子问题重叠性质。7 7n问题：给定n个矩阵A1,A2,An，其中Ai和A
5、i+1是可乘的，i=1,2,n-1，要求计算这n个矩阵的连乘积A1A2An。矩阵连乘问题n每一种完全加括号的方式对应于一种矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算量有着密切的关系。n解题思路：矩阵乘法满足结合律，如果矩阵连乘完全加了括号，则说明计算矩阵连乘的次序也完全确定。完全加括号的矩阵连乘积可以递归定义为：(1)单个矩阵是完全加括号的；(2)矩阵连乘积A是完全加括号的，则A可以表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。8 8若按第一种括号方式计算，则计算三个矩阵连乘积需要的数乘次数为：100*5*50+10*100*50=75,000。若按第二
6、种括号方式计算，则计算三个矩阵连乘积需要的数乘次数为：10*100*5+10*5*50=7,500。矩阵连乘问题示例【例1】三个矩阵 A1,A2,A3，其连乘积A1A2A3有2种计算次序：A1(A2A3)和(A1A2)A3，矩阵维数分别是10/100、100/5和5/50。分析：对于n个矩阵如何确定矩阵连乘积的最优计算次序？穷举法不是一个有效的算法9 9n设计算Ai:j(1ijn)所需的最少数乘次数为mij，则原问题的最优值为m1n。n当i=j时，Ai:j=Ai为单一矩阵，无需计算；n当ij时，可利用最优子结构性质计算mij。n若将mij的断开位置k记为sij=k，在计算出最优值mij后，可由
7、sij递归地构造出相应的最优解。jipppjkmkimjijimjkijki1min01建立递归关系1010n用动态规划法求解此问题可依据其递归式以自底向上的方式进行计算，在计算过程中保存已解决的子问题的答案，从而避免大量的重复计算，最终得到多项式时间的算法。n下面给出计算mij的动态规划算法MatrixChain，输入参数p0,p1,p2,pn存储于数组p中。算法除了输出最优值数组m外，还输出记录断开位置的数组s。n算法首先计算出mii=0(i=1,2,n)，然后在根据递归式、按矩阵链长递增的方式依次计算mii+1(i=1,2,n-1，此时的矩阵链长度是2)、mii+2(i=1,2,n-2，
8、此时的矩阵链长度是3)，。在计算mij时，只用到已经计算出的mik和mk+1j。计算最优值1111void MatrixChain(int pn,int n,int mn,int sn)int i,j,r,k,t;for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n-r+1;i+)j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;t=mik+mk+1j+pi-1*pk*pj;if(t 0，wi0，vi0，1in，要求找出一个n元向量(x1，x2，xn)，xi0,1，1in，使得 ，且 达到最大。cxwniii1n1iiixv1717
9、0-1背包问题n对于0-1背包问题，设A是能够装入容量为c的背包且具有最大价值的物品集合，则Aj=A-j是n-1个物品可装入容量为c-wj的背包的具有最大价值的物品集合。n在考虑0-1背包问题的物品选择时，应比较选择该物品和不选择该物品所导致的最终结果，然后再做出最好的选择。由此导致许多相互重叠的子问题出现，这正是0-1背包问题应采用动态规划算法求解的重要原因之一。1818贪心算法n贪心算法基本思想：总是作出在当前看来是最好的选择，即贪心算法并不从整体最优上考虑，而只考虑当前（局部）最优。n活动安排问题：设n个活动集合E=1,2,n，其中每个活动都要求使用同一资源（如演讲会场），而在同一时间有
10、且只有一个活动可以使用这一资源，每个活动i要求使用该资源的起始时间和结束时间分别是si和fi，且sifi，占用资源的半开时间区间是si,fi)。若si,fi)和sj,fj)不相交，则活动i和活动j是相容的，否则活动i和活动j是相互冲突的。1919活动安排问题的贪心算法求解n各活动的起始时间和结束时间分别存储在数组s和f中，且活动按结束时间递增排列。void GreedySelector(int n,DataType s,DataType f,int A)A1=1;int j=1;for(int i=2;i=fj)Ai=1;j=i;else Ai=0;2020贪心算法求解问题的条件n贪心选择性质
11、是指所求问题的整体最优解可以通过一系列局部最优解的选择来实现（贪心选择）。证明的具体步骤是：(1)考察问题的一个全局最优解，并证明可修改该最优解，使其以贪心选择开始；(2)做贪心选择后，原问题简化为一个规模更小的类似子问题；(3)用数学归纳法证明，通过每一步作贪心选择，最终可导致问题的一个全局最优解。n最优子结构是指当一个问题的最优解包含其子问题的最优解性质。2121贪心算法与动态规划算法的差异 n在动态规划算法中，每步所作出的选择往往依赖于相关子问题的解，因此只有在解出相关子问题的解后才能做出选择；n而贪心算法所作的贪心选择仅在当前状态下做出的最好选择，即局部最优选择，然后再求解作出该选择后
12、所产生的相应子问题的解，即贪心算法所作出的贪心选择可以依赖于“过去”所作出的选择，但绝不依赖于将来所作出的选择，也不依赖于子问题的解。n贪心算法和动态规划算法都具有最优子结构性质。2222差异在具体算法的体现n0-1背包问题：n种物品和一个背包，物品i重量wi，其价值vi，背包容量c。如何选择装入背包的物品，使背包中物品的总价值最大？（在选择装入背包中的物品时，对每种物品i只有两种选择：装入或不装入，即不能将物品i多次装入背包，也不能只装物品i一部分）。cxwniii1n1iiixv形式化描述：给定c0，wi0，vi0，1in，要找出n元向量(x1，x2，xn)，xi0,1，1in，使 ，且
13、达到最大。n背包问题：n种物品和一个背包，物品i重量wi，其价值vi，背包容量c。如何选择装入背包中的物品，使装入背包物品的总价值最大？（在选择装入背包中的物品时，对每种物品i只有三种选择：装入、不装入或部分装入）。形式化描述：给定c0，wi0，vi0，1in，要找出n元向量(x1，x2，xn)，0 xi1，1in，使 ，且 达到最大。cxwniii1n1iiixv2323背包问题分析n上述两个问题都具有最优子结构性质。n对于0-1背包问题，设A是能够装入容量为c的背包且具有最大价值的物品集合，则Aj=A-j是n-1个物品可装入容量为c-wj的背包的具有最大价值的物品集合。n对于背包问题，若它
14、的一个最优解包含物品j，则从该最优解中拿出所含物品j的那部分重量w，剩余的重量将是n-1个原重物品和重为wj-w的物品j中可装入容量为c-w的背包且具有最大价值的物品。背包问题可以用贪心算法求解，而0-1背包问题却不能使用贪心算法2424贪心算法求解背包问题(1)计算每种物品的单位重量的价值vi/wi；(2)根据贪心选择策略，将尽可能多的单位重量价值高的物品装入背包；(3)若将这种物品全部装入背包后，被包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包；(4)以此类推，直到背包装满为止。具体步骤：2525求解背包问题算法void KnapSack(int n,float
15、 M,float v,float w,float x)Sort(n,w,v);/各物品依单位重量价值大小从大到小排列各物品依单位重量价值大小从大到小排列 int i;for(i=1;i=n;i+)xi=0;float c=M;for(i=1;i c)break;xi=1;c-=wi;if(i=n)xi=c/wi;26260-1背包问题n贪心算法不适合0-1背包问题，因为它无法保证最终能将背包装满，部分背包空间的闲置使每千克背包空间的价值降低。粗粗框为框为0-10-1背包背包问题问题最优解最优解背包问题背包问题最优解最优解2727贪心算法应用之哈夫曼编码 n使平均码长达到最小的前缀编码称为C的一
16、个最优前缀码。n哈夫曼提出了一种构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。n哈夫曼算法采用自底向上的方式构造最优前缀码的二叉树T，算法以|C|个叶子结点开始，执行|C|-1次的“合并”运算后产生最终所求的二叉树T。n证明最优前缀码问题具有贪心选择性质和最优子结构性质。2828贪心算法应用之哈夫曼编码 n哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法，它利用一个字符在文件中出现的频率建立一个用0-1串表示各个字符的最优表示方法。假设有一个数据文件包含100 000个字符，其中共有六个字符形式，每个字符出现的频率如表9-1所示。问题是：如何采用压缩存储方式存储该文件。表 9
17、-1 字符出现的频率及字符编码 a b c d e f 频率(千次)45 13 12 16 9 5 定长码 000 001 010 011 100 101 变长码 0 101 100 111 1101 1100 2929贪心算法应用之哈夫曼编码 n译码过程必须方便地获取编码的前缀，因此需要一个表示前缀码的合适的数据结构，为此采用二叉树作为表示前缀编码的数据结构。在二叉树中，叶子代表给定的字符，并将每个字符的前缀码看做是从根到代表该字符的叶子的一条路经，代码中的每一位0或1分别作为指示某结点到左孩子或右孩子的“路标”。例如，图9-4中的两棵树分别表示表8-1中的编码方案所对应的数据结构。3030
18、贪心算法应用之哈夫曼编码 图图8-4 8-4 前缀码的二叉树表示前缀码的二叉树表示3131贪心算法应用之哈夫曼编码 n给定编码字符集C及其频率分布f，C的一个前缀码编码方案对应一个二叉树T，字符cC在树T中的深度记为dT(c),其中dT(c)也是字符c的前缀码长。该编码方案的平均码长定义为 使平均码长达到最小的前缀编码称为C的一个最优前缀码。3232贪心算法应用之哈夫曼编码 n考虑哈夫曼编码的正确性只要能证明最优前缀码问题具有贪心选择性质和最优子结构性质，就可证明哈夫曼编码是正确的。(1)证明最优子结构性质设T表示字符集C的一个最优前缀码的二叉树，C中字符c的出现频率为f(c)，x和y是树T中
19、的两个兄弟叶子，z是x和y的双亲，若将z看做频率为f(z)=f(x)+f(y)的字符，则树T=T-x,y表示字符集C=C-x,yz的一个最优前缀码。证明：T的平均码长用T的码长表示。对于任意cC-x,y，有dT(c)=dT(c)，故f(c)dT(c)=f(c)dT(c)。另外，dT(x)=dT(y)=dT(z)+1，故：f(x)dT(x)+f(y)dT(y)=(f(x)+f(y)(dT(z)+1)=f(x)+f(y)+f(z)dTz)因此，B(T)=B(T)+f(x)+f(y)。3333贪心算法应用之哈夫曼编码 若T所表示的字符集C 的前缀码不是最优的，则有T“表示的C 的前缀码使得B(T)B
20、(T)。由于将z看做C 中的一个字符，因此z在T“中是树叶。若将x和y加入树T 中作为z的孩子，则得到字符集C的前缀码的二叉树T ，且有这与T是最优前缀码相矛盾，故T所表示的前缀码也是最优3434贪心算法应用之哈夫曼编码(2)证明贪心选择性质设C是编码字符集，C中字符c的频率为f(c)，x和y是C中具有最小频率的两个字符，则存在C的一个最优前缀码使x和y具有相同的码长且它们的最后一位编码不同。设二叉树T表示C的任意一个最优前缀码，我们要证明在对T做适当修改后可以得到一棵新的二叉树T，使得在新树中x和y是最深叶子且互为兄弟，同时新树T表示的前缀码也是C的一个最优前缀码。如果能做到这一点，则x和y
21、在T表示的前缀码中具有相同的码长且仅最后一位编码不同。3535贪心算法应用之哈夫曼编码 证明：设b和c是二叉树T的最深叶子且为兄弟，不失一般性，设f(b)f(c)，f(x)f(y)。由于x和y是C中具有最小频率的两个字符，因此f(x)f(b)，f(y)f(c)。将树T中的叶子x和b交换得到树T ，再将y和c交换得到树T，则3636贪心算法应用之哈夫曼编码 同理得因此，。由于T所表示的前缀码是最优前缀码，因此B(T)B(T)。故B(T)=B(T)，即T表示的前缀码也是最优前缀码，且x和y具有最长的码长仅最后一位编码不同。3737本章小结l动态规划与贪心策略是把大规模问题分解成小规模问题进行求解的两种解决方法。l适用于动态规划策略求解的问题，具有最优子结构性质和子问题重叠性质。适用于贪心算法求解的问题，具有贪心选择性质和最优子结构性质。
