华东理工815数据结构Chap5_图剖析.ppt

* * * * V4的最迟发生时间是在V8在18天完成的前提下，从汇点到v4的最长路径长度11。 * 找最早开始时间最晚的。 * Vl[i]越小，表示最迟发生时间越早的。找最迟发生时间最早的。 * * el(i) = vl(k) – dut(j,k); * 任务进度时间参数说明 最早开始时间ES(Early start) 最晚开始时间LS(Late start) 最早完成时间EF(Early finish) 最晚完成时间LF(Late finish) 关键活动：该活动的最早开始时间=该活动的最迟开始时间,即活动的时间余量为0的时间 “事件（顶点）” 的 最早可能发生时间 ve(j) = 从源点到顶点vj的最长路径长度; v0 v1 v2 v3 v4 v5 v6 v7 v8 a1=6 a2=4 a3=5 a6=2 a4=1 a5=1 a7=8 a8=7 a10=2 a11=4 a9=4 “事件（顶点）” 的 最迟允许发生时间vl(j) =ve(汇点) - v(j)到汇点的最长路径; “活动(弧)”的 最早可能开始时间 e(i)=弧头顶点的最早发生时间; “活动(弧)”的 最迟开始时间 l(i)=vl(弧头) –活动的执行时间dut 活动ai的时间余量=l(i)-e(i) chapter__3 * 正推法实例 Start LF LS EF ES Duration=7 Task A 1 8 LF LS EF ES Duration=3 Task B 1 4 LF LS EF ES Duration=6 Task C 8 14 LF LS EF ES Duration=3 Task D 4 7 LF LS EF ES Duration=3 Task G 14 17 LF LS EF ES Duration=3 Task E 7 10 LF LS EF ES Duration=2 Task H 17 19 LF LS EF ES Duration=2 Task F 4 6 Finish 当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期 逆推法(Backward pass) 按照逆时间顺序计算最晚开始时间和最晚结束时间的方法,称为逆推法. 首先建立项目的结束时间 项目的结束时间是网络图中最后一个活动的最晚结束时间 从右到左，从上到下进行计算 当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期 chapter__3 * 逆推图示 Start LF LS EF ES Duration=7 Task A 1 8 1 8 LF LS EF ES Duration=3 Task B 1 4 8 11 LF LS EF ES Duration=6 Task C 8 14 8 14 LF LS EF ES Duration=3 Task D 4 7 11 14 LF LS EF ES Duration=3 Task G 14 17 14 17 LF LS EF ES Duration=3 Task E 7 10 14 17 LF LS EF ES Duration=2 Task H 17 19 17 19 LF LS EF ES Duration=2 Task F 4 6 12 14 Finish 当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期 CP:A-C-G-H Cp Path:18 为求得e[k]与l[k]，需要先求得从开始点V0 到各个顶点Vi 的Ve[i] 和Vl[i]。 求Ve[i]的递推公式 从Ve[1] = 0开始，向前递推 Vj, Vi ? S2, i = 2, 3, ?, n S2 是所有指向Vi 的有向边 Vj , Vi 的集合。 Ve = 6 Ve = 12 Ve = 9 5 2 4 Ve = 11? 14? 13? 已知 求解 ? 从Vl[n] = Ve[n]开始，反向递推 Vi, Vj ? S1, i = n-1, n-2, ?, 1 S1是所有源自Vi的有向边 Vi , Vj 的集合。 这两个递推公式的计算分别在拓扑有序及逆拓扑有序的前提下进行。 6 7 5 Vl = 19 Vl = 24 Vl = 11 Vl = 13? 17? 6? ? 已知 求解 找最迟发生时间最早的 0 0 0 0 0 0 0 0 0 6 4 5 7 14 7 15 18 18 18 18 18 18 18 18 18 18 16 14 7 6 6 10 8 0 计算事件