第三部分-动态规划.ppt

第三章动态规划(DynamicProgramming),内容,动态规划概述基本思想基本原理基本要素动态规划算法的设计与实现矩阵连乘、凸多边形最优三角剖分最长公共子序列、最大子段和多边形游戏、图像压缩电路布线、0-1背包问题,基本思想,动态规划是运筹学的一个分支。1950s，美国数学家RichardBellman在研究多阶段决策过程的优化问题时，提出了这一策略。使整个活动的总体效果达到最优的问题，称为多阶段决策问题。多阶段决策过程是指可以按照时间顺序将原问题分解成若干相互联系的阶段，在每一阶段都要作出决策。,多阶段决策问题及多阶段决策过程阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。状态：各阶段开始时的客观条件叫做状态。决策：当各阶段的状态确定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。状态转移：根据上一阶段的状态和决策来导出本阶段的状态。由第k-1段的状态Sk-1和决策Uk-1确定第k段的状态Sk。策略：各段决策确定后，整个问题的决策序列就构成一个策略。使整个问题达到最优效果的策略就是最优策略。最优策略的子策略也是最优策略。,基本思想,基本思想,动态规划策略通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。动态Dynamic在一定条件下，当前阶段和下一阶段的状态的转换。规划Programming建立状态转移方程（或称各阶段间的递推关系式）、将各个阶段的状态以表格式方法存储。表格式方法(tabularmethod)：用一个表来记录所有已解决的子问题的解。以空间换时间(space-for-timetradeoff)。,例如，找零钱问题当硬币系统为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分才是最优解！,Solveforallof1,2,3,.,6Tomake1(1coin)Tomake2,1+1(1coin+1coin=2coins)Tomake3,justusethe3coin(1coin)Tomake4,justusethe4coin(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,bestsolution,最优子结构性质(optimalsubstructure)原问题的最优解包含了子问题的最优解。该性质使我们能够以自底向上的方式递归地从子问题的最优解逐步构造出原问题的最优解。重叠子问题(overlappingsubproblem)有些子问题被反复计算多次（前一阶段的状态带到当前阶段，当前阶段的状态带到下一阶段）。,基本要素,最优子结构/最优化原理,最优策略的子策略也是最优策略原问题的最优解包含了子问题的最优解子问题的最优解不一定组成原问题的最优解FindtheminimumnumberofUScoins(1,2,5,10)tomakeanyamount.For13Theoptimalsolutionto7is5+2,andTheoptimalsolutionto6is5+1,butTheoptimalsolutionto13isnot(5+2)+(5+1)Butthereissomewayofdividingup13intosubsetswithoptimalsolutions(say,11+2)thatwillgiveanoptimalsolutionfor13Hence,theprincipleofoptimalityholdsforthisproblem,重叠子问题,与分治法类似，动态规划也是将待求解问题分解成若干子问题。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。例，fibonacci(5)=fibonacci(4)+fibonacci(3);fibonacci(4)=fibonacci(3)+fibonacci(2)如果能够记录已解决的子问题的答案，而在需要时再找出，就可以避免大量重复计算。表格式方法,矩阵连乘(matrix-chainmultiplication),给定n个矩阵A1,A2,An，其中，Ai和Ai+1是可乘的，现要计算出这n个矩阵的连乘积A1A2,An。矩阵A和矩阵B可乘的条件：A的列数等于B的行数。若A是一个pq矩阵，B是一个qr矩阵，则C=AB是一个pr矩阵，乘法次数为pqr。连乘：计算次序（完全加括号方式）对乘法次数有很大影响。该问题是最优性质问题：即求解矩阵连乘的最优计算次序，使得依此次序计算矩阵连乘需要的乘法次数最少。,蛮力算法设n个矩阵连乘有P(n)个不同的计算次序。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)，所以P(n)的递归关系式为：动态规划算法将矩阵连乘积AiAi+1.Aj简记为Ai:j，这里ij由于矩阵可乘，则设Ai的维数为Pi-1Pi设Ai:j的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ik2时找断开位置fork=i+1toj-1dot=mik+mk+1j+pi-1*pk*pjiftmijmij=tsij=k,构造最优解：Traceback(i,j,s)ifi=jreturnTraceback(i,sij,s)Traceback(sij+1,j,s),算法分析MatrixChain的计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为(1)，而3重循环的总次数为(n3)。因此算法的计算时间为(n3)。T(n)=填表时间(计算最优值)+查表时间(构造最优解)=填写二维表遍历断开位置+查表时间=(n3)+(n)=(n3)空间复杂性：表格大小，(n2),动态规划算法的基本步骤,分析最优解的结构；递归定义最优值（由最优子结构性质建立子问题最优值的递归关系）；决策：选择全部可能解中的最优解（最大/小）（以自底向上的方式）计算最优值；（根据计算最优值时得到的信息）构造最优解。,凸多边形最优三角剖分(TriangulationofaConvexPolygon),凸多边形就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形的其他各边均在此直线的同旁，那么这个多边形就叫做凸多边形。用顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1，表示有n条边v0v1,v1v2,vn-1v0若vi和vj是不相邻的顶点，则线段vivj称为弦；弦vivj将多边形分割成两个多边形vi,vi+1,vj和vj,vj+1,vi凸多边形的三角剖分是将凸多边形分割成互不相交的三角形的弦的集合。,凸多边形最优三角剖分给定一个凸多边形P=v0,v1,vn-1，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该三角剖分中诸三角形上权之和为最小。,本质上与矩阵连乘的最优计算次序问题极为相似表达式的语法树是一个完全二叉树：叶结点、内结点、根节点(A1(A2A3)(A4(A5A6)所对应的语法树矩阵连乘中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vj。三角剖分中的一条弦vivj，i0时，无论aj为何值，bj=bj-1+aj当bj-11时(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),i,N(i,j),j,(2)j(i)若(i,(i)MNS(i,j)，则对任意(t,(t)MNS(i,j)，有ti且(t)2n时，算法需要(n2n)计算时间。,装不下,能装但不装,装,设V(i,j)是背包容量为j，可选择物品为前i个(x1,x2,xi)时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算V(i,j)的递归式,0,0,0,0,0,0,0,0,goal,n,i-1,i,wi,vi,j-wi,j,c,Vi-1,j-wi,Vi-1,j,Vi,j,Capacityj,j,i,备忘录方法(MemoryFunctions),对于原问题的解而言，不是所有子问题的解都是必要的。用一个表格来保存已解决的子问题的答案。为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊值，表示该子问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是特殊值，则表示该子问题第一次遇到，则此时计算出该子问题的解并保存在相应的记录项中。若记录项中存储的已不是特殊值，则表示该子问题已被计算过，其相应的记录项中存储的是该子问题的解。,j,i,Ex.0-1knapsackproblem,Ex.matrix-chainmultiplication,A1A2A3A4,1,2,3,4,5,6,4,2,1,5,3,6,总结,动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。初始状态决策决策决策结束状态,总结,划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。,总结,确定了动态规划的阶段、状态、决策这三要素，整个求解过程就可以用一个最优决策表来描述，一般地，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题在某个阶段某个状态下的最优值。如最短路径，最长公共子序列，最大价值等填表的过程就是根据递推关系，从第1行第1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求