动态规划课件

第三章动态规划

(DynamicProgramming)1内容动态规划概述基本思想基本原理基本要素动态规划算法的设计与实现矩阵连乘、凸多边形最优三角剖分最长公共子序列、最大子段和多边形游戏、图像压缩电路布线、0-1背包问题2基本思想动态规划是运筹学的一个分支。1950s，美国数学家RichardBellman在研究多阶段决策过程的优化问题时，提出了这一策略。使整个活动的总体效果达到最优的问题，称为多阶段决策问题。多阶段决策过程是指可以按照时间顺序将原问题分解成若干相互联系的阶段，在每一阶段都要作出决策。3多阶段决策问题及多阶段决策过程阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。状态：各阶段开始时的客观条件叫做状态。决策：当各阶段的状态确定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。状态转移：根据上一阶段的状态和决策来导出本阶段的状态。由第k-1段的状态Sk-1和决策Uk-1确定第k段的状态Sk。策略：各段决策确定后，整个问题的决策序列就构成一个策略。使整个问题达到最优效果的策略就是最优策略。最优策略的子策略也是最优策略。基本思想4基本思想动态规划策略通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。动态Dynamic在一定条件下，当前阶段和下一阶段的状态的转换。规划Programming建立状态转移方程（或称各阶段间的递推关系式）、将各个阶段的状态以表格式方法存储。表格式方法(tabularmethod)：用一个表来记录所有已解决的子问题的解。以空间换时间(space-for-timetradeoff)。5例如，找零钱问题当硬币系统为2角5分、1角、5分、1分时，要找给顾客6角3分钱，怎么做？一般思维：0.63=2个0.25+1个0.1+3个0.01所拿出的硬币个数是最少的再如当硬币系统为4分、3分、1分时，要找给顾客6分钱，怎么做？一般思维：6=1个4分+2个1分2个3分才是最优解！6Solveforallof1¢,2¢,3¢,...,6¢Tomake1¢(1coin)Tomake2¢,1¢+1¢(1coin+1coin=2coins)Tomake3¢,justusethe3¢coin(1coin)Tomake4¢,justusethe4¢coin(1coin)Tomake5¢,try1¢+4¢(1coin+1coin=2coins)2¢+3¢(2coins+1coin=3coins)Tomake6¢,try1¢+5¢(1coin+2coins=3coins)2¢+4¢(2coins+1coin=3coins)3¢+3¢(1coin+1coin=2coins)子问题原问题Example:CountingCoins.Findtheminimumnumberofcoins(1¢,3¢,and4¢)tomakeanyamount.For6¢:√bestsolution√bestsolution7最优子结构性质(optimalsubstructure)原问题的最优解包含了子问题的最优解。该性质使我们能够以自底向上的方式递归地从子问题的最优解逐步构造出原问题的最优解。重叠子问题(overlappingsubproblem)有些子问题被反复计算多次（前一阶段的状态带到当前阶段，当前阶段的状态带到下一阶段）。基本要素8最优子结构/最优化原理最优策略的子策略也是最优策略原问题的最优解包含了子问题的最优解子问题的最优解不一定组成原问题的最优解FindtheminimumnumberofUScoins(1,2,5,10)tomakeanyamount.

For13¢Theoptimalsolutionto7¢is5¢+2¢,andTheoptimalsolutionto6¢is5¢+1¢,butTheoptimalsolutionto13¢isnot(5¢+2¢)+(5¢+1¢)Butthereissomewayofdividingup13¢intosubsetswithoptimalsolutions(say,11¢+2¢)thatwillgiveanoptimalsolutionfor13¢Hence,theprincipleofoptimalityholdsforthisproblem9重叠子问题与分治法类似，动态规划也是将待求解问题分解成若干子问题。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。例，fibonacci(5)=fibonacci(4)+fibonacci(3);fibonacci(4)=fibonacci(3)+fibonacci(2)如果能够记录已解决的子问题的答案，而在需要时再找出，就可以避免大量重复计算。表格式方法10矩阵连乘

(matrix-chainmultiplication)给定n个矩阵{A1,A2,…,An}，其中，Ai和Ai+1是可乘的，现要计算出这n个矩阵的连乘积A1A2,…,An。矩阵A和矩阵B可乘的条件：A的列数等于B的行数。若A是一个p×q矩阵，B是一个q×r矩阵，则C=A×B是一个p×r矩阵，乘法次数为pqr。连乘：计算次序（完全加括号方式）对乘法次数有很大影响。该问题是最优性质问题：即求解矩阵连乘的最优计算次序，使得依此次序计算矩阵连乘需要的乘法次数最少。11蛮力算法设n个矩阵连乘有P(n)个不同的计算次序。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)，所以P(n)的递归关系式为：动态规划算法将矩阵连乘积AiAi+1...Aj简记为A[i:j]，这里i≤j由于矩阵可乘，则设Ai的维数为Pi-1×Pi设A[i:j]的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为

