阅读:0       作者:严长生

关键路径算法详解

对于工程管理,人们最关注的两个问题分别是工程是否能顺利进行,以及估算整个工程完成所需要的最短时间和影响工程时间的关键活动。前一个问题可用拓扑排序解决,后一个问题则需要找出工程进行的关键路径,关键路径上的活动完成所需要的时间就是工程完成所需要的最短时间。

关键路径通常是所有工程活动中最长的路径,关键路径上的活动如果延期将直接导致工程延期。

利用 AOV 网表示有向,可以对活动进行拓扑排序,根据排序结果对工程中活动的先后顺序做出安排。但是寻找关键路径,估算工程活动的结束时间,则需要使用 AOE 网表示有向图。

AOE 网中用顶点表示事件,有向边表示活动,边上的权值表示活动持续的时间。只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始,反之亦然,只有在指向某一顶点的各有向边所代表的活动都己经结束后,该顶点所代表的事件才能发生。

AOE 网只有一个入度为0的顶点(源点)和一个出度为 0 的顶点(汇点),分别代表开始事件和结束事件,其他的顶点则表示两个意义,其一是此点之前的所有活动都己经结束,其二是此点之后的活动可以开始了。

计算关键路径的算法需要根据AOE网的特征调整图的数据结构定义,本节介绍的算法仍然使用邻接表来表示图,但是需要重新定义顶点和边的数据结构。因为 AOE 网的边代表具体的活动,需要在数据结构中明确体现“边”的定义,调整后的边和顶点的定义如下所示:
typedef struct tagEdgeNode {
    int vertexlndex; //活动边终点顶点索引 std::string name; //活动边的名称
    int duty;   //活动边的时间(权重)
}EDGE_NODE;

typedef struct tagVertexNode {
    int sTime; //事件最早开始时间
    int eTime; //事件最晚开始时间
    int inCount; //活动的前驱节点个数
    std::vector<EDGE_NODE> edges; //相邻边表
}VERTEX_NODE;
算法开始之前,每个顶点的 sTime 被初始化为 0,eTime 被初始化为一个有效范围之外的最大值(0x7FFFFFFF),算法结束之后,sTime 和 eTime 会被计算为实际的时间值。

什么是关键路径

开始讨论关键路径之前,先来介绍一下活动的最早开始时间和最晚开始时间。

工程中一个活动何时开始依赖于其前驱活动何时结束,只有所有的前驱活动都结束后这个活动才可以开始,前驱活动都结束的时间就是这个活动的最早开始时间。与此同时,在不影响工程完工时间的前提下,有些活动的开始时间存在一些余量,在时间余量允许的范围之内推迟一段时间开始活动也不会影响工程的最终完成时间,活动的最早开始时间加上这个时间余量就是活动的最晚开始时间。活动不能在最早开始时间之前开始,当然,也不能在最晚开始时间之后开始,否则会导致工期延误。

如果一个活动的时间余量为 0,即该活动的最早开始时间和最晚开始时间相同,则这个活动就是关键活动,由这些关键活动起来的一个工程活动路径就是关键路径。根据关键路径的定义,一个工程中的关键路径可能不止一个,我们常说的关键路径指的是工程时间最长的那条路径,也就是从源点到汇点之间最长的那条活动路径。

计算关键路径的算法

计算关键路径的基础是先找出工程中的所有关键活动,确定一个活动是否是关键活动的依据就是活动的最早开始时间和最晚开始时间,因此需要先介绍如何计算活动的最早开始时间和最晚开始时间。

在 AOE 网中,事件 ei 必须在指向 ei 的所有活动都结束后才能发生,只有 ei 发生之后,从 ei 发出的活动才能开始,因此 ei 的最早发生时间就是 ei 发出的所有活动的最早开始时间。

如果用 est[i] 表示事件 ei 的最早开始时间,用 duty[i,y] 表示连接事件 ei 和事件 ej 的活动需要持续的时间,则事件 ei 的最早开始时间可以用以下关系推算:

est[0] = 0
est[n] = max{est[i]+duty[i,n], est[j]+duty[j,n],...., est[k]+duty[k,n]}(其中i,j,...k是事件n的前驱事件)

这个推算关系是建立在合法的拓扑序列的基础上的,因此,推算事件的最早开始时间需要对图中的事件节点进行拓扑排序。本节我们只关注最早开始时间的计算方法。

假设 sortedNode 参数中存放的图的拓扑排序结果,CalcESTime() 函数从拓扑序列的第一个顶点开始(变量 u 代表的顶点),遍历这个顶点发出的有向边指向的相邻顶点(变量 v 代表的顶点),如果该顶点的最早开始时间与有向边代表的活动持续时间的和(这个结果存放在临时变量 uvst 中)大于有向边指向的相邻顶点的最早开始时间,则更新这个相邻顶点的最早开始时间。

需要注意的是,算法并没有直接利用推算关系中的 max 选择处理,而是按照 sortedNode 序列中的顶点先后关系,只在处理到相邻顶点时才更新最早开始时间(这正是所有顶点的 sTime 被初始化成 0 的原因),当 sortedNode 序列中的所有顶点都处理完之后,就相当于变相地实现了max 选择的处理。
void CalcESTime(GRAPH *g, const std::vector<int>& sortedNode)
{
    g->vertexs[0].sTime = 0; //est[0] = 0
    std::vector<int>::const_iterator nit = sortedNode.begin();
    for(; nit != sortedNode.end(); ++nit)
    {
        int u = *nit;
        //遍历u出发的所有有向边
        std::vector<EDGE_NODE>::iterator eit = g->vertexs[u].edges.begin();
        for(; eit != g->vertexs[u].edges.end(); ++eit)
        {
            int v = eit->vertexlndex;
            int uvst = g->vertexs[u].sTime + eit->duty;
            if(uvst > g->vertexs[v].sTime)
            {
                g->vertexs[v].sTime = uvst;
            }
        }
    }
}
事件 ei 的最晚开始时间定义为:ei 的后继事件 ej 的最晚开始时间减去 ei 和 ej 之间的活动的持续时间的差,当 ei 有多个后继事件时,则取这些差值中最小的一个作为 ei 的最晚开始时间。如果用 lst[j] 表示事件 ej 的最晚开始时间,用 dutyt[i,j] 表示事件 ei 和后继事件 ej 之间的活动需要持续的时间,则事件 ei 最晚开始时间可以用以下关系推算:

lst[n] = est[n]
est[i] = min{lst[j]-duty[i,j], est[k]-duty[i,k],...,est[m]-duty[i,w]}
(其中j,k...,m是事件i的后继事件)

这个最晚开始时间的推算关系是建立在合法的拓扑序列的逆序基础上的,CalcLSTime() 函数对 sortedNode 序列的处理顺序和 CalcESTime() 函数刚好相反,从拓扑序列的最后一个顶点(变量 u 代表的顶点)开始向前遍历。如果该顶点的后继顶点(变量 v 代表的顶点)的最晚开始时间与连接这两个顶点的活动的持续时间的差小于该顶点(u 顶点)的最晚开始时间,则更新该顶点的最晚开始时间。

和 CalcESTime() 函数一样,CalcLSTime() 函数也没有直接利用 min 选择处理,但是通过逆序遍历 sortedNode 序列中的所有顶点,变相地实现了 min 选择的处理。
void CalcLSTime(GRAPH *g, const std::vectors<int>& sortedNode)
{
    //最后一个节点的最晚开始时间等于最早开始时间
    g->vertexs[g->count - 1].eTime = g->vertexs[g->count - 1].sTime;
    std::vector<int>::const_reverse_iterator cit = sortedNode.rbegin();
    for(; cit != sortedNode.rend(); ++cit)
    {
        int u = *cit;
        //遍历u出发的所有有向边
        std::vector<EDGE_NODE>::iterator eit = g->vertexs[u].edges.begin();
        for(; eit != g->vertexs[u].edges.end(); ++eit)
        {
            int v = eit->vertexlndex;
            int uvet = g->vertexs[v].eTime - eit->duty;
            if(uvet < g->vertexs[u].eTime)
            {
                g->vertexs[u].eTime = uvet;
            }
        }
    }
}
在 AOE 网中计算好每个顶点代表的事件的最早开始时间和最晚开始时间之后,就可以很容易计算出每条边代表的活动的最早开始时间和最晚幵始时间。

假如某个活动两端的事件分别是 ei 和 ej,则该活动的最早开始时间就是事件 ei 的最早开始时间,该活动的最晚开始时间就是事件 ej 的最晚开始时间减去该活动的持续时间。用这个关系计算出所有活动的最早开始时间和最晚开始时间,只要最早开始时间和最晚开始时间相同的活动都是关键活动,按照事件顶点的拓扑序列的先后关系,顺序输出这些事件顶点相关的关键活动,得到的关键活动序列就是关键路径。

综合前面的分析,计算关键路径的需要以下四个步骤。
  1. 对事件顶点进行拓扑排序,得到事件的拓扑序列;
  2. 计算事件顶点的最早开始时间;
  3. 计算事件顶点的最晚开始时间;
  4. 计算活动的最早幵始时间和最晚开始时间,并按照事件的拓扑顺序逐次输出关键活动,得到关键路径。

这四个步骤非常清晰地体现在 CriticalPath() 函数中,重点是第四个步骤输出关键路径。判断活动是否是关键活动是通过这行 if 语句实现的:

if(g->vertexs[u].sTime == g->vertexs[v].eTime - eit->duty)

但是要实现按照活动顺序输出关键活动路径的功能,还需要按照事件顶点拓扑排序的结果逐个判断每个事件发出的活动(就是事件顶点发出的有向边),按照活动的开始次序逐个输出关键活动。

CriticalPath() 函数中的第一个 for 循环就是按照拓扑排序的结果逐个处理事件顶点,第二个 for 循环就是搜索一个顶点的所有有向边,查找关键活动。
bool CriticalPath(GRAPH *g)
{
    std::vector<int> sortedNode;
    if(!TopologicalSorting(g, sortedNode)) //步骤 1
    {
        return false;
    }
    CalcESTime(g, sortedNode); //步骤2
    CalcLSTime(g, sortedNode); //步骤3
    //步骤4:输出关键路径上的活动名称
    std::vector<int>::iterator nit = sortedNode.begin();
    for(; nit != sortedNode.end(); ++nit)
    {
        int u = *nit;
        std::vector<EDGE_NODE>::iterator eit = g->vertexs[u].edges.begin();
        for(; eit != g->vertexs[u].edges.end(); ++eit)
        {
            int v = eit->vertexlndex;
            if(g->vertexs[u].sTime == g->vertexs[v].eTime - eit->duty)
            {
                std::cout << eit->name << std::endl;
            }
        }
    }
    return true;
}
表 1 活动数据
活动名称 时间(天) 依赖
P1 8  
P2 5  
P3 6 P1,P2
P4 4 P3
P5 7 P2
P6 7 P4,P5
P7 4 P1
P8 3 P7
P9 4 P4,P8

对于表 1 的活动关系数据,转化成 AOE 网形式的有向图之后,用 CriticalPath() 函数计算出的关键路径是 P1-P3-P4-P6