《《算法设计与分析》第07章v2幻灯片》由会员分享，可在线阅读，更多相关《《算法设计与分析》第07章v2幻灯片（96页珍藏版）》请在金锄头文库上搜索。
1、,算法设计与分析,DeSign and Analysis of Algorithms In C+,“十一五”国家级规划教材,陈慧南 编著,电子工业出版社,第2部分 算法设计策略,第7章 动态规划法,7.1 一般方法和基本要素 7.2 每对结点间的最短路径 7.3 矩阵连乘 7.4 最长公共子序列 7.5 最优二叉搜索树 7.6 0/1背包 7.7 流水作业调度,7.1 一般方法和基本要素,7.1.3 多段图问题,例71 多段图G=(V,E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包
2、含汇点（sink）t。对所有边E，多段图要求若uVi，则vVi1，1ik，每条边的权值为c(u,v)。从s到t的路径长度是这条路径上边的权值之和，多段图问题（multistage graph problem）是求从s到t的一条长度最短的路径。,子集Vi,多段图问题的特性,最优子结构特性 （s,v2,v3,vk-1,t) 与 (v2,v3,vk-1,t)定义cost(i,j)， 1i=0;j-) float min=INFTY; for (ENode *r=aj;r;r=r-nextArc) int v=r-adjVex;if (r-w+costvw+costv;q=v;costj=min;dj
3、=q; p0=0; pk-1=n-1; /p记录最短路径 for(j=1;j=k-2;j+) pj=dpj-1; delete cost; delete d; ,2 k段图的自前向后递推求解,递推关系式 cost(1,s)=0 cost(i,j)=?,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以
4、处理不具备贪心准则的问题。,7.1.1 一般方法,最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策对相应的子问题来说，必定构成最优策略。这便是最优决策序列的最优子结构特性。,设计一个动态规划算法，通常可以按以下几个步骤进行： （1）刻画最优解的子结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。,7.1.2 基本要素,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠
5、子问题。,7.1.4 资源分配问题,【例72】将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。（这里假设，对同一个项目，获得的资源越多，收益越多；不同的项目对资源的单位收益不一样）,V(i,j)表示j个资源已经分配给前i-1个项目 N(m,n)表示n个资源分配给第m个项目了,4个资源、3个项目,7.1.4 资源分配问题,向后递推的动态规划算法？,7.1.5 关键路径问题（略）,工程安排 最短工期 关键路径 关键活动 在关键路径上的活动注意结点的编号,结点=事件（代表前一个活动结束， 后一个活动可开始的状态）,7.1
6、.5 关键路径问题,最优子结构特性？子问题重叠？,7.2 每对结点间的最短路径,单源最短路径问题,单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。,贪心法求解,迪杰斯特拉（Dijkstra） 算法 解视为向量（L1,L2,L3,Ln-1) ，分量Li表示s到结点i的最短路径首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。每步度量准则：当前最短路径（增量最少的分量） 以求得最短路径的结点集合记为S, 从其他结点找出当前最短的,6.6.3 迪杰斯特拉算法,【
7、程序610】迪杰斯特拉算法 template class MGraph public:MGraph(int mSize);void Dijkstra(int s,T*,private:int Choose(int* d, bool* s); T*a; /邻接矩阵 int n; ;,template int MGraph:Choose(int* d, bool* s) /找出在下一条当前最短路径上的尾结点int i,minpos; T min;min=INFTY; minpos=-1;for (i=1;in;i+) if (dimin ,template void MGraph:Dijkstra
8、(int s,T*,inSs=true; ds=0; for (i=1;in-1;i+) /需要n-1步完成 k=Choose(d,inS); inSk=true; for (j=0; jn; j+) /更新各结点的d和path if (!inSj ,时间复杂度？,7.2.1 结点对间最短路径问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数，每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,7.2.2 动态规划法求解,最优子结构 设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，(i,k) 和(
9、k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)= (i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。,定义dkij=i到j的路径上，包含的结点编号 不超过k是的最短路径长度,最优解的递推关系,重叠子问题：为了计算dkij时，必须先计算 dk1ij、dk1ik和dk1ik，dk1的元素被多个dk的元素的计算共享。,dkij指在i和j之间由编号不大于k的结点组成的最短路径长度。k=-1时表示不包含其他结点,7.2.3 弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一个结点k
10、。二维数组d用于保存各条最短路径的长度，其中，dij存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。,【程序72】弗洛伊德算法 template void MGraph:Floyd(T*,for (k=0;kn;k+) 总共n步完成for (i=0;in;i+)for (j=0;jn;j+) if (dik+dkj dij )dij=dik+dkj;pathij=pathkj; 弗洛伊德算法的时间复杂度也为O(n3),7.2.4 算法正确性,定理71 弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,结点对间最短路径问题,弗洛
11、伊德算法N次迪杰斯特拉算法,7.3 矩阵连乘,7.3.1 问题描述,给定n个矩阵A0,A1,An1， 其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,(A0A1) A3)A4),(A0(A1 A3)A4),完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(
12、BC)。,A=(M0M1M3Mk),(Mk+1Mk+2Mn-1),A=M0M1M3M4Mn-1,B,C,例74 4个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040, C:4030, D:305。,7.3.2 动态规划法求解,最优子结构 矩阵连乘AiAi+1Aj简记为Ai:j，ij。于是矩阵连乘A0A1An-1可记作A0:n-1。将这一计算次序在矩阵Ak和Ak+1，0kn-1之间断开，则其相应的完全加括号形式为（A0A1Ak）（Ak+1Ak+2An1）。可先分别计算A0:k和Ak+1:n-1，然后将两个连乘积再相乘得到A0:n-1。,矩阵连乘A0:n-1的最优计算次序的计算量等于A0:k和Ak+1:n-1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,最优解的递推关系 先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。,注意：N个矩阵的维数依序放在一维数组p中， 其中Ai的维数记为PiPi+1,