(AiAi+1...Ak)(Ak+1Ak+2...Aj)总的计算量=A[i:k]的计算量+A[k+1:j]的计算量+A[i:k]和A[k+1:j]相乘的计算量(Pi-1PkPj)12分析最优解的结构：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的；递归定义最优值：设计算A[i:j](1≤i≤j≤n)所需要的最少的乘法次数为m[i,j]，则原问题的最优值为m[1,n]；计算最优值：依据其递归式以自底向上的方式进行计算。记录已解决的子问题答案。设的维数为

的位置只有种可能13例，5个矩阵连乘，行列数如下：A1A2A3A4A52*33*44*55*66*7024641242080601502760120288021001234234344记录最优值记录断开位置(((A1A2)A3)A4)A514计算最优值：MatrixChain(p,m,s)//p={p0,p1,…,pn}，Ai的维数是p[i-1]*p[i]n=p.length-1//对角线为单一矩阵

fori=1tondom[i][i]=0//矩阵链长度

forr=2tondo

fori=1ton–r+1doj=i+r–1//相邻矩阵m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]s[i][j]=i//矩阵链长度>2时找断开位置

fork=i+1toj-1dot=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]

ift<m[i][j]m[i][j]=ts[i][j]=k构造最优解：Traceback(i,j,s)

ifi=jreturnTraceback(i,s[i][j],s)Traceback(s[i][j]+1,j,s)15算法分析MatrixChain的计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为θ(1)，而3重循环的总次数为θ(n3)。因此算法的计算时间为θ(n3)。T(n)=填表时间(计算最优值)+查表时间(构造最优解)=填写二维表×遍历断开位置+查表时间

=θ(n3)+θ(n)=θ(n3)空间复杂性：表格大小，θ(n2)16动态规划算法的基本步骤分析最优解的结构；递归定义最优值（由最优子结构性质建立子问题最优值的递归关系）；决策：选择全部可能解中的最优解（最大/小）（以自底向上的方式）计算最优值；（根据计算最优值时得到的信息）构造最优解。17凸多边形最优三角剖分

(TriangulationofaConvexPolygon)凸多边形就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形的其他各边均在此直线的同旁，那么这个多边形就叫做凸多边形。用顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}，表示有n条边v0v1,v1v2,…,vn-1v0若vi和vj是不相邻的顶点，则线段vivj称为弦；弦vivj将多边形分割成两个多边形{vi,vi+1,…,vj}和{vj,vj+1,…,vi}凸多边形的三角剖分是将凸多边形分割成互不相交的三角形的弦的集合。18凸多边形最优三角剖分给定一个凸多边形P={v0,v1,…,vn-1}，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该三角剖分中诸三角形上权之和为最小。19本质上与矩阵连乘的最优计算次序问题极为相似表达式的语法树是一个完全二叉树：叶结点、内结点、根节点((A1(A2A3))(A4(A5A6)))所对应的语法树矩阵连乘中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vj。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘A[i+1:j]20vkvkvk与矩阵连乘的算法相同时间复杂性：θ(n3)；空间复杂性：θ(n2)最优子结构性质：若凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形v0vkvn，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vK+1,…,vn}的权之和。定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值。v0v1vn21最长公共子序列

(LongestCommonSubsequence)给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xi序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。22分析最优解的结构：设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则若xm=yn

，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。

//Xm-1={x1,x2,…,xm-1};Yn-1={y1,y2,…,yn-1};Zk-1={z1,z2,…,zk-1}若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。递归定义最优值：用c[i][j]记录Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。建立递归关系如下：23计算最优值：LcsLength(x,y,b)m=x.length-1n=y.length-1

fori=1tomdoc[i][0]=0

fori=1tondoc[0][i]=0

fori=1tomdo

forj=1tondo

ifx[i]=y[j]c[i][j]=c[i-1][j-1]+1b[i][j]=对角线值

elseifc[i-1][j]>=c[i][j-1]c[i][j]=c[i-1][j]b[i][j]=上值

elsec[i][j]=c[i][j-1]b[i][j]=左值构造最优解：Lcs(i,j,x,b)

ifi=0orj=0return

ifb[i][j]=对角线值

Lcs(i-1,j-1,x,b)System.out.print(x[i])

