第8章动态规划.

1第8章动态规划2引言•动态规划(DynamicProgramming)是应用数学和计算机科学领域中一个非常重要的算法设计技术•美国数学家RichardBellman于20世纪50年代发明，用于解决多阶段决策过程最优问题•这里的Programming是计划和规划的意思3动态规划的适用条件•1.最优化原理（最优子结构性质）•一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质•使我们可以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。•最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。4•2.无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。5动态规划的适用条件•3.子问题的重叠性(非必要条件)该条件为非必要条件，但是缺少此条件，则动态规划方法与别的方法相比毫无优势。•每次产生的子问题并不是新的子问题，有些子问题被重复计算。•在解某一问题中，相同的子问题反复出现，并且不同子问题的个数又相对较少时，用动态规划是有效的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。6•基本思路：•（1）找出最优解的性质，并刻画其结构特征。•（2）递归地定义最优值。•（3）以自底向上的方式计算出最优值。•（4）根据计算最优值时得到的信息，构造一个最优解。•与分治法比较–都将问题划分为若干个子问题–分治法中各子问题相互独立，而动态规划中各子问题允许相互交叠7•注意：•动态规划一般用于多阶段最优化问题•但是书中•8.1计算二项式系数•8.2.1warshall•并不是最优化问题。•8.2.2floyed•8.3最优二叉查找树•8.4背包问题•才是最优化问题对于交叠的子问题，无需一次又一次的求解，只需将每个较小子问题求解一次并把结果记录在表中。89108.1计算二项式系数•二项式系数，记作C(n,k)或者，是来自于一个n元素集合的k元素组合(子集)的数量(0≤k≤n)•该名字来源于二项式公式•递推式(特性)–C(n,k)=C(n-1,k-1)+C(n-1,k),当nk0–C(n,0)=C(n,n)=1•因此计算C(n,k)变为C(n-1,k-1)和C(n-1,k)两个较小的交叠问题nk()(,0)...(,)...(,)nnniinabCnaCniabCnnb11•动态规划算法–把二项式系数记录在一张n+1行k+1列的表中C(i,j)的值记录在第i行，第j列12•算法Binomial(n,k)//用动态规划算法计算C(n,k)//输入：—对非负整数n=k=0//输出：C(n,k)的值fori←0tondoforj←0tomin(i,k)doifj=0orj=iC[i,j]←1elseC[i,j]←C[i-1,j-1]+C[i-1,j]returnC[n,k]13•时间效率分析–基本操作：加法148.2Warshall算法和Floyd算法•Warshall算法用于计算有向图传递闭包•Floyd算法用于计算全部最短路径158.2.1Warshall算法•传递闭包定义:一个n顶点有向图的传递闭包可以定义为一个n阶布尔矩阵T={tij}，如果从第i个顶点到第j个顶点之间存在一条有效的有向路径，矩阵第i行(1≤i≤n)第j列(1≤j≤n)的元素为1；否则，tij为0换言之：对给定的有向图，求出每个点能到达的所有点16dcba邻接矩阵abcda0100b0001c0000d1010传递闭包abcda1111b1111c0000d1111对给定的有向图，求出每个点能到达的所有点17•求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。•用深度优先查找和广度优先查找如何生成传递闭包？18•动态规划求解思路动态规划将问题分段，Warshall算法是通过一系列n阶矩阵R（k）来构造最终阶段n阶传递闭包矩阵R（n）,k=0,1,…,n-1.WARSHALL算法19R（k）由它的前趋R（k-1）计算得到（分级推进计算）—允许路径中包含前k个顶点作为中间顶点•R（0）——该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的任意顶点出发的路径不含有中间顶点，此即邻接矩阵。•R（1）——允许路径中包含第1个顶点作为中间顶点。WARSHALL算法20•R（2）—允许路径中包含前2个顶点作为中间顶点。•……………..•R（k）—允许路径中包含前k个顶点作为中间顶点。•R（n）—允许路径中包含全部n个顶点作为中间顶点。每个后继矩阵R（k）对其前趋R（k-1）来说，在路径上允许增加一个顶点，因此有可能包含更多的1（增加前为1的在增加后依然为1）。WARSHALL算法21用与或式可以直接写成下式：不包含第k个节点包含第k个节点22•WARSHALL算法的时间复杂度为O(n3)。WARSHALL算法23•算法思想说明–搭桥找路径–选取一个顶点作为桥梁，考察所有顶点，是否可以通过桥梁到达其它的顶点。–用i控制依次选择各顶点做桥梁。–用j控制当选定某顶点做为桥梁时，依次考察所有顶点。–用k控制当桥梁选定时，考察某一顶点通过该桥梁是否可以到达其它顶点。24•外循环第一次，选择0作为桥梁–考察0是否可以通过0到达其它顶点101001–考察1是否可以通过0到达其它顶点111001–考察2是否可以通过0到达其它顶点011000–考察3001110–考察4000011–考察5000011123405012345010100111100002011000300111040000115000011用i控制用j控制用k控制25•外循环第二次，增加1为桥梁–考察0是否可以通过1到达其它顶点101001–考察1是否可以通过1到达其它顶点111001–考察2是否可以通过1到达其它顶点111001–考察3001110–考察4000011–考察5000011012345010100111110012011000300111040000115000011123405可看成是动态规划的阶段性，意味着可以通过0，1。即当前是否有路径可以建立在前一阶段的路径基础上。26•循环6次结束，M最终记录了闭包矩阵的信息。•实现细节说明之一–if(M[j，i]＝T)–for(k=1;i＝n;i++){…}–当M[j，i]＝F时说明什么？–考察的顶点j到桥梁i没有路径，–也就意味着该顶点不可能通过选择的桥梁建立到其它顶点的路径，因此不必考察它通过该桥梁是否可以到达其它顶点，即内循环不用做。278.2.2Floyd算法•完全最短路径问题：找到从每个顶点到其他所有顶点之间的距离(最短路径的长度)dcba23671权重矩阵0∞3∞20∞∞∞7016∞∞0距离矩阵01034205677016169028•Floyd算法中体现的动态规划思路：•用一系列n阶矩阵来计算一个n顶点加权图的距离矩阵•矩阵D(k)的第i行第j列的元素dij(k)为从第i个顶点到第j个顶点之间最短路径的长度，并且路径的每一个中间顶点的编号不大于k(0)(1)()(),...,,,...,kknDDDD29•D(0)为权重矩阵D(n)为距离矩阵•（1）找出最优解的性质，并刻画其结构特征•（2）并递归地定义最优值。(0)()(1)(1)(0)1,,min{,}kkkijijijijikkjkdwdddd当时不包含第k个节点：dij(k-1)包含第k个节点：dik(k-1)+dkj(k-1)k-130注：从任意节点i到任意节点j的最短路径不外乎2种可能，Case1.直接从i到j，Case2.从i经过若干个节点k到j。•我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)Dis(i,j)是否成立，•如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)，•这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。31•（3）以自底向上的方式计算出最优值。•（4）根据计算最优值时得到的信息，构造一个最优解。32dcba23671D(0)0∞3∞20∞∞∞7016∞∞0D(1)0∞3∞205∞∞7016∞90D(2)0∞3∞205∞97016∞90D(3)010342056970161690D(4)01034205677016169033•算法Floyd(W[1..n,1..n])//实现计算完全最短路径的Floyd算法//输入：图的权重矩阵W//输出：包含最短路径长度的距离矩阵for1todofor1todoforj1todo[,]min{[,],[,]+[,]}returnDWkninnDijDijDikDkjD算法效率Θ(n3)34问题描述•给定n个键{a1,a2,a3,......,an},其相应的查找概率为{p1,p2,p3,......,pn}。构成最优BST,表示为T1n，求这棵树的平均查找次数C[1,n]（耗费最低)。•换言之，如何构造这棵最优BST，使得C[1,n]最小。8.3最优二叉查找树35•它在查找中的平均比较次数是最低的平均比较次数的计算：所有节点上概率与比较次数的乘积之和•例子：非最优二叉查找树ABCDABCD36•动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。•对于最优BST问题，利用减一技术和最优性原则，如果前n-1个节点构成最优BST，加入一个节点an后要求构成规模n的最优BST。•按n-1,n-2,...,2,1递归，问题可解。自底向上计算：C[1,2]→C[1,3]→...→C[1,n]。37•用C[i,j]表示由{a1,a2,......,an}构成的BST的耗费。其中1≤i≤j≤n。这棵树表示为Tij。•从中选择一个键ak作根节点，它的左子树为Ti,k-1，右子树为Tk+1,j。要求选择的k使得整棵树的平均查找次数C[i,j]最小。•左右子树递归执行此过程。（根的生成过程）3839•可能的最优二叉查找树形式•其中Ti,k-1,Tk+1,j是两棵最优二叉查找子树•注意这只是可能的最优二叉查找树形式，注意树的表示符号40C[i,j]表示这棵树中成功查找的最小的平均查找次数41•考虑用二维表记录C[i,j]•当i在1和n+1之间时，C[i,i-1]为多少？•当i在1和n之间时，C[i,i]为多少？•我们的目标是求什么？0p1目标0p2C[i,j]pn001jnn+11i仅求出C[1,n]是否可以获得最优二叉查找树本身42•例：–键ABCD–查找概率0.10.20.40.3初始表43最终表计算C[1,2]44•为了获得最优二叉树本身需要记录什么？45得到最优二叉查找树46•算法OptimalBST(P[1..n])//用动态规划算法求最优二叉查找树//输入：一个n个键的有序列表的查找概率数组P[1..n]//输出：在最优BST中成功查找的平均比较次数，以及最优BST中子树的根表Rfori←1tondoC[i,i-1]←0C[i,i]←P[i]R[i,i]←iC[n+1,n]←iford←1ton-1do//对角线计数fori←1ton-ddoj←i+dminval←∞fork←itojdoifC[i,k-1]+C[k+1,j]minvalminval←C[i,k-1]+C[k+1,j];kmin←kR[i,i]←ksum←P[i];fors←i+1tojdosum←sum+P[s]C[i,i]←minval+sumR