动态规划中的最长路径问题

动态规划中的最长路径问题

ID:11802303

大小:51.37 KB

页数:7页

时间:2018-07-14

动态规划中的最长路径问题_第1页
动态规划中的最长路径问题_第2页
动态规划中的最长路径问题_第3页
动态规划中的最长路径问题_第4页
动态规划中的最长路径问题_第5页
资源描述:

《动态规划中的最长路径问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、动态规划中的最长路径问题题目:设图G=(V,E)是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi(2≤k≤n,1≤i≤k),使得E中的任何一条边(u,v),必有u∈Vi,v∈Vi+m(1≤i<k,1<i+m≤k),则称图G为多段图,称s∈V1为源点,t∈Vk为终点。多段图的最长路径问题是求从源点到终点的最大代价路径由于多段图将顶点划分为k个互不相交的子集,所以,多段图划分为k段,每一段包含顶点的一个子集。不失一般性,将多段图的顶点按照段的顺序进行编号,同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n,则源点s

2、的编号为0,终点t的编号为n-1,并且,对图中的任何一条边(u,v),顶点u的编号小于顶点v的编号。2120345678949387684756866537一个多段图用c(u,v)表示边上的权值,将从源点s到终点t的最长路径记为d(s,t),则从源点0到终点9的最长路径d(0,9)由下式确定:d(0,9)=max{c01+d(1,9),c02+d(2,9),c03+d(3,9)}这是最后一个阶段的决策,它依赖于d(1,9)、d(2,9)和d(3,9)d(1,9)=max{c14+d(4,9),c15+d(5,9)}d(2,9)=ma

3、x{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=max{c35+d(5,9),c26+d(6,9)}这是倒数第二阶段的式子它分别依赖于d(4,9),d(5,9),d(6,9)d(4,9)=max{c47+d(7,9),c48+d(8,9)}d(5,9)=max{c57+d(7,9),c58+d(8,9)}d(6,9)=max{c67+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)=m

4、ax{c67+d(7,9),c68+d(8,9)}=max{6+7,5+3}=13(6→8)d(5,9)=max{c57+d(7,9),c58+d(8,9)}=max{8+7,6+3}=15(5→8)d(4,9)=max{c47+d(7,9),c48+d(8,9)}=max{5+7,6+3}=12(4→7)d(3,9)=max{c35+d(5,9),c36+d(6,9)}=max{4+15,7+13}=20(3→6)d(2,9)=max{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=max{6+12,7+15,

5、8+13}=22(2→5)d(1,9)=max{c14+d(4,9),c15+d(5,9)}=min{9+12,8+15}=23(1→5)d(0,9)=max{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=max{4+23,2+22,3+20}=27(0→3)最后,得到最长路径为0→1→5→7→9,长度为27。下面考虑多段图的最长路径问题的填表形式。用一个数组cost[n]作为存储子问题解的表格,cost[i]表示从顶点i到终点n-1的最长路径,数组path[n]存储状态,path[i]表示从顶点i到终点n-1

6、的路径上顶点i的下一个顶点。则:cost[i]=max{cij+cost[j]}(i≤j≤n且顶点j是顶点i的邻接点)(式6.7)path[i]=使cij+cost[j]最大的j(式6.8)程序算法多段图算法:ProcedureFGRAPH(E,k,n,P)//输入是按段的顺序给结点编号的,有n个结点的k段图。E是边集,c(i,j)是边的成本。P(1:k)是最大成本路径。//realCOST(n),integer(n-1),P(k),r,j,k,nCOST(n)<-0forj<-n-1to1by-1do//计算COST(j

7、)//设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;forj<-2tok-1do//找路径上的第j个节点//P(j)<-D(P(j-1));repeat;endFGRAPH四.程序关键代码voidfgraph(intcost[],intpath[],intd[])//使用向前递推算法求多段图的最长路径{intr,j,temp,min;for(j=0;j<=n;j++)c

8、ost[j]=0;for(j=n-1;j>=1;j--){temp=0;min=c[j][temp]+cost[temp];//初始化大值for(r=0;r<=n;r++){if(c[j][r]!=MIN){if((c[j][r]+c

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。