《动态规划中的最长路径问题》由会员分享，可在线阅读，更多相关《动态规划中的最长路径问题（7页珍藏版）》请在金锄头文库上搜索。
1、动态规划中的最长路径问题题目：设图G=(V, E)是一个带权有向连通图，如果把顶点集合V 划分成k个互不相交的子集Vi (2WkWn, IWiWk),使得E中的任 何一条边M, v)，必有uVi, vUVi+m (IWiVk, 1Vi+mWk),则称 图G为多段图，称sUV1为源点,tuVk为终点。多段图的最长路径 问题是求从源点到终点的最大代价路径由于多段图将顶点划分为k个互不相交的子集，所以，多段图划 分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶 点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设 图中的顶点个数为n，则源点s的编号为0，终点t的编号为小1，并 且
2、，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。一个多段图用c (u，v)表示边上的权值，将从源点s到终点t的最长路径记为d(s,。，则从源点0到终点9的最长路径d(0, 9)由下式确定:d(0, 9)=maxc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)这是最后一个阶段的决策，它依赖于d(1, 9)、d(2, 9)和d(3, 9)d(1, 9)=maxc14+d(4, 9), c15+d(5, 9) d(2, 9) =maxc24+d(4, 9), c25+d(5, 9) , c26+d(6, 9) d(3, 9) =maxc35+d(5, 9),
3、c26+d(6, 9) 这是倒数第二阶段的式子 它分别依赖于d(4, 9)，d(5, 9)，d(6, 9)d(4, 9)= maxc47+d(7, 9), c48+d(8, 9) d(5, 9)= maxc57+d(7, 9), c58+d(8, 9) d(6, 9)= maxc67+d(7, 9), c68+d(8, 9) 这是倒数第三阶段的式子 它们依赖于d(7,9)，d(8, 9)d(7, 9)= c79=7d(8, 9)= c89=3再往前推d(6, 9)=maxc67+d(7, 9), c68+d(8, 9)=max 6+7, 5+3=13(68)d(5, 9)= max c57+d
4、(7, 9), c58+d(8, 9)=max 8+7, 6+3=15(5f 8)d(4, 9)= max c47+d(7, 9), c48+d(8, 9)=max 5+7, 6+3=12(47)d(3, 9)= max c35+d(5, 9), c36+d(6, 9)=max 4+15, 7+13=20(36)d(2,9)= max c24+d(4,9), c25+d(5,9), c26+d(6,9)=max 6+12, 7+15, 8+13=22(25)d(1,9)= max c14+d(4, 9), c15+d(5, 9)=min9+12, 8+15=23(15)d(0, 9)= max
5、 c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=max 4+23, 2+22, 3+20=27(03)最后，得到最长路径为0f 1579,长度为27。下面考虑多段图的最长路径问题的填表形式。用一个数组costn作为存储子问题解的表格，costi表示从 顶点i到终点n-1的最长路径，数组pathn存储状态,pathi表示从 顶点i到终点n-1的路径上顶点i的下一个顶点。则：costi=maxcij+costj(iWjWn且顶点j是顶点i的邻接点)(式6.7) pathi= cij+costj 最大的 j(式 6.8)程序算法多段图算法：Procedure FGRAP
6、H (E,k,n,P)输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c (i, j)是边i, j的成本。P (1： k)是最大成本路径。/ real COST(n),integer(n-1),P(k),r,j,k,n COST(n)-0for j-n-1 to 1 by -1 do 计算 COST (j) /设r是一个这样的结点，(j, r) E且使c (j, r) +COST (r) 取最大值 COST(j)- c(j，r)+COST(r);D(j)-r;Repeat 向前对 j-1 进行决策/P(1)-1; P(k)-n;for j-2 to k-1 do /找路径上的第j
7、个节点/ P( j) -D(P(j-1);repeat; end FGRAPH四.程序关键代码void fgraph(int cost,int path,int d) 使用向前递推算法求多段 图的最长路径( int r,j,temp,min; for(j=0;j=1;j-) ( temp=0;min=cjtemp+costtemp;/ 初始化大值for(r=0;r=n;r+)(if(cjr!=MIN) (if(cjr+costr)max)/ 找到最大的 r( min=cjr+costr; temp=r;costj=cjtemp+costtemp;dj=temp; path1=1; pathk=
8、n;for(j=2;jk;j+)pathj=dpathj-1;void bgraph(int bcost,int path1,int d)/使用向后递推算法求多 段图的最短路径 int r,j,temp,min; for(j=0;j=n;j+) bcostj=0; for(j=2;j=n;j+) temp=12;min=ctempj+bcosttemp;/ 初始化最大值for(r=0;r=n;r+)if(crj!=MIN) if(crj+bcostr)=2;i-) path1i=dpath1i+1;void main()(int cur=-1; int cost13,d12,bcost13;
9、int pathk; int path1k;coutttt 动态规划解多段图问题endl; coutnn; init(cost);fgraph(cost,path,d);cout输出使用向前递推算法后的最长路径:nn; for(int i=1;i=5;i+) ( coutpathi ;coutn;coutendl最长路径为长度:cost1endl;coutn;coutn输出使用向后递推算法后的最长路径:nn;bgraph(bcost,path1,d); for(i=1;i=5;i+)( coutpath1i; ;coutn; coutendl最长路径为长 度:bcost12endl;coutn;实验小结动态规划最长路径问题和动态规划的最短路径很相似，我们用递 归的的方法，递推最优化的最长路径长度，让时间复杂度更为简单， 我们再设计算法时，也要注意怎样实现这个过程，如何找到它的前驱 结点和后继结点，我们通过连接矩阵或你连接表的方式查找。
