小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

图算法入门4：活动网络-AOE网络和关键路径（critical path）

作者：小小林熬夜学编程 | 2024-06-08 16:09:57

踩

aoe网络

AOE网络的基本概念

上一节介绍了活动网络AOV网络的相关内容，这一节将进一步介绍另一种活动网络AOE网络。如果对于有向无环图(DAG)，用有向边表示一个工程的各项活动（activity）,边上的权值表示活动的持续时间（duration）,用顶点表示事件（event），那么这种DAG被称为边表示活动的网络（Activity On Edges）,简称AOE网络。

图1

如图所示为一个AOE网络，可以看到有11项活动 $a_{1-11}$ ，有9个事件 $E_{0-8}$ 。事件 $E_i$ 发生表示之前的活动都已经完成，例如 $E_4$ 发生表示 $a_4$ 和 $a_5$ 已完成， $a_7$ 和 $a_8$ 可以开始。每条边的权重表示对应活动的持续时间。工程开始之后， $a_{1-3}$ 可以并行执行，而 $E_4$ 发生后， $a_{7-8}$ 也可以并行执行。对于AOE网络，其有两个特殊的顶点：开始点（ $E_0$ , 入度为0的顶点）称之为源点（source）和结束点（ $E_8$ ，出度为0的点）称之为汇点（sink），分别表示整个工程的开始和结束，均只有一个。

AOE网络主要要解决的问题：

1.完成整个工程至少需要多长时间？

2.为缩短完成工程的事件，应加快哪些活动？

可以看到从源点到汇点有多条路径，而由于并行化的原因，完成整个工程所需的时间取决于最长路径的长度，这条最长路径称为关键路径（critical path）。例如图1的关键路径为 $a_1, a_4, a_7, a_{10}$ 或者 $a_1,a_4, a_8, a_{11}$ ，持续时间之和都是18。

关键路径求解方法

关键量定义

找出关键路径可以分解为找出关键活动（critical activity）,即关键路径上的所有活动。先定义几个关键量：

1） $E_e[i]$ :事件 ${E_i}$ 最早可能的开始时间， $E_e[i]$ 表示顶点 $E_0$ 到顶点 $E_i$ 的最长路径长度，例如 $E_e[4]=7$ ;

2） $E_l[i]$ :事件 $E_i$ 最迟允许开始时间，即在保证汇点 $E_{n-1}$ 在 $E_e[n-1]$ 时刻完成的前提下，事件 $E_i$ 的允许最迟开始时间，其等于 $E_e[n-1]$ 减去 $E_i$ 到 $E_{n-1}$ 的最长路径长度,例如 $E_l[5]=10$ ;

3） $e[k]$ :活动 $a_k$ 的最早可能开始时间， $a_k$ 在有向边 $<E_i,E_j>$ 上，则 $e[k]$ 是从源点 $E_0$ 到顶点 $E_i$ 的最长路径长度，因此 $e[k]=E_e[i]$ ;

4） $l[k]$ :活动 $a_k$ 的最迟允许开始时间， $a_k$ 在有向边 $<E_i,E_j>$ 上，则 $l[k]$ 是在不会引起时间延迟的前提下，该活动允许的最迟开始时间。 $l[k]=E_l[j]-dur(<E_i,E_j>)$ , $dur(<E_i,E_j>)$ 为完成 $a_k$ 所需的时间。

$l[k]-e[k]$ 表示活动 $a_k$ 的最早可能开始时间和最迟允许开始时间的时间余量，也称为松弛时间（slack time）。若 $l[k]==e[k]$ 则表示活动 $a_k$ 没有时间余量，是关键活动。

看下图1的例子，对于 $a_8$ :

$e[8]=E_e[4]=7$

$l[8]=E_l[7] - dur(<E_4,E_7>) = 14-7 =7$ 。

故 $a_8$ 是关键路径上的关键活动。

考虑 $a_9$ :

$e[9]=E_e[5]=7$

$l[9]=E_l[7] - dur(<E_5,E_7>) = 10$

故 $a_9$ 可以推迟3个时间单位,并不是关键活动。

递推关系

为了找出关键活动，就需要求得各个活动的 $e[k]$ 和 $l[k]$ ，从而判别二者是否相等。而要求得 $e[k]$ 和 $l[k]$ 需要先求得各个顶点 $E_i$ 的最早可能开始时间 $E_e[i]$ 和最迟允许开始时间 $E_l[i]$ 。下面分别介绍求 $E_e[i]$ 、 $E_l[i]$ 、 $e[k]$ 和 $l[k]$ 的递推公式。

1.求 $E_e[i]$ 的递推公式，从 $E_e[0] = 0$ 开始，向前递推

$E_e[i]=\mathop{max}\limits_{j}\{ E_e[j] + dur(<E_j,E_i>) \}, <E_j, E_i> \in S_2, i = 1, 2, ..., n-1$

$S_2$ 为指向顶点 $E_e[i]$ 得所有有向边 $<E_j,E_i>$ 的集合。

2.求 $E_l[i]$ 的递推公式。从 $E_l[n-1] = E_e[n-1]$ （有定义可知）开始，反向递推

