【文档说明】算法设计与分析基础第2版算法分析第8章课件.ppt，共(42)页，370.035 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-7196.html

以下为本文档部分文字说明：

动态规划(dynamicprogramming)是一种算法设计技术，它有着相当有趣的历史。作为一种使多阶段决策过程最优的通用方法，它是在20世纪50年代由一位卓越的美国数学家RichardBellman所发明的。因此，这个技术

名字中的“Programming”是计划和规划的意思，不是代表计算机中的编程。它作为一种重要的工具在应用数学中的价值被大家认同以后，起码在计算机科学的圈子里，人们不仅用它来解决特定类型的最忧问题，而且最终把它作为一种通用的算法设计技术来使用。在这里，我们

正是从这个角度来考虑这种技术的。如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术来解决它。一般来说，这样的于问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。动态规

划法建议，与其对交叠的子问题一次又一次地求解，还不如对每个较小的子问题只求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解8.1计算二项式系数•计算二项式系数是把动态规划应用于非最优化问题的一个标准例子•在二项式系数的多种特性之中，只

关心两种：当n>k>0时，C(n,k)＝C(n-1,k-1)+C(n-1,k)•以及C(n,0)=C(n,n)=1•为了计算c(n,k)，一行接一行地填充下表，从行0开始，到行n结束•算法Binomial(n,k)•//用动态规划算法计算C(n,k)•//输入：—对非负整

数n>=k>=0•//输出：C(n,k)的值•fori←0tondo•forj←0tomin(i,k)do•ifj=0orj=k•C[i,j]←1•elseC[i,j]←C[i-1,j-1]+C[i-1,j]•returnC[n,k]•该算法的时间效率如何呢?显然，该算法的基本操作是加法8.2

Warshall算法和FLoyd算法•8．2．2Warshall算法一个有向图的邻接矩阵A={aij}是一个布尔矩阵，当且仅当从第i个顶点到第j个顶点之间有一条有向边时，矩阵第i行第j列的元素为1。定义一个n顶点有向图的传递闭包可以定义

为一个n阶布尔矩阵T={tij}，如果从第i个到顶点到第j个顶点之间存在一条有效的有向路径，矩阵第i行(1≤i≤n)第j列(1≤j≤n)的元素为1；否则，tij为0。•我们可以在深度优先查找和广度优先查找的帮助下生成有向图的传递闭包。从第i个顶点开始，无论采用哪种

遍历方法，都能够得到通过第i个顶点访问到的所有顶点的信息，因此，传递闭包的第i行的相应列置为了1。以每个顶点为起始点做一次这样的遍历就生成了整个图的传递闭包。•Warshall算法通过一系列n阶布尔矩阵来构造一个给定的n个顶点有向图的传递

闭包，算法的中心思想是，任何中的所有元素都可以通过它在序列（8.5）中的直接前趋计算得到。：式(8．7)是Warshall算法的核心•算法Warshall（A[1..n,1..n]）•//实现计算传递闭包的War

shall算法•//输入：包括n个顶点有向图的邻接矩阵A•//输出：该有向图的传递闭包8.2.2计算完全最短路径的Floyd算法绐定一个加权连通图（无向的或有向的），完全最短路径问题要求找到从每个顶点到其他所有顶点之间的距离(最

短路径的长度)•Floyd算法通过一系列n阶矩阵来计算一个n顶点加权图的距离矩阵：•每一个这种矩阵都包含了所讨论的矩阵在特定路径约束下的最短路径的长度•每条这种路径都由两条路径构成：一条从vi到vk的路径，路径中每个中间顶点的编号都大于K一1；

一条从vi到vj的路径，路径中每个中间顶点的编号也都不大于k-1.算法Floyd(W[1..n,1..n])//实现计算完全最短路径的Floyd算法//输入：图的权重矩阵W//输出：包含最短路径长度的距离矩阵8.3最优二叉树•考虑分别以概率0.1，0.2，0.4，0.3

来查找4个键A,B,C,D。包含这些键的二叉查找树有14种不同的可能ABCDABCD•在成功查找时，第一棵树的平均键值比较次数为0.1*1+0.2*2+0.4*3+0.3*4＝2.9，而第二棵树是0.1*2+0.2*1+0.4*2+0.3

*3＝2.1。•作为一个通用的算法，这种穷举查找方法是不现实的：包含n个键的二叉查找树的总数量等于第n个卡塔兰数当n>0时，•设a1,……an是从小到大排列的互不相等的键，p1,……pn是它们的查找概率。是由

键a1,……an构成的二叉树，C[i,j]是在这棵树中成功查找的最小的平均查找次数。•要求出该问题的所有较小实例的C[i,j]值。为了推导出动态规划算法中隐含的递推关系，需要考虑从键ai,……aj中选择一个根ak的所有可能的方法。•对于这样一棵二叉树来说，它的根包含了键ak，它的左子树

中的键是最优排列的，它的右子树中的键也是最优排列的。•当1≤i≤n+1时，C[i,i-1]＝0，这可以解释为空树的比较次数。请注意，这个公式意味着•二维表给出了用公式(8.11)来计算C[i,j]时需要用到的一些值；它们是i行中位于j列左边的列上的值，以及j列

