07.AOE网和图的关键路径

2023-11-11 17:55:16

相关代码地址：https://gitee.com/gudongkun/datestruct

一、什么是AOE网

AOE(Activity on edge network) :在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网

AOE网中没有入边的顶点称为始点（或源点）；没有出边的点称为终点（或汇点）

二、AOE网的性质

只有再某顶点所代表的事件发生后，从该顶点出发的活动才能开始；
只有再进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

三、AOE网可以解决下列问题

完成整个工程至少需要多少时间
为缩短完成工程所需要的时间，应当加快哪些活动

四、关键活动

关键路径：耗时最长的活动，可能不只一条，所以最主要的是要找到，最不能耽误的活动称为关键活动

如果缩短某一条活动的时间，不能改变总体结束时间，活动就不是关键活动；如果缩短某条活动的时间，活动，就是关键活动。

五、求关键活动算法描述

1.关键活动的4个前导量

（1）事件A的最早发生时间event_early[B] ：event_early[B] = max{event_early[BeforeB]+len<BeforeB,B>}
（2）事件A的最迟发生时间event_latest[B]：event_latest[B] = min{event_latest[AfterB]-len<B,AfterB>}
（3）活动AB 的最早发生时间 activity_early ：activity_early[BC] = event_early[B]
（4）活动AB 的最迟发生时间 activity_latest : activity_latest[CD] = event_latest[D] - len[CD]

注：len<A,B>表示弧AB的长度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0eEvWXcE-1642157321022)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

(1) event_early分析

event ： A B C D E F G H I
event_early ： 0 6 4 5 7 7 16 14 18

从起点开始算，起点时间一定是0
之后的事件用前一个事件的时间推算如：
1. event_early[B] = max{event_early[A]+len<A,B>}
2. event_early[E] = max{event_early[B]+len<B,E> ，event_early[C]+len<C,E>}

（2）event_latest分析,依赖event_early

event ： A B C D E F G H I
event_early ： 0 6 4 5 7 7 16 14 18
event_latest： 0 6 6 8 7 10 16 14 18

从后往前计算，结束事件直接取event_early
用前一个事件的时间推算如：event_latest[B] = min{event_latest[C]-len<A,B>}
开始时间，必定是0

（3）activity_early 分析

活动BC 的最早开始时间应该等于时间B的最早开始时间因此有：activity_early[BC] = event_early[B]

event ： A B C D E F G H I
event_early ： 0 6 4 5 7 7 16 14 18
event_latest： 0 6 6 8 7 10 16 14 18

activity : AB AC AD BE CE DF EG EH FH GI HI
activity_early : 0 0 0 6 4 5 7 7 7 16 14

(4) activity_latest分析

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tybGS2Yh-1642157321023)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

activity_latest 要从前往后算

例如活动CD 的最晚开始时间要保证时间D的最迟时间不能拖后所有：activity_latest[CD] = event_latest[D] - len[CD]

event ： A B C D E F G H I
event_early ： 0 6 4 5 7 7 16 14 18
event_latest： 0 6 6 8 7 10 16 14 18

activity : AB AC AD BE CE DF EG EH FH GI HI
activity_early : 0 0 0 6 4 5 7 7 7 16 14
activity_latest: 0 2 3 6 6 8 7 11 10 16 14

关键活动：

最早开始时间和最晚开始时间是一样的称为关键活动。

activity : AB AC AD BE CE DF EG EH FH GI HI
activity_early : 0 0 0 6 4 5 7 7 7 16 14
activity_latest: 0 2 3 6 6 8 7 7 10 16 14

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9qtF4GUO-1642157321023)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

关键活动组成的路径叫关键路径

虽然会产生多条关键路径，但是多条关键路径的执行时间是一样的。

工程的总执行时间就是任意选其中一条关键路径的总执行时间。

六、动画演示

https://www.bilibili.com/video/BV1PW41187vc

七、代码实现

aoe.go

package aoe

import (
	"fmt"
	"gitee.com/gudongkun/datestruct/dataStructures/graph"
	"gitee.com/gudongkun/datestruct/dataStructures/linear"
)