$E_l[i]=\mathop{min}\limits_{j}\{ E_l[j] - dur(<E_i,E_j>) \}, <E_i, E_j> \in S_1, i = n-2, n-3, ..., 0$

$S_1$ 是所有从顶点 $E_i$ 出发的有向边 $<E_i,E_j>$ 集合。

显然这两条递推公式可以通过之前的定义直接得到。

这两个递推公式的计算必须分别在拓扑排序和逆拓扑排序的前提下进行，逆拓扑排序（reverse topological sort）是指首先输出出度为0的顶点，以相反的次序输出拓扑排序序列。

按照拓扑排序，在计算 $E_e[i]$ 时， $E_i$ 的所有前驱顶点 $E_j$ 的 $E_e[j]$ 都已经求出。

按照逆拓扑排序，在计算 $E_l[i]$ 时， $E_i$ 的所有后继顶点 $E_j$ 的 $E_l[j]$ 都已经求出，这里我们需要根据拓扑排序计算的 $E_e[i]$ 来计算 $E_l[i]$ 。

3.求 $e[k]$ 和 $l[k]$ 的递推公式，活动 $a_k$ 对应带权有向边 $<E_i,E_j>$ ，则有 $e[k]=E_e[i]$ , $l[k]=E_l[j]-dur(<E_i,E_j>)$

关键路径算法实现

根据前面分析，我们可以给出计算关键路径的算法

1）构建邻接表；

2）从源点 $E_0$ 出发，令 $E_e[0]=0$ ,按照拓扑排序计算每个顶点的 $E_e[i]$ ，若存在有向环则不能继续求关键路径；

3）从汇点 $E_{n-1}$ 出发，令 $E_l[n-1]=E_{n-1}$ ,按照逆拓扑排序求各顶点的的 $E_l[i]$ ；

4）根据各顶点的 $E_e[i]$ 和 $E_l[i]$ ，求各边的 $e[k]$ 和 $l[k]$ ；

5）每条边如果满足 $e[k]=l[k]$ ,则是关键活动，求出所有关键活动并输出。

代码实现

基于上一节AOV网络的代码来实现，同样用邻接表来表示连接，但需要增加连接的信息，每个连接的数据结构变为：


typedef struct Vertex{
	string name; //顶点名字
	int index; //顶点索引编号
	int dur; // 活动的持续时间
	int no; // 活动序号
	Vertex(string inputName, int inputIndex, int inputDur, int inputNo):name(inputName),index(inputIndex),dur(inputDur),no(inputNo){}
	Vertex():name(""),index(0),dur(0),no(0){}
} VertexNode;

增加活动持续时间和活动序号，另外图信息文件与之前有所不同，文件得每一样存储内容格式如下：起始顶点->连接顶点1->连接1持续时间->连接顶点2->连接2持续时间.....

我们一个例子（graph_struct.txt）：


0 1 6 2 4 3 5
1 4 1
2 4 1
3 5 2
4 6 9 7 7
5 7 4
6 8 2
7 8 4
8

对应的就是图1中的图结构，完整代码如下：