中在i行下边的行上的值。箭头指出了需要对元素求和的一对对单元，然后求出这些元素对的和的最小值，把它作为C[i,j]的值记录下来。这意味着我们要沿着表格的对角线填写表格，从全部是0的主对角线和右上方给定概率Pi(1<=i<=n)的对角线开始，并向着右上

角移动。0p1目标0p2C[i,j]Pn001jnn+1例1让我们对本节开头使用的4个键的集合应用该算法，来给大家一个感性的认识：键ABCD查找概率0.10.20.40.3•算法OptimalBST(P[1..n])•//用动态规划算法求最优二叉查找树•//输入：

一个n个键的有序列表的查找概率数组P[1..n]•//输出：在最优BST中成功查找的平均比较次数，以及最优BST中子////树的根表R•Fori←1tondo•C[i,i-1]←0•C[i,i]←P[i]•R[i,i]←i•C[n+1,n]←i•Ford←1ton-1do//对角线计数•For

i←1ton-ddo•j←i+d•minval←∞•fork←itojdo•ifC[i,k-1]+C[k+1,j]<minval•minval←C[i,k-1]+C[k+1,j];kmin←k•R[i,i]←k•sum←P[i];fors←i+1tojdosum←su

m+P[s]•C[i,i]←minval+sum•ReturnC[1,n],R•该算法的空间效率显然是平方级的；这个算法的时间效率是立方级的。一个更详细的分析告诉我们，根表中的单元格总是沿着每一行和每一列非降序排列的。这就把R[i，j]值限定在范围R[

i,j-1],….R[i+1,j].间，使得我们有可能把该算法的运行时间降低到。8.4背包问题和记忆功能•8.4.1背包问题•为了设计一个动态规划算法，需要推导出一个递推关系，用较小于实例的解的形式来•表不背包问题的实例的解。让我们来考虑

一个由前i个物品(1≤i≤n)定义的实例，物品的重量分别为w1,…,wi、价价值分别为v1，…，vi，背包的承重量为j(1≤j≤W)。设V[i,j]为该实例的最优解的物品总价值，也就是说，是能够放进承重量为j的背包中的前i个物品中最有价值子集的总价值。可以把前i个物品中能够放进承重

量为j的背包中的子集分成两个类别：那些包括第j个物品的子集和那些不包括第J个物品曲子集。•有下面的结论：•1.根据定义，在不包括第i个物品的子集中，最优子集的价值是V[i-1,j].•2．在包括第i个物品的子集中(因此，j—w≥0)，员优子集是由该物品

和前i-1个物•品中能够放进承重量为卜wj的背包的最优子集组成。这种最忧子集的总价值等于•Vi+V[i-1,j-wi]。•因此，在前j个物品中员优解的总价值等于这两个价值中的较大值。当然，如果第i个•物品不能放进背包，从前i个

物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个观察结果导致了下面这个递推式：•Max{V[i-1,j],vi+V[i-1,j-wi]}如果j-wi≥0•V[i，j]﹛•V[i-1,j]如果j-wi<0•我们可以很容易地这样定义初始条件：•当j≥0时；V[0，i]

=0;当i≥0时,V[i,0]=0•我们的目标是求V[n，W]，即n个给定物品中能够放进承重量为肛的背包的子集的最大总价值，以及最优子集本身。8.4.2记忆功能•该方法用自顶向下的方式对给定的问题求解，但还需要维护一个类似自底向上动态规•划算法使用的表格。一开始的时候，用一种“null”符号创

始化表中所省的单元，用来表•明它们还没有被计算过(在这里可以便用一种称为虚拟初始化的技术——参见习题7．1的•第8题)。然后，一日需要计算个新的值．该方法先检查表中相应的单元；如果该单元•不是“null”，它就简单地从表中取值；否则，就使用递归调用进行计算，然后把返回

的结•果记录在表中。•算法MFKnapsack(I,j)•／／对背包问题实现记忆功能方法•／／输入：一个非负整数f指出先考虑的物品数量，一个非负整数J指出了背包的承重量•／／输出：前i个物品的最伏可行子集的价值•／／注意：我们把输入数组Weights[1…n],Values[1…n]和表格V[0.

.n,0..W]作为全局变量，除了行0和列0用0初始化以外，V的所有单元都用-1做初始化。•ifV[I,j]<01•ifj<Weights[i]•valueMFKnapsack(i-1,j)•else•valuemax(MFKnapsack

(i-1),j),•Value[i]+MFKnapsack(i-1,j-Weights[i]))•V[I,j]value•returnV[I,j]•例2对例1中的实例应用记忆功能法*图8．14给出了结果。只计算了20个有效值•(也就是

不在行o和列o上的)中的10个。只有一个有效单元的值是从表中取到的，而•不是计算得来的。对于较大的实例，这种单元的比例会显著地增加。•一般来说，我们不要奢望对背包问题应用了记忆功能法以后，提高的效率会超过一个常数因子，因为它的时间效率类型和自底向上算法

是相同的（为什么？）。如果在动态规划算法中，计算一个值无法在常数时间内完成，性能的改进可能会更显著。最好记住这一点，相对于自底向上算法的空间优化版本来说，记忆功能法的空间效率是较低的。