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

动态规划中的最长路径问题题目: 设图 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 的编号。 2 1203 456 78 9 4 93 87 6847 5686 65 3 7 一个多段图用 c( u, v) 表示边上的权值, 将从源点 s 到终点 t 的最长路径记为 d(s,t) ,则从源点 0 到终点 9 的最长路径 d (0, 9) 由下式确定: d (0, 9)=m ax{c 01+ d (1, 9), c 02+ d (2, 9), c 03+ d (3, 9)} 这是最后一个阶段的决策,它依赖于 d (1, 9)、 d (2, 9)和 d (3, 9) d (1, 9) =max {c 14+d(4, 9), c 15+d(5, 9)} d (2, 9) =max {c 24+d(4, 9), c 25+d(5, 9),c 26+d(6, 9)} d(3, 9) =max {c 35+d(5, 9), c 26+d(6, 9)} 这是倒数第二阶段的式子它分别依赖于 d(4, 9), d(5, 9), d(6, 9) d(4, 9)= max {c 47+d(7, 9), c 48+d(8, 9)} d(5, 9)= max {c 57+d(7, 9), c 58+d(8, 9)} d(6, 9)= max {c 67+d(7, 9), c 68+d(8, 9)} 这是倒数第三阶段的式子它们依赖于 d(7, 9), d(8, 9) d(7, 9)=c 79=7 d(8, 9)=c 89=3 再往前推 d (6, 9)=m ax{c 67+ d (7, 9), c 68+ d (8, 9)} =m ax {6+7, 5+3}= 13 (6→ 8) d (5, 9)= m ax{c 57+ d (7, 9), c 58+ d (8, 9)} =m ax {8+7, 6+3}= 15 (5→ 8) d (4, 9)= m ax{c 47+ d (7, 9), c 48+ d (8, 9)} =m ax {5+7, 6+3}= 12 (4→ 7) d (3, 9)= m ax{c 35+ d (5, 9), c 36+ d (6, 9)} =m ax {4+ 15, 7+ 13 }= 20 (3→ 6) d (2,9)= m ax{c 24+ d (4,9), c 25+ d (5,9), c 26+ d (6, 9)} =m ax {6+ 12, 7+ 15, 8+ 13 }= 22 (2→ 5)