算法图算法

DAG典型应用-活动网络

字数统计: 2.9k字   |   阅读时长: 12分
, ,

摘要: AOV、AOE 两种活动网络。关键路径算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$0 活动网络

活动网络(activity network)是一种 DAG，可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。

活动网络可分为两种: AOV 网络和 AOE 网络。

$1 AOV 网络与拓扑排序

AOV 网

一般一个工程可以分成若干个子工程，这些子工程称为活动(activity)。完成了这些活动，整个工程就完成了。

可以用有向图来表示一个工程。在这种有向图中，用顶点表示活动，用有向边 (u, v) 表示活动 u 必须先于活动 v 进行。这种有向图叫做顶点表示活动的网络(activity on vertices)，记 作 AOV 网络。

例子

AOV网

拓扑排序

AOV 上的问题，例如判定 DAG，确定活动顺序。均可以用拓扑排序解决。参考文章: 拓扑排序

$2 AOE 网络与关键路径

AOE 网

如果在有向无环图中用有向边表示一个工程中的各项活动(Activity)，用有向边上的权值表示活动的持续时间(duration)，用顶点表示事件(Event)，则这种有向图叫做用边表示活动的网络(activity on edges)，简称 AOE 网络。

由于整个工程只有一个开始点和一个完成点，所以称开始点(即入度为 0 的顶点)为源点(source)，称结束点(即出度为 0 的顶点)为汇点(sink)。

AOE 网络在某些方面(如工程估算)非常有用，例如，从 AOE 网络可以了解到:

  • (1) 完成整个工程至少需要多长时间?
  • (2) 为缩短完成工程所需的时间，应加快哪些活动?

例子

AOE网

关键路径

在 AOE 网络中，有些活动可以并行进行。从源点到各个顶点，以及从源点到汇点的有向路径可能不止一条，这些路径的长度可能也不同。完成不同路径上每个活动所需的总时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，所需时间为这条路径上所有活动的持续时间之和。这条路径长度最长的路径就称为关键路径(critical path)。

关键路径求解方法

  • 参考：《图论算法理论、实现及应用》

要找出关键路径，必须找出关键活动。所谓关键活动(critical activity)，就是不按期完成就会影响整个工程完成的活动。关键路径上所有活动都是关键活动，因此，只要找到关键活动，就可以找到关键路径。

DAG D = (E, A)，E 为事件(顶点)集合，A 为活动(边)集合，源点 E[0]， 汇点 E[n- 1]，边权 w[i][j]。

  • (1) 事件 E[i] 的最早可能开始时间，记为 Ee[i]。Ee[i]是从源点 E[0] 到顶点 E[i] 的最长路径长度。
  • (2) 事件 E[i] 的最迟允许开始时间，记为 El[i]。El[i]是在保证汇点 E[n-1] 在 Ee[n-1] 时刻完成的前提下， 事件 E[i] 的允许最迟开始时间，它等于 Ee[n-1] 减去从 E[i] 到 E[n-1] 的最长路径长度。
  • (3) 活动 A[k] 的最早可能开始时间，记为 e[k]。设活动 A[k] 在有向边 E[i] -> E[j] 上， e[k] = Ee[i]。
  • (4) 活动 A[k] 的最迟允许开始时间，记为 l[k]。设活动 A[k] 在有向边 E[i] -> E[j] 上， l[k] 是在不会引起时间延误的前提下，该活动允许的最迟开始时间。l[k] = El[j] – w[i][j]。

l[k] – e[k] 表示活动 A[k] 的最早可能开始时间和最迟允许开始时间的时间余量，也叫做松弛时间(slack time)。l[k] == e[k]表示活动 A[k] 没有时间余量，是关键活动。

因此，分析关键路径的目的，是要从源点 E[0] 开始估算每个活动，辩明哪些是影响整个工程进度的关键活动，以便科学的安排工作。

为了找出关键活动，就需要求得各个活动的 e[k] 与 l[k]，以判别二者是否相等;
而为了求得 e[k] 与 l[k]，就要先求得从源点 E[0] 到各个顶点 E[i] 的最早可能开始时间 Ee[i] 和最迟允许开始时间 El[i]。

其中有一步是求源点到各个带你的最长路径，以及汇点到各个点的最长路径，就是给定 DAG 已经起点 S 终点 T，求 S 到 T 的最长路径。

这个问题有两种解法，参考：DAG上的DP。

  • 一种是 DAG 上的 DP，推导 DP 状态的顺序为拓扑序。
  • 一种是将权值取相反数后用 Bellman Ford 或 spfa 求最短路径，其松弛操作与 DP 的转移方程是一样的。

模板题：PTA 7-11 关键活动

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。

任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。

请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。

算法

(1) 建图

给定带权有向图 D，和反图 RD (邻接表)，同时记录入度和出度。

如果没有入度为零或出度为零的点，则直接返回不可行。

将所有入度为零的点连接一个超级源 SS，边权为 0。将所有出度为零的点连接一个超级汇 ST，边权为 0。

(2) 求最长路径

BFS 拓扑序 DP 求 S 到 T 的最长路径。

