【题23】计算能影响整个计划完成时间的关键活动--试题解析

【题23】计算能影响整个计划完成时间的关键活动工厂的工程计划用一张有向图表示，有向图的结点表示事件，有向边表示活动，边上的权标明一项活动需要的时间。结点所表示的事件实际上就是它入边代表的活动均已完成，出边代表的活动可以开始这样一种状态。例如上图含11项活动、9个事件。其中事件v1表示开始时活动a1、a2、a3并行实施；事件v5代表活动a4、a5已经完成，活动a7、a8可以开始。V9表示整个计划完成。活动依事件的顺序要求进行。例如活动a4、a5、a6只有当事件v2、v3、v4分别发生后才能进行，而它们的完成又标志事件v5、v6的发生。当活动a10、a11完成后，整个计划完成。上述有向图存在唯一的入度为0的开始结点v1，表明整个计划从该事件开始；存在唯一的出度为0的完成结点vn，表明该事件完成后，整个计划结束。现在的问题是，整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度。输入：n(事件数，1≤n≤100)e(活动数，1≤e≤4000)以下为e行，每行为连接两个事件的序号以及活动需要的时间输出：完成整个计划的最少时间以下k行，每行为一个关键活动（i，j）和目前花费的时间wij，加快该活动的速度能提前完成计划⑴关键路径的由来如果有向图的结点表示活动，有向边表示活动间的优先关系，那么我们通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列。如果有向有权图满足下述条件⑴存在唯一的入度为0的结点和唯一的出度为0的结点；⑵可通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列（即有向图没有回路）则称该有向有权图为AOV网（活动结点网络）。由于前面已经给出了拓扑排序的算法，因此这里不再赘述。如果本题给出的有向有权图是一个AOV网，则利用AOV网可以估算出整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度等问题。解决这些问题有一种有效的方法——求关键路径方法。由于AOV网中的活动可以并行进行，因此完成整个计划的最少时间是从开始结点v1到完成结点vn的最长路径长度（路径上各边权的和）。具有最大长度的路径称作关键路径。在上图中v1→v2→v5→v8→v9是一条关键路径，长度为18。换句话说，整个计划至少需要18个时间单位完成。关键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误整个计划。找出关键活动后就可以适当调度，集中力量于关键活动，以保证计划如期或提前完成。⑵关键路径的计算为了找出关键活动，我们先定义几个变量：n—AOV网的结点数；m—AOV网的有向边数；ee[i]—vi事件可能发生的最早时间，即从开始结点v1至结点vi的最长路径长度；le[i]—在保证完成结点vn所代表的事件在ee[n]时刻发生的前提下，事件vi允许发生的最晚时间，即le[i]=ee(n)-vi至vn最长路径长度；e[k]—活动ak（对应边vi，vj）可能的最早开始时间，即等于事件vi的可能的最早发生时间ee[i]；l[k]—活动ak(对应边vi，vj)允许的最晚完成时间，即等于事件vj允许最晚发生时间le[j]；(1≤i，j≤n，1≤k≤m)]显然活动ak的最大可利用时间是l[k]-e[k]。若最大可利用时间等于ak边所带的权wk(即为计划时间)，则ak是关键活动。ak延期，则整个计划将顺延。若最大可利用时间大于wk，则ak不是关键活动，ak的完成时间允许超过wk。只要不超过最大可利用时间，无妨于整个计划完成的进度。我们可以采取以下步骤，计算上面定义的几个变量值，从而找到关键活动：⑴首先令ee[1]=0，然后向前递推ee[j]ee[j]=max{ee[i]+wij}2≤j≤n，(i，j)∈以j为头的弧集显然，ee[j]的计算必须在vj的所有前趋结点的最早发生时间都已求得前提下进行；⑵从le[n]=ee[n]起向后倒推le[i]le[i]=min{le[j]-wij}i=n-1‥1，(i，j)∈以i为尾的弧集显然，le[i]的计算必须在vi的所有后继结点的最晚发生时间都已求得的前提下进行。由⑴、⑵可以看出结点序列v1‥vn必须是拓扑序列。⑶对于每一条边ak=vi，vj(1≤k≤m)，求e[k]和l[k]e[k]←ee[i]，l[k]←le[j]若l[k]-e[k]=wij，则ak为关键活动。计算关键路径时间复杂度为W(n2)。⑶计算能影响整个计划完成时间的关键活动在找出关键活动后，只要将所有的非关键活动从AOV网中去掉，这时从开始结点至完成结点的所有路径都是关键路径。AOV网中的关键路径可能不止一条。并不是加快任一关键活动就可以缩短整个计划的完成时间。只有加快那些包括在所有关键路径上的关键活动才能达到目的的。例如试题给出的AOV网中，关键路径为v1→v2→v5→v８→v9和v1→v2→v5→v7→v9。如果仅加快事件v8和v9之间的关键活动a11的速度，是不能缩短计划完成时间的，因为第一条路径不包括活动a11。如果加快v1和v2之间的关键活动a1，则由于两条关键路径都包含关键活动a1而导致整个计划提前完成。设a为关键路径组成的01矩阵，a0为辅助矩阵；b为关键活动序列，其中b[k].x、b[k].y和b[k].l分别为第k项关键活动的两个顶点序号和花费；nopath为v1至vn间有路可走的标志；首先计算关键活动序列b和关键活动组成的有向图a。然后逐一地在a图中去除一条关键活动边，看一看是否存在v1至vn的路径。如果v1至vn间无路可走,则说明这个关键活动为影响整个计划完成的关键活动。判别过程采用深度优先搜索proceduredfs(i:integer)；{深度优先搜索a0图中由顶点i出发的所有可能路径。若存在一条到达顶点n的路径，则nopath设为false；否则为true}beginf[i]←true；ifi=nthenbeginnopath←false；exit；end{then}forj←1tondobeginif(not(f[j]))and(a0[i,j]=1)thendfs(j)；end；{for}end；{dfs}判别运算的时间复杂度为W(n2)。由此得出算法活动的时间矩阵w初始化为0；输入带权有向图的信息（顶点数n、活动数e和活动的时间矩阵w）；if图中的所有顶点不能排成一个拓扑序列then失败退出；fillchar(ee，sizeof(ee)，0)；fori←1ton-1doforj←1tondo{计算各个事件的最早发生时间表ee}if((i,j)∈E)and(ee[j]ee[i]+wij)thenee[j]←ee[i]+wij；输出完成整个计划的最少时间ee[n]；fori←1tondole[i]←ee[n]；{所有事件的最晚发生时间初始化}k←0；{关键活动数初始化}fori←n-1downto1do{计算各个事件的最晚发生时间表le}forj←1tondoif(wij0)and(le[i]le[j]-wij)thenle[i]←ee[j]-wij；fillchar(a,sizeof(a),0)；{由关键活动组成的有向图a初始化}fori←1ton-1do{计算关键活动和由关键活动组成的有向图a}forj←1tondoif(wij0)and(le[j]-ee[i]=wij)thenbegink←k+1；b[k].x←i；b[k].y←j；b[k].l←wij；a[i,j]←1；end；{then}fort←1tokdo{枚举每一个关键活动}begina0←a；a0[b[t].x，b[t].y]←0；{在有向图a中去除第t个关键活动}fillchar(f，sizeof(f)，false)；nopath←true；{访问标志和成功标志初始化}dfs(1)；{通过深度优先搜索判断v1与n间是否有路}ifnopaththen输出关键活动（b[t].x，b[t].y）和目前花费b[t].l；end；{for}由上可见，影响整个计划完成的关键活动为所有关键路径共用的边，这些公共边称之为“桥”。寻找“桥”的方法很多，我们给出的方法仅是其中的一种，虽然思路比较简单，但时间效率并不高（O(k*n2)）。关于更高效的算法，请读者参阅有关图论的书籍。