算法设计与分析基础第2版清华出版社算法分析第8章

《算法设计与分析基础第2版清华出版社算法分析第8章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划(dynamicprogramming)是一种算法设计技术，它有着相当有趣的历史。作为一种使多阶段决策过程最优的通用方法，它是在20世纪50年代由一位卓越的美国数学家RichardBellman所发明的。因此，这个技术名字中的“Programming”是计划和规划的意思，不是代表计算机中的编程。它作为一种重要的工具在应用数学中的价值被大家认同以后，起码在计算机科学的圈子里，人们不仅用它来解决特定类型的最忧问题，而且最终把它作为一种通用的算法设计技术来使用。在这里，我们正是从这个角度来考虑这种技术的。如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术来解决它。一般来说，这样的于

2、问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议，与其对交叠的子问题一次又一次地求解，还不如对每个较小的子问题只求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解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>

3、=k>=0//输出：C(n,k)的值fori←0tondoforj←0tomin(i,k)doifj=0orj=kC[i,j]←1elseC[i,j]←C[i-1,j-1]+C[i-1,j]returnC[n,k]该算法的时间效率如何呢?显然，该算法的基本操作是加法8.2Warshall算法和FLoyd算法8．2．2Warshall算法一个有向图的邻接矩阵A={aij}是一个布尔矩阵，当且仅当从第i个顶点到第j个顶点之间有一条有向边时，矩阵第i行第j列的元素为1。定义一个n顶点有向图的传递闭包可以定义为一个n阶布尔矩阵T={tij}，如果从第i个到顶点到第j个顶点之间存在一条有效的有向路径，

4、矩阵第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]）//实现计算

5、传递闭包的Warshall算法//输入：包括n个顶点有向图的邻接矩阵A//输出：该有向图的传递闭包8.2.2计算完全最短路径的Floyd算法绐定一个加权连通图（无向的或有向的），完全最短路径问题要求找到从每个顶点到其他所有顶点之间的距离(最短路径的长度)Floyd算法通过一系列n阶矩阵来计算一个n顶点加权图的距离矩阵：每一个这种矩阵都包含了所讨论的矩阵在特定路径约束下的最短路径的长度每条这种路径都由两条路径构成：一条从vi到vk的路径，路径中每个中间顶点的编号都大于K一1；一条从vi到vj的路径，路径中每个中间顶点的编号也都不大于k-1.算法Floyd(W[1..n,1..n])//实现计算

6、完全最短路径的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,…

7、…an构成的二叉树，C[i,j]是在这棵树中成功查找的最小的平均查找次数。要求出该问题的所有较小实例的C[i,j]值。为了推导出动态规划算法中隐含的递推关系，需要考虑从键ai,……aj中选择一个根ak的所有可能的方法。对于这样一棵二叉树来说，它的根包含了键ak，它的左子树中的键是最优排列的，它的右子树中的键也是最优排列的。当1≤i≤n+1时，C[i,i-1]＝0，这可以解释为空树的比较次数。请注意，这个公式意