计算机学院动态规划教学课件

第3讲 动态规划 王 静 河南理工大学计算机学院 2013年3月 第3讲 动态规划 一、算法总体思想 二、算法基本要素 三、算法范例分析 第3讲 动态规划 动态规划算法与分治法类似，其基本思想 也 是将待求解问题分解成若干个子问题。 一、算法总体思想一、算法总体思想 n T(n/2) T(n/2)T(n/2)T(n/2) T(n) = 第3讲 动态规划 但是经分解得到的子问题往往不是互相独立的。 不同子问题的数目常常只有多项式量级。在用分 治法求解时，有些子问题被重复计算了许多次。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) 第3讲 动态规划 如果能够保存已解决的子问题的答案，而 在需要时再找出已求得的答案，就可以避 免大量重复计算，从而得到多项式时间算 法。 n= n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2n/2 T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) T(n/4) T(n) 第3讲 动态规划 动态规划通常应用于最优化问题，即要做 出一组选择以达到一个最优解。在做选择 的同时，经常出现同样形式的问题。当某 一特定的子问题可能出自于多于一种选择 的集合时，动态规划是很有效的；关键技 术是存储这些子问题每一个的解，以备它 重复出现。 第3讲 动态规划 动态规划基本步骤动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优 解。 第3讲 动态规划 矩阵连乘问题矩阵连乘问题 给定n个矩阵 ，其中 与 是可乘的 ， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有 许多不同的计算次序。这种计算次序可以用加括号的方 式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连 乘积已完全加括号，则可以依此次序反复调用2个矩阵相 乘的标准算法计算出矩阵连乘积。 第3讲 动态规划 矩阵连乘问题 给定n个矩阵A1,A2,An，其中Ai与Ai+1是 可乘的，i=1，2，n-1。如何确定计算矩阵连乘积 的计算次序，使得依此次序计算矩阵连乘积需要的数 乘次数最少。 第3讲 动态规划 16000, 10500, 36000, 87500, 34500 u完全加括号的矩阵连乘积可递归地定义为： u设有四个矩阵 ，它们的维数分别 是： u总共有五中完全加括号的方式 （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 第3讲 动态规划 u穷举法 列举出所有可能的计算次序，并计算出每一种计算 次序相应需要的数乘次数，从中找出一种数乘次数 最少的计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下： 第3讲 动态规划 u动态规划方法 将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ik void MatrixChain(int* p,int n,int m6,int s6); void Traceback(int i,int j,int s6); int main(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; for (int ii=0;ii 2 using namespace std; 3 #define N 6 4 #define M 1000 5 int wN=1,2,3,5,10,20; 6 int cN=0; 7 int visitM+1 = 0; 9 int weight_count() 10 int i = 0; 12 int j = 0; 13 int total = 0; 14 int count =0; 16 visit0 = w0*c0;/visit0用于每添加一个砝码时遍历的结束位置 17 for(i = 1;iM) 27 break; 28 if(visitj = 1 31 total = j+k*wi; 35 visit0 = total; 36 37 for(i = 1;ici; 53 int count = weight_count(); 54 cout 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k =cij-1) cij=ci-1j; bij=2;/竖直向下填写 else cij=cij-1; bij=3;/水平向右填写 return cmn; 第3讲 动态规划 (4)(4)构造最长公共子序列构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout 另一个解B,C,A,B 第3讲 动态规划 #include “stdafx.h“ #include void LCSLength(int m,int n,char *x,char *y,int c7,int b7); void LCS(int i,int j,char *x,int b7); int main(int argc, char* argv) int m=7; int n=6; char x8= ,A,B,C,B,D,A,B; char y7= ,B,D,C,A,B,A; /cout=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,char *x,int b7) if (i=0|j=0) return; if (bij=1) LCS(i-1,j-1,x,b); coutn时，顶点 i+s实际编号为（i+s）mod n。按上述递推式计算出的 min1即为游戏首次删去第i条边后得到的最大得分。 第3讲 动态规划 (3)算法描述 minWeighuTriangulation(int n, int tnn, int snn) for (int i = 1; i minf) mij0=minf; if(mij1si-j+j*bmax) si=si-j+j*bmax; li=j; /计算si-11 si+=header; /计算si 第3讲 动态规划 output(int s, int l,int b) int n=length(s)-1;/s的最大下标 printf(“the optimal value is %dn”,sn); int m=0;/给m赋初值 traceback(n,s,l);/将各最优分段的位数移位 sm=n;/ 将最后一个最优分段的位数移位 printf(“decomposed into %d”,m,”segmentsn”); for(int j=1;j(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上 有尽可能多的连线。换句话说，该问题要求确定导线集 Nets=(i,(i),1in的最大不相交子集。 第3讲 动态规划 记 。N(i,j)的最大不相交子 集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)当i=1时， (2)当i1时， 2.1 j1时 （1）最优子结构及建立递归方程 第3讲 动态规划 （2 2）计算最优值的程序）计算最优值的程序 mnset(int c,int size) / c存放(i)的值， size存放Size(i,j)的值 int n=length(c)-1;/c的大小为11,c0冗余 for(int j=0;j1; i-) if (sizeij!= sizei-1j) netm+= i; j= ci-1; return m; 第3讲 动态规划 70 例. 求解布线问题 61039152478C解 ： for(int j=0;jT(S,b(1)， 设是作业集S在机器M2的等待时间为b(1)情况下的一个最优 调度。则(1)， (2)， (n)是N的一个调度，且该调度 所需的时间为a(1)+T(S,b(1)2n时，算法需要(n2n)计算时间。 第3讲 动态规划 （2 2）算法改进算法改进 由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的 i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃 点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其 全部跳跃点唯一确定。如图所示。 对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部 跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算 ，初始时pn+1=(0，0)。 第3讲 动态规划 例例： n=3，c=6，w=4，3，2，v=5，2，1。 x (0,0) m(4,x) x (2,1) m(4,x-2)+1 x (0,0) (2,1) m(3,x) (3,2) x m(3,x-3)+2(5,3) x (0,0) (2,1) m(2,x) (3,2) (5,3) x m(2,x-4)+5 (4,5) (6,6) (7,7) (9,8) x (0, 0) (2, 1) m(1,x) (3,2) (5,3) (4,5) (6,6) (7,7) (9,8) x (0,0) (2,1) m(3,x) x (0,0) (2,1) m(2,x) (3,2) (5,3) 第3讲 动态规划 函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算 得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j) 的跳跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的 并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t- vi)pi+1。因此，容易由pi+1确定跳跃点集qi+1如下 qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点 ，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是 pi中的跳跃点。除受控跳跃点外，pi+1qi+1中的其它跳 跃点均为pi中的跳跃点。 由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计 算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控 跳跃点得到表pi。 （2 2）算法改进算法改进 第3讲 动态规划 例例： n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。 初始时p6=(0,0)，(w5,v5)=(4,6)。因此， q6=p6(w5,v5)=(4,6)。 p5=(0,0),(4,6)。 q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并 集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于 跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到 p4=(0,0),(4,6),(9,10) q4=p4(6，5)=(6，5)，(10，11) p3=(0，0)，(4，6)，(9，10)，(10，11) q3=p3(2，3)=(2，3)，(6，9) p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11) q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15) p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15) p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15 。第3讲 动态规划 上述算法的主要计算量在于计算跳跃点集 pi(1in)。由于qi+1=pi+1(wi，vi)，故计 算qi+1需要O(|pi+1|)计算时间。合并pi+1和 qi+1并清除受控跳跃点也需要O(|pi+1|)计算时 间。从跳跃点集pi的定义可以看出，pi中的跳 跃点相应于xi,xn的0/