else

ifb[i][j]=上值

Lcs(i-1,j,x,b)

elseLcs(i,j-1,x,b)24算法的改进在算法LcsLength和Lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在O(1)时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。25算法分析T(n)=计算最优值（填表）的时间+构造最优解的时间=θ(mn)+θ(m+n)空间复杂性：表格大小θ(mn)26最大子段和

(Maximumsubarray)给定由n个整数组成的序列a1,a2,…,an，求该序列形如（即连续的）的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为27蛮力算法：扫描任意个数的子段的和改进算法一：表格式方法tabularmethod，利用已得到的结果，避免重复计算。θ(n2)表格中存放的并不是各阶段的最优值！能否进一步改进？该问题的最好情况输入：全负或全正。θ(n)改进算法二：分治法θ(nlogn)改进算法三：动态规划θ(n)28设，即b[j]=max(a[i]+a[i+1]+..+a[j])，1≤i≤j≤n

则根据b[j]的定义，可以看出当b[j-1]>0时，无论a[j]为何值，b[j]=b[j-1]+a[j]当b[j-1]<0时，无论a[j]为何值，b[j]=a[j]故29多边形游戏

(PolygonGame)有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏规则：第一步，将一条边删除；随后n-1步按以下方式操作：选择一条边E以及由E连接着的2个顶点v1和v2；用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2。将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有的边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。对于给定的多边形，计算出最高得分，且列出所有得到这个最高得分首次被删除的边的编号。-7452+**+213430蛮力算法：穷举法解决此问题的复杂性是n!-7452+**+2134-7452+*+214-242+*24-44+201号边与2号边之间的顶点的数值是1号顶点的数值…最后一个数值对应于与n号边和1号边相关联的顶点。31设p(i,j)是从顶点i开始，长度为j（即链中有j个顶点）的顺时针链，表示为v[i],op[i+1],…,v[i+j-1]如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1)，则可在op[i+s]处将链分割为2个子链p(i,s)和p(i+s,j-s)设m1是对子链p(i,s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b，c≤m2≤d在op[i+s]处合并后的值为m=(m1)op[i+s](m2)当op[i+s]=‘+’时，a+c≤m≤b+d当op[i+s]=‘*’时，min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}32为了求链合并的最大值，必须同时求子链合并的最大值和最小值。设m[i,j,0]是p(i,j)合并的最小值，m[i,j,1]是p(i,j)合并的最大值。设子链p(i,s)和p(i+s,j-s)的最大值和最小值分别为：a=m[i,s,0],b=m[i,s,1],c=m[i+s,j-s,0],d=m[i+s,j-s,1]时间复杂性（与矩阵连乘相同）为：θ(n3)33-7452+**+2134-7-3-6-304840-16210-405-22-112341234ijm[i,j,0]-7-3133484033210375-22612341234ijm[i,j,1]p(i,j)是从顶点i开始，长度为j（即链中有j个顶点）的顺时针链。m[i,j,0]是p(i,j)合并的最小值，m[i,j,1]是p(i,j)合并的最大值。34图像压缩

(ImageCompression)计算机中常用像素点灰度值序列{p1,p2,…,pn}表示图像。其中整数pi表示像素点i的灰度值。通常灰度值的范围是0~255（需要用8位表示一个像素）图像的变位压缩格式是将所给的像素点序列{p1,p2,…,pn}分割成m个连续段S1,S2,…,Sm。第i个像素段Si中有l[i]个像素，且该段中每个像素都只用b[i]位来表示。设表示前i-1个像素段所包含的像素

个数，则第i个像素段Si

：35设，则hi

b[i]

8，因此需要用3位表示b[i]。如果限制1

l[i]

255，则需要用8位表示l[i]。因此，第i个像素段所需的存储空间为l[i]*b[i]+11位。按此格式存储像素序列{p1,p2,…,pn}，需要位的存储空间。图像压缩问题要求确定像素序列{p1,p2,…,pn}的最优分段（确定l[i]和b[i]），使得依此分段所需的存储空间最少。其中，每个分段的长度不超过256位。36最优子结构性质原问题的最优解：设l[i]和b[i]，1im是{p1,p2,…,pn}的一个最优分段子问题的最优解：l[1]和b[1]是{p1,…,pl[1]}的一个最优分段，且l[i]和b[i]，2im是{pl[1]+1,…,pn}的一个最优分段。设s[i]是{p1,…,pi}的最优分段所需的存储位数，则时间复杂性由于对k的循环次数不超过256，故对每一个确定的i，可在时间θ(1)内完成s[i]的计算。因此整个算法所需的计算时间为θ(n)其中：{p1,p2,…,pi}{p1,…,pi-k,pi-k+1,…,pi}S[i]

