动态规划法 -算法设计与分析PPT.ppt

7.2.1? ?问题描述 设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数， 每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。 7.2 每对结点间的最短路径 分析： 利用单源最短路径算法求解 ● 计算n个结点的单源最短路径。 ● 时间复杂度：Ο(n3) 利用动态规划策略求解 将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。 ● 决策什么？ ● 最优性原理对于该问题是否成立？ 7.2.2 动态规划法求解 最优子结构 设图G=(V,E)是带权有向图，?(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，?(i,k) 和?(k,j)分别是从i到k和从k到j的最短路径长度，则必有?(i,j)= ?(i,k)+?(k,j)。因为若不然，则?(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。 最优解的递推关系 重叠子问题：为了计算dk[i][j]时，必须先计算 dk－1[i][j]、dk－1[i][k]和dk－1[i][k]，dk?1的元素被多个dk的元素的计算共享。 7.2.3?弗洛伊德算法 弗洛伊德算法的基本思想是：令k=0,1,?,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，d[i][j]存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。 【程序7－2】弗洛伊德算法 templateclass T void MGraphT::Floyd(T** d, int ** path) { int i,j,k; d= new T*[n];path=new int *[n]; for(i=0;in;i++){ d[i]=new T [n];path[i]=new int[n]; for (j=0;jn;j++){ d[i][j]=a[i][j]; if (i!=j w[i][j]INFTY) path[i][j]=i; else path[i][j]=-1; } } for (k=0;kn;k++) for (i=0;in;i++) for (j=0;jn;j++) if (d[i][k]+d[k][j] d[i][j] ){ d[i][j]=d[i][k]+d[k][j]; path[i][j]=path[k][j]; } }弗洛伊德算法的时间复杂度为O(n3) 7.2.4 算法正确性 定理7－1 弗洛伊德算法得到的d[i][j]，0?i,j?n-1是从i到j的最短路径。 7.3.1? 问题描述 给定n个矩阵{A0,A1,…,An－1}， 其中Ai，i=0,…,n-1的维数为pi?pi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1…An?1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。 7.3 矩阵连乘 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 例7－4 4个矩阵连乘积ABCD，设它们的维数分别为A:50?10，B:10?40, C:40?30, D:30?5。 7.3.2 动态规划法求解 最优子结构 矩阵连乘AiAi+1…Aj简记为A[i:j]，i?j。于是矩阵连乘A0A1…An-1可记作A{0:n-1}。将这一计算次序在矩阵Ak和Ak+1，0?kn-1之间断开，则其相应的完全加括号形式为（（A0A1…Ak）（Ak+1Ak+2…An?1））。可先分别计算A[0:k]和A[k+1:n-1]，然后将两个连乘积再相乘得到A[0:n-1]。 矩阵连乘A[0:n-1]的最优计算次序的计算量等于A[0:k]和A[k+1:n-1]两者的最优计算次序的计算量之和，再加上A[0:k]和A[k+1:n-1]相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说