关键路径.ppt

Z语言问题。Z语言的基本字母也是26个,不妨用a到z表示,但是其字母的先后顺序与英语中的不同。现在按Z语言的字典顺序给出N个单词,请你按照这些单词给出一个可能的Z语言字母顺序。
输入文件:
第一行是一个整数N(N<100),表示所给出的单词个数。
第二行至第N+1行,每行是一个单词。
输出文件:
仅一行,为一个可能的字母排列顺序。
课堂练****br/>g[a[i,j],a[i+1,j]]:=1;
应该为j<=length(a[i+1])
关键路径
图论算法
AOE网
AOE网(Activity On work),即边表示活动的网络,与AOV网相对应,它通常表示一个工程的计划或进度。
AOE网是一个带权的有向无环图,图中的: 边:表示活动(子工程), 边上的权:表示该活动的持续时间,即完成该活动所需要的时间;
顶点:表示事件,每个事件是活动之间的转接点,即表示它的所有入边活动到此完成,所有出边活动从此开始。其中有两个特殊的顶点(事件),一个称做源点,它表示整个工程的开始,亦即最早活动的起点,显然它只有出边,没有入边;另一个称做汇点,它表示整个工程的结束,亦即最后活动的终点,显然它只有人边,没有出边。除这两个顶点外,其余顶点都既有人边,也有出边,是入边活动和出边活动的转接点。
关键路径的概念
AOE网中有些活动可以并行进行,所以完成整个工程的最短时间是从源点到汇点的最长路径长度,路径长度为路径上各边的权值之和。把从源点到汇点的最长路径长度称为关键路径。
对于一个AOE网,待研究的问题是: (1)整个工程至少需要多长时间完成? (2)哪些活动是影响工程进度的关键?
关键路径
假设开始点是v1,从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i),这是在不推迟整个工程的前提下,活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i) 的活动叫做关键活动。
关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。
怎样找关键活动
求事件的最早发生时间ve(j)和最迟发生时间。如果活动ai由弧<j,k>表示,其持续时间记为dut<j,k>,则有如下关系:
e(i)=ve(j); l(i)=vl(k)-dut(<j,k>);
求ve(j):
从ve(1)=0开始向后递推
ve(j)=max{ve(i)+dut(<i,j>)} 2≤j≤n
求vl(j):
从vl(n)=ve(n)起向前递推
vl(i)=min{vl(j)-dut(<i,j>)} 1≤i≤n-1
以上两个递推公式的计算必须分别在拓补有序和逆拓补有序的前提下进行。
求ve(j):
E[1]=0;
E[2]=max{e[1]+dust[1,2]}=6
E[3]=max{e[1]+dust[1,3]}=4
E[4]=max{e[1]+dust[1,4]}=5
E[5]=max{e[2]+dust[2,5] ,e[3]+dust[3,5]}={6+1,4+1}=7
E[6]=max{e[4]+dust[4,6]}={5+2}=7
E[7]=max{e[5]+dust[5,7]}={7+9}=16
E[8]=max{e[5]+dust[5,8],e[6]+dust[6,8]}={7+7,7+4}=14
E[9]= max{e[7]+dust[7,9],e[8]+dust[8,9]}={16+2,14+4}=18
E[1]=0;
E[K]=max{e[j]+dust[j,k]}
其中,j是k的直接前驱事件,dust[j,k]表示边<j,k>上的权。
求vL(j):
L[9]= E[9]=18
L[8]=min{L[9]-dust[8,9]}={18-4}=14
L[7]=min{L[9]-dust[7,9]}={18-2}=16
L[6]=min{L[8]-dust[6,8]}={14-4}=10
L[5]=min{L[8]-dust[5,8] ,L[7]-dust[5,7]}={14-7,16-9}=7
L[4]=min{L[6]-dust[4,6]}={10-2}=8
L[3]=min{L[5]-dust[3,5]}={7-1}=6
L[2]=min{L[5]-dust[2,5]}={7-1}=6
L[1]=min{L[2]-dust[1,2],L[3]-dust[1,3],L[4]-dust[1,4]}=min{6-6,6-4,8-5}=0;
L[9]=E[9];
L[J]=min{E[K]-dust[j,k]}
其中