请选择 进入手机版 | 继续访问电脑版

关键路径(AOE)网 通俗易懂

[复制链接]
谢世民 发表于 2021-1-1 18:34:24 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
关键路径

  关键路径是求「工程上时间最短的问题」的方法
  阅读本文前请先相识
  拓扑排序
拓扑排序主要解决「工程是否能顺序举行」的问题,关键路径在拓扑排序的基础上解决「工程最短时间的问题」。
一、工程最短时间


工程时间最短的问题:
<blockquote>  按照工厂上图生产一辆汽车,外壳、发动机、轮子和其他部件可以同时制作。
  (1)求组装完成最短需要多少时间?
  (2)如何缩短最短时间?
  答案:
  (1)
  因为所有部件可以同时制作,所以只要最长时间的「发动机」不制作完毕集中部件就无法举行。所以:「工程最短时间」就是通向汇点的和 最长的权重。(最长权重的路径也叫做「关键路径」)
  上图 开始 -> 发动机完成 -> 部件集中完成 -> 组装完成 就是最长权重,组装完成最短用时 6
  (2)
  关键路径性质:缩短关键路径上的时间就能缩短最短时间(但是缩短的同时关键路径会动态发生变化,好比发动机制作时间 <strong>                            }                                  etv[j] = max\{etv(i) + weight\}                     etv[j]=max{etv(i)+weight}
  通过「反向推导」求出 ltv「事件最晚发生时间」
                                         l                            t                            v                            [                            i                            ]                            =                            m                            a                            x                            {                            e                            t                            v                            (                            j                            )                            −                            w                            e                            i                            g                            h                            t                            <                            i                            ,                            j                            >                            }                                  ltv = max\{etv(j) - weight\}                     ltv=max{etv(j)−weight}
  通过 etv 求出 ete「活动最早发生时间」
活动最早发生时间等于                                         f                            r                            o                            m                                  from                     from(箭头开始方向的事件最早发动时间)
  通过 ltv 求出 lte「活动最晚发生时间」
活动最晚发生时间等于                                         t                            o                            −                            w                            e                            i                            g                            h                            t                                  to - weight                     to−weight(箭头竣事方向的事件发生时间 - 权重)
  通过 lte - ete 求出关键路径
</ul>
四、代码