func GetGraph() graph.DMGraph {
	g := graph.NewDMGraph()

	g.AddNode("A")
	g.AddNode("B")
	g.AddNode("C")
	g.AddNode("D")
	g.AddNode("E")
	g.AddNode("F")
	g.AddNode("G")
	g.AddNode("H")
	g.AddNode("I")

	g.AddEdge("A", "B", 6)
	g.AddEdge("A", "C", 4)
	g.AddEdge("A", "D", 5)
	g.AddEdge("B", "E", 1)
	g.AddEdge("C", "E", 1)
	g.AddEdge("E", "G", 9)
	g.AddEdge("E", "H", 7)
	g.AddEdge("G", "I", 2)
	g.AddEdge("H", "I", 4)
	g.AddEdge("D", "F", 2)
	g.AddEdge("F", "H", 4)

	return g
}

func AOEKeyEvents() []string {
	g := GetGraph()
	eventEarly := make(map[string]int)
	eventLatest := make(map[string]int)
	activeEarly := make(map[string]int)
	activeLatest := make(map[string]int)

	// 1. 求eventEarly
	indegrees := make(map[string]int)
	stack := linear.NewStack()

	for _, v := range g.Nodes {
		indegrees[v] = g.GetIndegree(v)
		if indegrees[v] == 0 {
			stack.Push(v)
			indegrees[v] = -1
			eventEarly[v] = 0
		}
	}

	for !stack.IsEmpty() {
		v, _ := stack.Pop()
		for _, edge := range g.GetEdgesByHead(v) {
			indegrees[edge.Tail]--
			if indegrees[edge.Tail] == 0 {
				stack.Push(edge.Tail)
				indegrees[edge.Tail] = -1
				for _, endEdge := range g.GetEdgesByTail(edge.Tail) {
					val, ok := eventEarly[edge.Tail]
					if !ok {
						eventEarly[edge.Tail] = eventEarly[endEdge.Head] + endEdge.Val
					} else {
						if val < eventEarly[endEdge.Head]+endEdge.Val {
							eventEarly[edge.Tail] = val
						}
					}
				}
			}
		}
	}

	// 2. 求eventLatest
	outdegrees := make(map[string]int)
	outstack := linear.NewStack()
	for _, v := range g.Nodes {
		outdegrees[v] = g.GetOutdegree(v)
		if outdegrees[v] == 0 {
			outstack.Push(v)
			outdegrees[v] = -1
			eventLatest[v] = eventEarly[v]
		}
	}

	for !outstack.IsEmpty() {
		v, _ := outstack.Pop()
		for _, edge := range g.GetEdgesByTail(v) {
			outdegrees[edge.Head]--
			if outdegrees[edge.Head] == 0 {
				outstack.Push(edge.Head)
				outdegrees[edge.Head] = -1
				for _, endEdge := range g.GetEdgesByHead(edge.Head) {
					val, ok := eventLatest[edge.Head]
					if !ok {
						eventLatest[edge.Head] = eventLatest[endEdge.Tail] - endEdge.Val
					} else {
						if val < eventLatest[endEdge.Tail]-endEdge.Val {
							eventLatest[edge.Head] = val
						}
					}
				}
			}
		}
	}

	// 3.求 activityEarly
	for _, v := range g.GetEdgeList() {
		activeEarly[v.Head+"-"+v.Tail] = eventEarly[v.Head]
	}
	// 4. 求activeLatest
	for _, v := range g.GetEdgeList() {
		activeLatest[v.Head+"-"+v.Tail] = eventLatest[v.Tail] - v.Val
	}
	// 5.关键活动
	var keyActivity []string
	for k,v := range activeEarly {
		if activeLatest[k] == v {
			keyActivity = append(keyActivity,k)
		}
	}

	fmt.Println(keyActivity)

	return keyActivity

}

aoe_test.go

package aoe

import "testing"

func TestAOEKeyEvents(t *testing.T) {
	list := AOEKeyEvents()

	if len(list) != 6 {
		t.Fail()
	}
}

添加了新方法的有向图 dmgraph.go

package graph

import (
	"errors"
)

const DMaxSize = 20
const DMaxNum = 99999

