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

【题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，vjvi的可能的最早发生时间ee[i]； l[k]ak(对应边vi，vj)vj允许最晚发生时间le[j]； (1i， jn， 1k≤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(1k≤m)，e[k]和l[k] e[k]←ee[i]， l[k]le[j] 若l[k]-e[k]=wij，ak为关键活动。计算关键路径时间复杂度为W(n2)。 ⑶计算能影响整个计划完成时间的关键活动 在找出关键活动后，只要将所有的非关键活动从AOV网中去掉，这时从开始结点至完成结点的所有路径都是关键路径。AOV网中的关键路径可能不止