1
2
3
4
5
6
7
8
9
10
11
12
dp[v] := S 到 v 的最长路径

初始化
dp[v] = INT_MIN / 2;
dp[S] = 0

答案
dp[T]

转移
dp[v] = dp[u] + e[u][v] 
其中 (u, v) 为 D 的有向边且 dp[u] != INT_MIN / 2

拓扑排序结束后，遍历所有节点，如果存在 v，dp[v] = INT_MIN / 2，则返回 0。即点 v 的入度始终到不了 0，内部出现了环。

按照以上方法求出超级源 SS 到各点的最长路径 dp1 和超级汇到超级汇到各点的最长路径 dp2

(3) 求关键活动

预处理各个点的信息：

1
2
Ee[i] := 事件 i 的最早可能开始时间, Ee[i] = dp1[i]
El[i] := 事件 i 的最迟允许开始时间, El[i] = Ee[ST] - dp2[i] = dp1[ST] - dp2[i]

枚举各边 e，判定是否为关键活动。

1
2
3
4
int ee = Ee[u]; // 活动 e 的最早可能开始时间
int le = El[v] - w; // 活动 e 的最迟允许开始时间

if(ee == le) 则 e 为关键活动

代码 (模板: AOE 网络求关键活动)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

struct Edge
{
    int u, v, w;
    int id;
    Edge(int u, int v, int w, int id):u(u),v(v),w(w),id(id){}
    Edge(){}
};

struct Cmp
{
    bool operator()(const Edge& e1, const Edge& e2) const
    {
        if(e1.u == e2.u)
            return e1.id > e2.id;
        return e1.u < e2.u;
    }
};

struct EdgeTo
{
    int v, w;
    EdgeTo(int v, int w):v(v),w(w){}
};

vector<int> top_sort(const vector<vector<EdgeTo>>& g, int SS, vector<int>& indegrees)
{
    int N = g.size();
    vector<int> dp(N, INT_MIN / 2);
    dp[SS] = 0;
    queue<int> q;
    q.push(SS);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(EdgeTo son: g[u])
        {
            int v = son.v;
            int w = son.w;
            if(dp[u] + w > dp[v])
                dp[v] = dp[u] + w;
            --indegrees[v];
            if(indegrees[v] == 0)
                q.push(v);
        }
    }
    return dp;
}

int main()
{
    int N, M;
    // fstream fin("./test.txt");
    cin >> N >> M;
    // fin >> N >> M;
    // 建图，提前开好超级源和超级汇的空间
    vector<vector<EdgeTo>> g(N + 2), rg(N + 2);
    vector<int> indegrees(N + 2, 0);
    vector<int> outdegrees(N + 2, 0);
    vector<Edge> edges(M);
    for(int i = 0; i < M; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        // fin >> u >> v >> w;
        edges[i].u = u;
        edges[i].v = v;
        edges[i].w = w;
        edges[i].id = i;
        g[u].emplace_back(v, w);
        rg[v].emplace_back(u, w);
        ++indegrees[v];
        ++outdegrees[u];
    }
    // 找 0 入度点链接超级源
    int SS = 0; // 0 为超级源
    int ST = N + 1; // N + 1 为超级源
    bool flag1 = false, flag2 = false;
    for(int i = 1; i <= N; ++i)
    {
        if(indegrees[i] == 0)
        {
            g[SS].emplace_back(i, 0);
            rg[i].emplace_back(SS, 0);
            ++indegrees[i];
            ++outdegrees[SS];
            flag1 = true;
        }
        if(outdegrees[i] == 0)
        {
            g[i].emplace_back(ST, 0);
            rg[ST].emplace_back(i, 0);
            ++indegrees[ST];
            ++outdegrees[i];
            flag2 = true;
        }
    }
    // 无 0 入度点特判
    if(!flag1 || !flag2)
    {
        cout << 0 << endl;
        return 0;
    }
    // BFS 拓扑序 DP
    vector<int> dp1 = top_sort(g, SS, indegrees);
    vector<int> dp2 = top_sort(rg, ST, outdegrees);
    // 判定环
    if(dp1[ST] == INT_MIN / 2)
    {
        cout << 0 << endl;
        return 0;
    }
    // 返回最短时间
    cout << dp1[ST] << endl;

    // 寻找关键活动
    // 预处理信息
    // Ee[i] := 事件 i 的最早可能开始时间, Ee[i] = dp1[i]
    // El[i] := 事件 i 的最迟允许开始时间, El[i] = Ee[ST] - dp2[i] = dp1[ST] - dp2[i]
    vector<int> &Ee = dp1;
    vector<int> El(N + 2);
    for(int i = 0; i <= N + 1; ++i)
        El[i] = dp1[ST] - dp2[i];
    sort(edges.begin(), edges.end(), Cmp());
    for(Edge &e: edges)
    {
        int u = e.u, v = e.v, w = e.w;
        int ee = Ee[u]; // 活动 e 的最早可能开始时间
        int le = El[v] - w; // 活动 e 的最迟允许开始时间
        if(ee == le)
        {
            // 没有余量，是关键活动
            cout << u << "->" << v << endl;
        }
    }
}
Share