魔都网站建设,网站群站优化,南宁百度推广代理商,网站建设心得8000字1.AOV网#xff08;Activity On Vertex NetWork#xff09;
用DAG图表示一个工程。顶点表示活动#xff0c; V i , V j V_i,V_j Vi,Vj表示 V i V_i Vi必须先于活动 V j V_j Vj进行
2.拓扑排序
#xff08;1#xff09;拓扑排序定义 …1.AOV网Activity On Vertex NetWork
用DAG图表示一个工程。顶点表示活动 V i , V j V_i,V_j Vi,Vj表示 V i V_i Vi必须先于活动 V j V_j Vj进行
2.拓扑排序
1拓扑排序定义 在图论中由一个DAG图的顶点组成的序列当且仅当满足下列条件时称为该图的一拓扑排序 1每个顶点出现且出现一次 2若顶点A在序列中排在顶点B的前面则在图中不存在从顶点B到顶点A 的路径
2AOV/AOE网的拓扑排序步骤 1从AOV/AOE网中选择一个没有前驱入度为0的顶点并输出 2从网中删除该顶点和所有以它为起点的有向边 3重复1和2两个步骤直到AOV/AOE网为空
3AOV/AOE网的逆拓扑排序 1从AOV/AOE网中选择一个没有后继出度为0的顶点并输出 2从网中删除该顶点和所有以它为终点的有向边 3重复1和2两个步骤直到AOV/AOE网为空
3.AOE网Activity On Edge NetWork
1AOE网的定义 在带权DAG图中以顶点表示事件以有向边表示活动以边上的权值表示完成该活动的开销称之为用边表示活动的网络简称AOE网Activity On Edge NetWork
2AOE网的性质 1只有在某顶点所代表的事件发生后从该顶点出发的各有向边所代表的活动才能开始 2只有在进入某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发生另外有些活动是可以合并的
3源点和汇点 1源点在AOE网中仅有一个入度为0的顶点称为开始顶点源点表示整个工程的开始 2汇点也仅有一个出度为0的顶点称为结束顶点汇点表示整个工程的结束
4.关键路径
1关键路径和关键活动的定义 从源点到汇点的有向路径可能有多条所有路径中具有最大路径长度的路径称为关键路径把关键路径上的活动称为关键活动
2关键路径和关键活动的含义 关键路径的长度就是完成整个工程的最短时间 1若关键活动耗时增加则整个工程的完成时间就会延长 2缩短关键活动的时间可以缩短整个工程的工期。但是缩短到一定程度关键活动可能会变成非关键活动 3AOE网可能有多条关键路径只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
5.关键路径的计算
1相关概念
概念描述事件 V k V_k Vk的最早发生时间 V E ( k ) VE(k) VE(k)决定了所有 V k V_k Vk开始的活动能够开工的最早时间事件 V k V_k Vk的最晚发生时间 V L ( k ) VL(k) VL(k)指在不推迟整个工程完成的前提下该事件最迟必须发生的时间活动 A i A_i Ai的最早开始时间 E ( i ) E(i) E(i)指向该弧的弧尾所表示事件的最早发生时间即 E ( i ) V E ( k ) E(i)VE(k) E(i)VE(k)活动 A i A_i Ai的最晚开始时间 L ( i ) L(i) L(i)指向该弧的弧头所表示事件的最晚发生时间与该活动所需时间之差即 L ( i ) V L ( k ) − W e i g h t ( i ) L(i)VL(k)-Weight(i) L(i)VL(k)−Weight(i)活动 A i A_i Ai的时间余量 D ( i ) D(i) D(i)指在不增加完成整个工程所需总时间的情况下活动 A i A_i Ai可以拖延的时间时间余量为零的活动就是关键活动
2关键路径的计算步骤 1按拓扑排序序列依次求各个顶点的 V E ( k ) VE(k) VE(k) V E ( 源点 ) 0 VE(源点)0 VE(源点)0 V E ( k ) M a x { V E ( j ) W e i g h t ( V j , V k ) } VE(k)Max\{VE(j)Weight(V_j,V_k)\} VE(k)Max{VE(j)Weight(Vj,Vk)} V j V_j Vj为 V k V_k Vk的任意前驱 2按逆拓扑排序序列依次求各个顶点的 V L ( k ) VL(k) VL(k) V L ( 汇点 ) V E ( 汇点 ) VL(汇点)VE(汇点) VL(汇点)VE(汇点) V L ( k ) M i n { V L ( j ) − W e i g h t ( V j , V k ) } VL(k)Min\{VL(j)-Weight(V_j,V_k)\} VL(k)Min{VL(j)−Weight(Vj,Vk)} V j V_j Vj为 V k V_k Vk的任意后继 3求所有活动的最早发生时间 E ( i ) E(i) E(i) 若边 V k , V j V_k,V_j Vk,Vj表示活动 A i A_i Ai则 E ( i ) V E ( k ) E(i)VE(k) E(i)VE(k) 4求所有活动的最晚发生时间 L ( i ) L(i) L(i) 若边 V k , V j V_k,V_j Vk,Vj表示活动 A i A_i Ai则 L ( i ) V L ( j ) − W e i g h t ( V k , V j ) L(i)VL(j)-Weight(V_k,V_j) L(i)VL(j)−Weight(Vk,Vj) 5求所有活动的时间余量 D ( i ) D(i) D(i) D ( i ) L ( i ) − E ( i ) D(i)L(i)-E(i) D(i)L(i)−E(i) 6时间余量为0的活动就是关键活动关键路径由关键活动组成
