多段图
多段图问题是求由s到t的最小成本路径。
图中的结点被划分成 k≥ 2个不相交的集合Vi , 1≤i≤k,其中V1和Vk分别只有一个结点 s (源点) 和t ( 汇点)。
多段图向前处理的算法
1、算法执行过程
COST[j]=c(j,r)+COST[r];
第4段 COST(4,9) = c(9,12) = 4
COST(4,10) = c(10,12) = 2
COST(4,11) = c(11,12) = 5
第3段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)}= 7
COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5
COST(3,8) =min{5+COST(4,10),6+COST(4,11)} = 7
第2段 COST(2,2) = min{4+COST(3,6) , 2+COST(3,7), 1+COST(3,8)} = 7
COST(2,3) = 9
COST(2,4) = 18
COST(2,5) = 15
第1段 COST(1,1) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16
S到t的最小成本路径的成本 ＝ 16
2、最小路径的求取
记 D(i,j)＝每一COST(i,j)的决策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。
例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10
D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8
D(1,1) = 2
根据D(1,1)的决策值向后递推求取最小成本路径：
● v2=D(1,1)=2
● v3 = D(2,D(1,1)) = 7
● v4 = D(3,D(2,D(1,1))) = D(3,7) = 10
故由s到t的最小成本路径是：1→2→7→10→12
3、算法描述
|
多段图的向前处理算法 procedure FGRAPH(E,k,n,P) real COST(n); int D(n-1), P(k), r, j, k, n; COST[n]=0; for j=n-1 downto 1 do { 寻找结点r, 满足<j, r>∈E且使c(j,r)+COST(r)值最小 COST[j]=c(j,r)+COST[r]; D[j]=r ; } P[1]=1; P[k]=n; for j=2 to k-1 do P[j]=D[P[j-1]] ; end FGRAPH |
4、多段图向前处理的算法用邻接表表示
邻接表是图的一种链式存储结构, 对图中的每个顶点建立一个单链表, 链表中的结点有3个域, 分别存储顶点, 边的成本和下一个结点的指针.
多段图向后处理的算法
1、算法的执行过程
第2段 BCOST(2,2) = 9
BCOST(2,3) = 7
BCOST(2,4) = 3
BCOST(2,5) = 2
第3段 BCOST(3,6) = min{BCOST(2,2)+4,BCOST(2,3)+2} = 9
BCOST(3,7) = min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11} = 11
BCOST(3,8) = min{BCOST(2,4)+11, BCOST(2,5)+8} = 10
第4段 BCOST(4,9) =min{BCOST(3,6)+6,BCOST(3,7)+4} = 15
BCOST(4,10) =min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5} = 14
BCOST(4,11) =min{BCOST(3,8)+6} = 16
第5段 BCOST(5,12) =min{BCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5}=16
S到t的最小成本路径的成本＝ 16
2、最小路径的求取
记 BD(i,j)＝每一COST(i,j)的决策即，使COST(i-1,l)+c(l,j)取得最小值的l值。
例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5
BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8
BD(5,12) = 10
根据D(5,12)的决策值向前递推求取最小成本路径：
● v4 = BD(5,12)=10
● v3 = BD(4,BD(5,12)) = 7
● v2 = BD(3,BD(4,BD(5,12))) = BD(3,7) = 2
故由s到t的最小成本路径是：1→2→7→10→12
3、算法描述
BCOST(j)=min{BCOST(l)+ c( l , j)}
|
procedure BGRAPH(E,k,n,P) real BCOST(n); int D(n-1), P(k), r, j, k, n; BCOST[1]=0; for j=2 to n do { 寻找结点r, 满足<r, j>∈E且使BCOST(r)+c(r, j)值最小 BCOST[j]= BCOST[r]+c(r, j); D[j]=r ; } P[1]=1; P[k]=n; for j=k-1 downto 2 do P[j]=D[P[j+1]] ; end BGRAPH |
4、向后处理算法多段图用反邻接表来存储
多段图问题的应用实例
将n个资源分配给r个项目的问题：如果把j个资源，0≤j≤n，分配给项目i，可以获得N(i,j)的净利。求效益最大的分配方案