type DMGraph struct {
	Edges   [DMaxSize][DMaxSize]int
	EdgeNum int
	Nodes   []string
	Indexs  map[string]int
}

type DEdge struct {
	Head, Tail string
	Val        int
}

func NewDMGraph() DMGraph {
	var g DMGraph
	for k, v := range g.Edges {
		for kk, _ := range v {
			if k == kk {
				g.Edges[k][kk] = 0
			} else {
				g.Edges[k][kk] = DMaxNum
			}

		}
	}
	g.Indexs = make(map[string]int)
	return g

}

func (g *DMGraph) AddNode(nodeName string) error {
	if g.Indexs == nil {
		return errors.New("不是有效的图")
	}
	if _, ok := g.Indexs[nodeName]; ok {
		return errors.New("已经添加过此结点")
	}
	g.Indexs[nodeName] = len(g.Nodes)
	g.Nodes = append(g.Nodes, nodeName)
	return nil
}

func (g *DMGraph) AddEdge(Head, Tail string, val int) error {
	if _, ok := g.Indexs[Head]; !ok {
		return errors.New("结点不存在：" + Head)
	}
	if _, ok := g.Indexs[Tail]; !ok {
		return errors.New("结点不存在：" + Tail)
	}
	if g.Edges[g.Indexs[Head]][g.Indexs[Tail]] != DMaxNum {
		return errors.New("边已经存在")
	}

	g.Edges[g.Indexs[Head]][g.Indexs[Tail]] = val
	g.EdgeNum++
	return nil
}

func (g *DMGraph) GetEdgeList() []DEdge {
	var edgeList []DEdge

	for i := 0; i < len(g.Nodes); i++ {
		for j := 0; j < len(g.Nodes); j++ {
			if g.Edges[i][j] != DMaxNum && i != j {
				edgeList = append(
					edgeList,
					DEdge{Head: g.Nodes[i], Tail: g.Nodes[j], Val: g.Edges[i][j]},
				)
			}
		}
	}

	return edgeList
}

func (g *DMGraph) GetIndegree(ele string) int {
	tail, ok := g.Indexs[ele]
	if !ok {
		return -1 //点不存在
	}
	indegree := 0
	for i := 0; i < len(g.Nodes); i++ {
		if g.Edges[i][tail] != 0 && g.Edges[i][tail] != DMaxNum {
			indegree++
		}
	}
	return indegree
}

func (g *DMGraph) GetOutdegree(ele string) int {
	head, ok := g.Indexs[ele]
	if !ok {
		return -1 //点不存在
	}
	outdegree := 0
	for i := 0; i < len(g.Nodes); i++ {
		if g.Edges[head][i] != 0 && g.Edges[head][i] != DMaxNum {
			outdegree++
		}
	}
	return outdegree

}


func (g *DMGraph) GetEdgesByTail(ele string) []DEdge {
	var edgeList []DEdge
	tail, ok := g.Indexs[ele]
	if !ok {
		return nil
	}

	for i := 0; i < len(g.Nodes); i++ {
		if g.Edges[i][tail] != 0 && g.Edges[i][tail] != DMaxNum {
			edgeList = append(
				edgeList,
				DEdge{Head: g.Nodes[i], Tail: g.Nodes[tail], Val: g.Edges[i][tail]},
			)
		}
	}
	return edgeList
}

func (g *DMGraph) GetEdgesByHead(ele string) []DEdge {
	var edgeList []DEdge
	head, ok := g.Indexs[ele]
	if !ok {
		return nil
	}

	for i := 0; i < len(g.Nodes); i++ {
		if g.Edges[head][i] != 0 && g.Edges[head][i] != DMaxNum {
			edgeList = append(
				edgeList,
				DEdge{Head: g.Nodes[head], Tail: g.Nodes[i], Val: g.Edges[head][i]},
			)
		}
	}
	return edgeList
}

码农公寓

一、什么是AOE网

二、AOE网的性质

三、AOE网可以解决下列问题

四、关键活动

五、求关键活动算法描述

1.关键活动的4个前导量

(1) event_early分析

（2）event_latest分析,依赖event_early

（3）activity_early 分析

(4) activity_latest分析

关键活动：

六、动画演示

七、代码实现

相关文章