示例如下图:

  1. public class CriticalPath {    /** 边 */    static class Edge{        /** 权重 */        int weight;        /** 出度指向的点 */        int toVertex;        Edge next;        public Edge(int weight, int toVertex, Edge next) {            this.weight = weight;            this.toVertex = toVertex;            this.next = next;        }    }    /** 极点 */    static class Vertex{        /** 入度 数量 */        int inNumber;        /** 极点信息 */       Integer data;        /** 第一条边 */        Edge firstEdge;        public Vertex(int inNumber, Integer data, Edge firstEdge) {            this.inNumber = inNumber;            this.data = data;            this.firstEdge = firstEdge;        }    }    static void criticalPath(List graph){        //极点数量        int length = graph.size();        //边数量        int numOfEdges = 0;        for (Vertex vertex : graph) {            Edge edge = vertex.firstEdge;            while (edge!=null){                numOfEdges ++;                edge = edge.next;            }        }        //事件最早发生时间        int[] etv = new int[length];        //事件最晚发生时间        int[] ltv = new int[length];        //活动最早发生时间        int[] ete = new int[numOfEdges];        //活动最晚发生时间        int[] lte = new int[numOfEdges];        //1. 通过拓扑排序求 etv 「事件最早发生时间」        //etvStack 用于储存拓扑排序后的顺序        Stack etvStack = new Stack();        //stack 用于拓扑排序        Stack stack = new Stack();        for (Vertex vertex : graph) {            if (vertex.inNumber == 0){                stack.push(vertex);            }        }        while (!stack.isEmpty()){            Vertex pop = stack.pop();            //储存拓扑排序后的布局            etvStack.push(pop);            //遍历出度            Edge edge = pop.firstEdge;            while (edge != null){                Vertex vertex = graph.get(edge.toVertex);                vertex.inNumber --;                if (vertex.inNumber == 0){                    stack.push(vertex);                }                //赋值更大的间隔给 etv                if (etv[pop.data] + edge.weight > etv[edge.toVertex]){                    etv[edge.toVertex] = etv[pop.data] + edge.weight;                }                edge = edge.next;            }        }        //2.通过 etv 反向推导求出 ltv「事件最晚发生时间」        System.out.println("====etv====");        for (int i = 0; i < etv.length; i++) {            System.out.print("V"+i +" = "+etv[i]+" ");        }        System.out.println();        //初始化 ltv        Integer endVertex = etvStack.peek().data;        for (int i = 0; i < ltv.length; i++) {            ltv[i] = etv[endVertex];        }        while (!etvStack.isEmpty()) {            Vertex pop = etvStack.pop();            Edge edge = pop.firstEdge;            while (edge != null) {                //赋值更小的间隔给 ltv                if (ltv[pop.data] > ltv[edge.toVertex] - edge.weight) {                    ltv[pop.data] = ltv[edge.toVertex] - edge.weight;                }                edge = edge.next;            }        }        System.out.println("====ltv====");        for (int i = 0; i < ltv.length; i++) {            System.out.print("V"+i +" = "+ltv[i]+" ");        }        System.out.println();        //3. 通过 etv 求 ete        int index = 0;        for (Vertex vertex : graph) {            Edge edge = vertex.firstEdge;            while (edge != null){                ete[index++] = etv[vertex.data];                edge = edge.next;            }        }        System.out.println("====ete====");        for (int i = 0; i < ete.length; i++) {            System.out.print("E"+i +" = "+ete[i]+" ");        }        System.out.println();        //4. 通过 ltv 求 lte        index = 0;        for (Vertex vertex : graph) {            Edge edge = vertex.firstEdge;            while (edge != null){                lte[index++] = ltv[edge.toVertex] - edge.weight;                edge = edge.next;            }        }        System.out.println("====lte====");        for (int i = 0; i < lte.length; i++) {            System.out.print("E"+i +" = "+lte[i]+" ");        }        System.out.println();        //5. 用 lte - ete 求关键路径         System.out.println("====关键路径====");        for (int i = 0; i < ete.length; i++) {            if (lte[i] - ete[i] == 0) {                System.out.print("E"+i+" ");            }        }        return ;    }    /** 测试 */    public static void main(String[] args) {        char[] vertices = new char[]{&#39;A&#39;,&#39;B&#39;,&#39;C&#39;,&#39;D&#39;,&#39;E&#39;,&#39;F&#39;,&#39;G&#39;};        Edge e3 = new Edge(2, 4, null);        Edge e2 = new Edge(1, 3, e3);        Edge e1 = new Edge(3, 2, e2);        Edge e0 = new Edge(2, 1, e1);        Edge e4 = new Edge(1, 5, null);        Edge e5 = new Edge(1, 5, null);        Edge e6 = new Edge(1, 5, null);        Edge e7 = new Edge(1, 5, null);        Edge e8 = new Edge(2, 6, null);        Vertex a = new Vertex(0, 0, e0);        Vertex b = new Vertex(1, 1, e4);        Vertex c = new Vertex(1, 2, e5);        Vertex d = new Vertex(1, 3, e6);        Vertex e = new Vertex(1, 4, e7);        Vertex f = new Vertex(4, 5, e8);        Vertex g = new Vertex(1, 6, null);        ArrayList graph = new ArrayList();        graph.add(a);        graph.add(b);        graph.add(c);        graph.add(d);        graph.add(e);        graph.add(f);        graph.add(g);        criticalPath(graph);    }}
复制代码
效果:
  1. ====etv====V0 = 0 V1 = 2 V2 = 3 V3 = 1 V4 = 2 V5 = 4 V6 = 6 ====ltv====V0 = 0 V1 = 3 V2 = 3 V3 = 3 V4 = 3 V5 = 4 V6 = 6 ====ete====E0 = 0 E1 = 0 E2 = 0 E3 = 0 E4 = 2 E5 = 3 E6 = 1 E7 = 2 E8 = 4 ====lte====E0 = 1 E1 = 0 E2 = 2 E3 = 1 E4 = 3 E5 = 3 E6 = 3 E7 = 3 E8 = 4 ====关键路径====E1 E5 E8
复制代码
来源:https://blog.csdn.net/jarvan5/article/details/112015112
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )