丽水做网站,效果好的锦州网站建设,注册营业执照网上申请入口,网站设计的难点文章目录 关键路径引例AOE网关键路径与关键活动关键路径算法引例与原理关键路径算法的实现边的存储结构代码实现运行示例 关键路径
关于拓扑排序的内容见拓扑排序详解
引例
通过拓扑排序我们可以解决一个工程是否可以顺序进行的问题#xff0c;拓扑排序把一个工程分成了若干… 文章目录 关键路径引例AOE网关键路径与关键活动关键路径算法引例与原理关键路径算法的实现边的存储结构代码实现运行示例 关键路径
关于拓扑排序的内容见拓扑排序详解
引例
通过拓扑排序我们可以解决一个工程是否可以顺序进行的问题拓扑排序把一个工程分成了若干个流水级只有当前流水级的工作完成才能进入下一个流水级然而有时候我们还要解决工程完成的最短时间问题。比如说造一辆汽车我们要先造各种各样的零件、部件最终再组装成车。
这些零部件都是在流水线上同时生产的假如造一个轮子需要0.5天造一个发动机需要3天造一个车底盘需要2天造一个外壳需要2天造其他零部件需要2天全部零部件集中到一处需要0.5天组装成车需要2天那么我们生产一辆车最短需要几天呢
如果回答说把所有时间加起来假如所有活动是串行的话那么自然是每个活动时间相加但是这些零件是分别在流水线上同时生产的也就是说生产发动机的3天内我们可能已经生产了6个轮子1.5个外壳1.5个底盘了而车的组装是在所有零部件都生产好之后才可以进行的因此最短时间应该是先导活动中时间最长的发动机3天集中零部件0.5天组装车的2天一共5.5天完成一辆车的生产。
因此我们如果要对一个流程图求最短完成时间就要分析它们的拓扑关系并找到其中的关键流程这个流程的时间就是最短时间。
AOE网
基于我们拓扑排序中AOV网(Activity On Vertex Network)我们根据求流程的最短时间的需求提出一个新的概念。在一个表示工程的带权有向图中用顶点表示事件用有向边表示活动边上的权值表示活动的持续时间这种有向图的边表示活动的网我们称之为AOE网(Activity On Edge Network).
我们把AOE网中入度为0的点称为始点或源点出度为0的点称为终点或汇点它们分别代表工程的开始和结束所以正常情况下AOE网只有一个源点和一个汇点。如下图中顶点vi代表一个事件弧vi , vj则表示一个活动其权值代表活动的持续时间。 AOE网有着明显的工程特性只有某顶点的事件发生后由该顶点出发的各项活动才能开始。只有进入该顶点的所有活动都已经结束该顶点的事件才能发生。
AOE网和AOV网有着相似之处二者都是对工程进行建模但又有很大差别。AOV网用顶点表示活动它描述了活动间的偏序关系AOE网则用边来表示活动边上的权值表示活动的持续时间。仍以我们汽车的流水线生产为例其AOV网和AOE网的对比体现了二者的差别。AOE网是建立在活动的偏序关系或制约关系没有矛盾的基础上再来分析整个工程至少需要多少时间以及为了缩短工程时间可以加快哪些活动或者对于各个活动ddl的限制等。 关键路径与关键活动
我们把路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最大长度的路径叫关键路径在关键路径上的活动叫关键活动。显然就上图的AOE网而言开始→发动机完成→部件集中到位→组装完成就是关键路径路径长度为5.5。
我们发现如果我们加快非关键路径上的活动并不会缩短整个工程的时间即使一个轮子只需要0.1的生产时间也无济于事但是如果我们缩短了关键路径上关键活动的时间如发动机缩短为2.5天组装车缩短为1.5天那么我们的关键路径长度就缩短为了4.5天。
所以我们如何去求关键路径呢
关键路径算法
引例与原理
这是关于关键路径的一个很经典的例子。假设一个学生放学回家除掉吃饭、洗漱外到睡觉前有四小时空闲而家庭作业需要两小时完成。不同的学生会有不同的做法抓紧的学生会在头两小时就完成作业然后看看电视、读读课外书什么的;但也有超过一半的学生比如我(悲)会在最后两小时才去做作业要不是因为没时间可能还要再拖延下去。这也没什么好奇怪的拖延就是人性几大弱点之一。
这里做家庭作业这一活动的最早开始时间是四小时的开始可以理解为0而最晚开始时间是两小时之后马上开始不可以再晚否则就是延迟了此时可以理解为2。显然当最早和最晚开始时间不相等时就意味着有空闲。接着老妈发现了孩子拖延的小秘密太痛了x_x于是买了很多的课外习题要求你四个小时不许有一丝空闲省得你拖延或偷懒。此时整个四小时全部被占满最早开始时间和最晚开始时间都是0因此它就是关键活动了。也就是说我们只需要找到所有活动的最早开始时间和最晚开始时间并且比较它们如果相等就意味着此活动是关键活动活动间的路径为关键路径。如果不等则就不是。
关键路径算法的实现
那么关键路径的求解过程如下 用数组etv(earliest time of vertex)和ltv(latest time of vertex)来存储事件的最早/最晚发生时间 e t v [ k ] { 0 , 当 k 0 时 m a x { e t v [ i ] l e n v i , v k } . , 当 k ≠ 0 且 v i , v k ∈ p [ k ] 时 etv[k] \left\{\begin{matrix} 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,当k0时\\ max\left \{ etv[i]lenvi,vk\right \} .,当k≠0且 vi,vk∈p[k]时 \end{matrix}\right. etv[k]{0 ,当k0时max{etv[i]lenvi,vk}.,当k0且vi,vk∈p[k]时 其中p[ k ]为所有到达vk的边集合转移方程保证了事件k在etv[ k ]发生时其所有先导活动都能完成 l t v [ k ] { e t v [ k ] , 当 k n − 1 时 m i n { l t v [ j ] − l e n v k , v j } , 当 k ≠ n − 1 且 v k , v j ∈ S [ k ] 时 ltv[k] \left\{\begin{matrix} etv[k]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,当kn-1时\\ min\left \{ ltv[j]-lenvk,vj\right \} ,当k≠n-1且 vk,vj∈S[k]时 \end{matrix}\right. ltv[k]{etv[k] ,当kn−1时min{ltv[j]−lenvk,vj},当kn−1且vk,vj∈S[k]时 其中S[k]为vk发出的边集合转移方程保证了事件k在ltv[ k ]发生时其发出的所有活动到达的事件都能在其最早开始时间完成 活动的最早开始时间即其先导事件的最早发生时间因此只有先导事件发生了活动才能开始 活动的最晚开始时间是其抵达事件的最晚发生时间减去活动时长活动再晚也不能等其到达的事件发生了才开始所以要赶在到达的事件发生之前
这里我们使用邻接表来存储边。
边的存储结构
vectorint etv, ltv; // 事件最早发生时间
stackint path; // 存储拓扑序列
struct Edge
{Edge(int a, int w) : adjvex(a), weight(w), _next(nullptr){}// int in;//边的起点这里省去int adjvex;//边的终点int weight;//权值Edge *_next;//in发出的下一条边
};代码实现
求解etv的过程就是一次拓扑排序只不过加了行对于elv的更新开始事件的etv显然是0由开始事件往后由拓扑顺序更新etv
而求解ltv其实就是对于拓扑排序的逆过程因为结束事件的etv和ltv显然相同那么对拓扑序列逆向遍历更新ltv
再根据ltvetv和lteete的关系求寻找我们的关键活动
void TopoLogicalSort(vectorEdge * edges)
{int n edges.size();etv.resize(n);vectorint ind(n); // 记录入度for (auto e : edges){while (e){ind[e-adjvex];e e-_next;}}queueint q;for (int i 0; i n; i)if (!ind[i])q.push(i);int f;while (!q.empty()){f q.front();q.pop();path.push(f); // 存储拓扑序列Edge *e edges[f];while (e){if (!(--ind[e-adjvex]))q.push(e-adjvex);if (e-weight etv[f] etv[e-adjvex])// 如果事件f的etv 活动e的时间晚于etv[adjvex]则更新事件adjvex的etv保证adjvex的etv时事件adjvex的所有先导活动都已完成etv[e-adjvex] e-weight etv[f];e e-_next;}}
}
void CriticalPath(vectorEdge * edges)
{Edge *e nullptr;int ete, lte; // 活动的最早最晚发生时间int n edges.size(), t;TopoLogicalSort(edges);ltv.resize(n);for (int i 0; i n; i)ltv[i] etv[n - 1]; // 初始化最晚发生时间while (!path.empty()){t path.top();path.pop();e edges[t];while (e){if (etv[e-adjvex] - e-weight ltv[t]) // 保证事件t如果在etv开始发出的活动到达的事件都能在其各自etv完成ltv[t] etv[e-adjvex] - e-weight;e e-_next;}}for (int i 0; i n; i){e edges[i];ete etv[i]; // 事件的最早发生时间和其发出活动的最早发生时间一致while (e){lte ltv[e-adjvex] - e-weight;if (lte ete){printf(v%d-v%d length:%d\n, i, e-adjvex, e-weight);break;}e e-_next;}}
}运行示例
运行代码
#include iostream
#include vector
#include queue
#include stack
using namespace std;
vectorint etv, ltv; // 事件最早发生时间
stackint path; // 存储拓扑序列
struct Edge
{Edge(int a, int w) : adjvex(a), weight(w), _next(nullptr){}// int in;int adjvex;int weight;Edge *_next;
};
void TopoLogicalSort(vectorEdge * edges)
{int n edges.size();etv.resize(n);vectorint ind(n); // 记录入度for (auto e : edges){while (e){ind[e-adjvex];e e-_next;}}queueint q;for (int i 0; i n; i)if (!ind[i])q.push(i);int f;while (!q.empty()){f q.front();q.pop();path.push(f); // 存储拓扑序列Edge *e edges[f];while (e){if (!(--ind[e-adjvex]))q.push(e-adjvex);if (e-weight etv[f] etv[e-adjvex])// 如果事件f的etv 活动e的时间晚于etv[adjvex]则更新事件adjvex的etv保证adjvex的etv时事件adjvex的所有先导活动都已完成etv[e-adjvex] e-weight etv[f];e e-_next;}}
}
void CriticalPath(vectorEdge * edges)
{Edge *e nullptr;int ete, lte; // 活动的最早最晚发生时间int n edges.size(), t;TopoLogicalSort(edges);ltv.resize(n);for (int i 0; i n; i)ltv[i] etv[n - 1]; // 初始化最晚发生时间while (!path.empty()){t path.top();path.pop();e edges[t];while (e){if (etv[e-adjvex] - e-weight ltv[t]) // 保证事件t如果在etv开始发出的活动到达的事件都能在其各自etv完成ltv[t] etv[e-adjvex] - e-weight;e e-_next;}}for (int i 0; i n; i){e edges[i];ete etv[i]; // 事件的最早发生时间和其发出活动的最早发生时间一致while (e){lte ltv[e-adjvex] - e-weight;if (lte ete){printf(v%d-v%d length:%d\n, i, e-adjvex, e-weight);break;}e e-_next;}}
}
int main()
{int n, cnt, adj, w;cout 请输入事件数量 endl;cin n;Edge *e;vectorEdge * edges(n, nullptr);for (int i 0; i n; i){cout 活动数目 endl;cin cnt;for (int j 0; j cnt; j){cout 输入活动输入顶点和权值 endl;cin adj w;e new Edge(adj, w);e-_next edges[i];edges[i] e;}}CriticalPath(edges);return 0;
}