当前分段S[i-k]37电路布线在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤i<j≤n，第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。在制作电路时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题就是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。38设的最大不相交子集为MNS(i,j)，且Size(i,j)=|MNS(i,j)|当i=1时，当i>1时(1)j<π(i)，。在这种情况下，N(i,j)=N(i-1,j)，故MNS(i,j)=MNS(i-1,j)，从而Size(i,j)=Size(i-1,j)。π(i)iN(i,j)j39(2)j≥π(i)若(i,π(i))∈MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)，有t<i且π(t)<π(i)，否则(t,π(t))和(i,π(i))相交；

MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集，否则N(i-1,π(i)-1)的最大不相交子集MNS(i-1,π(i)-1)并上{(i,π(i))}（包含于）是N(i,j)中比MNS(i,j)更大的不相交子集。与MNS(i,j)的定义矛盾。所以，Size(i,j)=Size(i-1,π(i)-1)＋1iπ(i)jN(i,j)i-1π(i)-140若，则对任意(t,π(t))∈MNS(i,j)有t<i。从而。故Size(i,j)≤Size(i-1,j)另外，，故Size(i,j)≥Size(i-1,j)所以，Size(i,j)=Size(i-1,j)iπ(i)jN(i,j)tπ(t)41(1)当i=1时(2)当i>1时42实例练习对应关系为：(1,8),(2,7),(3,4),(4,2),(5,5),(6,1),(7,9),(8,3),(9,10),(10,6)43计算最优值123456789101000000011120000001111300011111114011111111150111222222611112222227111122223381122222233911222222341011222333341,82,73,44,25,56,17,98,39,1010,6i,π(i)ij44构造最优解123456789101000000011120000001111300011111114011111111150111222222611112222227111122223381122222233911222222341011222333341,82,73,44,25,56,17,98,39,1010,6iji,π(i)450-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1：在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。0-1背包问题是一个特殊的整数规划问题。作个假设找出一个n元0-1向量(x1,x2,…,xn)，使得46Theexhaustivesearchapproachtothisproblemleadstoconsideringallthesubsetsofthesetofnitemsgiven,computingthetotalweightofeachsubsetinordertoidentifyfeasiblesubsets,andfindingasubsetofthelargestvalueamongthem.Theknapsackproblemisthebest-knownexamplesofso-calledNP-hardproblem.Nopolynomial-timealgorithmisknownforanyNP-hardproblem.Moreover,mostcomputerscientistsbelievethatsuchalgorithmsdonotexist,althoughthisveryimportantconjecturehasneverbeenproven.47分析最优子结构性质原问题的最优解：设(y1,y2,…,yn)是给定n种物品在背包载重为c时的一个最优解子问题的最优解：则(y2,…,yn)是除了第一个物品之外的n-1个物品在背包载重为c-w1y1时的一个最优解。反证法：如若不然，设(z2,…,zn)是上述子问题的一个最优解，而(y2,…,yn)不是。48Letusconsideraninstancedefinedbythefirstiitems,1in,withweightsw1,w2,…,wi,valuesv1,v2,…,vi,andknapsackcapacityj,1jc.LetV[i,j]bethevalueofanoptimalsolutiontothisinstance,i.e.,thevalueofthemostvaluablesubsetofthefirstiitemsthatfitintotheknapsackofcapacityj.Wecandivideallthesubsetsofthefirstiitemsthatfittheknapsackofcapacityjintotwocategories:thosethatdonotincludetheithitemandthosethatdo.49Amongthesubsetsthatdonotincludetheithitem,thevalueofanoptimalsubsetis,bydefinition,V(i-1,j)Amongthesubsetsthatdoincludetheithitem(j-wi0),anoptimalsubsetismadeupofthisitemandanoptimalsubsetofthefirsti-1itemsthatfitintotheknapsackofcapacityj-wi.Thevalueofsuchanoptimalsubsetisvi+V(i-1,j-wi)OutgoalistofindV(n,c),themaximalvalueofasubsetofthengivenitemsthatfitintotheknapsackofcapacityc,andanoptimalsubsetitself.50算法复杂性：θ(nc)。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。装不下能装但不装装设V(i,j)是背包容量为j，可选择物品为前i个(x1,x2,…,xi)时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算V(i,j)的递归式5100000000goalni-1iwivij-wijcV[i-1,j-wi]V[i-1,j]V[i,j]itemweightvalue12122