动态规划中地最长路径问题.docVIP

动态规划中的最长路径问题题目：设图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的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。22120345678949387684756866537 一个多段图用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) =max{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)=max{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, 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的路径上顶点i的下一个顶点。则： cost[i]=max{cij+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点) （式6.7）path[i]=使cij+cost[j]最大的j （式6.8） 程序算法 多段图算法： Procedure FGRAPH（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)-0 for 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）