#include<iostream>
#include<vector>
#include<fstream>
#include<sstream>
#include<string>
#include<unordered_map>
#include<stack>
using namespace std;
typedef struct Vertex{
	string name; //顶点名字
	int index; //顶点索引编号
	int dur; // 活动的持续时间
	int no; // 活动序号
	Vertex(string inputName, int inputIndex, int inputDur, int inputNo):name(inputName),index(inputIndex),dur(inputDur),no(inputNo){}
	Vertex():name(""),index(0),dur(0),no(0){}
} VertexNode;
// graph表示邻接表，id表示每个节点入度统计，topSortId存储拓扑排序的索引。
bool criticalPath(const vector<vector<VertexNode> >& graph, const vector<vector<VertexNode> >& revGraph, vector<int>& id, vector<int>& invId,
	vector<int>& Ee, vector<int>& El, vector<int>& e, vector<int>& L) {
	vector<int> topSortId;
	topSortId.reserve(graph.size());
	//step1: 拓扑排序，获取各事件最早可能开始时间Ee
	stack<int> S; // 栈，存放入度为0的顶点
	for(int i = 0; i < graph.size(); i++) {
		if (id[i] == 0) {
			S.push(i);
		}
	}
	for (int i = 0; i < graph.size(); i++) {
		if(S.empty()) {
			return false;
		}
		int j = S.top();
		S.pop(); //弹出栈顶存储的顶点j
		topSortId.push_back(j); //存入拓排序序列
		for(int k = 0; k < graph[j].size(); k++) {
			int currentIndex = graph[j][k].index; // 顶点j连接的顶点
			int currentDur = graph[j][k].dur; // 顶点j连接的顶点之间边的活动持续时间
			if(--id[currentIndex] == 0) {
				S.push(currentIndex);
			}
			if (Ee[j] + currentDur > Ee[currentIndex]) {
				Ee[currentIndex] = Ee[j] + currentDur;
			}
		}
	}
	// step2: 逆拓扑排序，获取各事件最迟允许开始时间El
	stack<int> S1; // 栈，存放出度为0的顶点
	for(int i = 0; i < El.size(); i++) {
		El[i] = Ee[topSortId.back()];
		if(invId[i] == 0) S1.push(i); //初始出度为0的顶点入栈
	}
	for (int i = 0; i < revGraph.size(); i++) {
		int j = S1.top();
		S1.pop(); //弹出栈顶存储的顶点j
		for(int k = 0; k < revGraph[j].size(); k++) {
			int currentIndex = revGraph[j][k].index; // 顶点j连接的顶点
			int currentDur = revGraph[j][k].dur; // 顶点j连接的顶点之间边的活动持续时间
			if(--invId[currentIndex] == 0) {
				S1.push(currentIndex);
			}
			if (El[j] - currentDur < El[currentIndex]) {
				El[currentIndex] = El[j] - currentDur;
			}
		}
	}
	// step3: 判定各条边是否是关键活动
	for(int i = 0; i < graph.size(); i++) {
		for(int k = 0; k < graph[i].size(); k++) {
			int currentIndex = graph[i][k].index; // 顶点j连接的顶点
			int currentDur = graph[i][k].dur; // 顶点j连接的顶点之间边的活动持续时间
			int no = graph[i][k].no; // 该条边对应活动的序号
			e[no] = Ee[i];
			L[no] = El[currentIndex] - currentDur;
			if(e[no] == L[no]) {
				cout << "a" << no + 1 <<" : " << i << "->" << currentIndex <<endl;
			}
		}
	}
	return true; // 如果前面所有顶点全部循环没问题，那么说明可以拓扑排序故返回true.
}
int main() {
	unordered_map<string ,int> graphMap; // 图节点名和编号的Map
	vector<vector<VertexNode> > adjGraph; // 图的连接表表示法，邻接表
	vector<vector<VertexNode> > reverseAdjGraph; // 图的连接表表示法，逆邻接表
	ifstream graphRdFile("graph_struct.txt");
	if(!graphRdFile.good()) {
		cout << "open graph file failed!" << endl;
		return -1;
	}
	string line;
	int index = 0;
	string vertexName;
	// 首先对Vertex Name进行编码
	while (getline(graphRdFile, line)) {
		istringstream ss(line);
		string tmp1,tmp2; //顶点名字和顶点权重。
		if (ss >> tmp1) {
			if (graphMap.find(tmp1) == graphMap.end()) {
				graphMap.insert(make_pair(tmp1, index++));
			}
		}
		while(ss >> tmp1 >> tmp2) {
			if (graphMap.find(tmp1) == graphMap.end()) {
				graphMap.insert(make_pair(tmp1, index++));
			}
		}
	}
	// 编码与Vertex的反映射
	vector<string> indexName = vector<string>(graphMap.size(),"");
	for(auto itr=graphMap.begin();itr!=graphMap.end();itr++) {
		indexName[itr->second] = itr->first;
	}
	// 重新读
	graphRdFile.clear();
	graphRdFile.seekg(0,std::ios::beg);
	adjGraph.resize(graphMap.size());
	reverseAdjGraph.resize(graphMap.size());
	int currentIndex = 0; // 当前图节点的编号
	vector<int> id(adjGraph.size(), 0); // 每个节点入度统计
	vector<int> invId(adjGraph.size(), 0); // 每个节点出度统计
	vector<int> Ee(adjGraph.size(), 0); //各事件最早可能开始时间
	vector<int> El(adjGraph.size(), 0); //各事件最迟允许开始时间
	int activNum = 0; // 活动序号
	while (getline(graphRdFile, line)) { //按行读，每一行是一个图节点的连接情况
		istringstream ss(line);
		string tmp; // 顶点名字
		int inputDur; //顶点权重
		bool firstFlag = true;
		while(ss >> tmp) {
			if (firstFlag) {
				if (graphMap.find(tmp) != graphMap.end()) {
					currentIndex = graphMap[tmp];
				} else {
					break;
				}
				firstFlag = false;
				continue;
			}
			if (graphMap.find(tmp) != graphMap.end()) {
				if(ss >> inputDur){
					adjGraph[currentIndex].emplace_back(VertexNode(tmp,graphMap[tmp],inputDur, activNum++)); //邻接表构造
					id[graphMap[tmp]]++; // 终点入度+1
					invId[currentIndex]++; //起点出度+1
					reverseAdjGraph[graphMap[tmp]].emplace_back(VertexNode(indexName[currentIndex],currentIndex,inputDur,0));
				}
			}
		}
	}
	vector<int> e(activNum, 0);  //各活动最早可能开始时间
	vector<int> L(activNum, 0);  //各活动最迟允许开始时间
	// AOE关键路径测试：
	if(criticalPath(adjGraph, reverseAdjGraph, id, invId, Ee, El, e, L)) {
		cout << "Success!" << endl;
	} else {
		cout << "Network has a cycle!" << endl;
	}
	return 0;
}

对应图1的图结构执行结果如下：


a1 : 0->1
a4 : 1->4
a7 : 4->6
a8 : 4->7
a10 : 6->8
a11 : 7->8
Success!

可以看到成功输出了所有的关键活动。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/690338