哈尔滨电子网站建设,郑州百度搜索优化,网站每年续费给谁,长沙电商网站制作关键路径算法#xff08;Critical Path Method#xff0c;简称CPM#xff09;是一种用于项目管理的技术#xff0c;主要用于计算项目中的关键路径和关键活动。关键路径是指项目中的最长路径#xff0c;决定了项目的最短完成时间。关键活动是指在关键路径上的活动#xff…关键路径算法Critical Path Method简称CPM是一种用于项目管理的技术主要用于计算项目中的关键路径和关键活动。关键路径是指项目中的最长路径决定了项目的最短完成时间。关键活动是指在关键路径上的活动必须按时完成才能确保项目按计划完成。
关键路径算法通常包含如下步骤一是确定项目的所有活动和它们之间的先后关系建立活动网络图。需要注意的是活动网络图必须是有向无环图。二是计算每个活动的最早开始时间和最晚结束时间。三是根据活动的持续时间和先后关系计算活动的总浮动时间和自由浮动时间。四是根据活动的最早开始时间和最迟开始时间确定关键路径和关键活动计算项目的总时间。
以下是用go语言实现的关键路径算法
首先定义任务结构体
type Task struct {id string // 任务IDduration int // 任务持续时间dependencies []*Task // 前置任务列表successors []*Task // 后继任务列表earliestStart int // 最早开始时间latestStart int // 最晚开始时间
}
其次是对当前任务序列进行拓扑排序并检查是否是有向无环图。
func topologicalSort(tasks []*Task) ([]*Task,bool) {n : len(tasks)visited : make(map[*Task]int) //记录每个任务的访问状态0表示没有访问过1表示已经访问过了2表示访问完成order : make([]*Task,n) //排序结果
index : n - 1cycle : falsevar dfs func(node *Task) //遍历函数dfs func(node *Task) {visited[node] 1for _, neighbor : range node.successors {if visited[neighbor] 0 {dfs(neighbor)} else if visited[neighbor] 1 {cycle truereturn}}visited[node] 2order[index] nodeindex--}
for _,task : range tasks {if visited[task] 0 {dfs(task)if cycle {return nil, false}}}
return order, true
}
排序函数将一组活动列表作为参数传入然后递归遍历所有活动结点将排序结果作为第一个返回值返回第二个返回值为布尔类型true表示是有向无环图false表示当前活动网络图有环。
然后计算每个活动的最早开始时间和最晚开始时间
func (s *Schedule)calculateEarlyStart(task *Task) int {// -1为默认值如果最早开始时间不为-1表示已经设置过最早开始时间了if task.earliestStart ! -1 {return task.earliestStart}maxEarlyStart : 0//计算所有前置任务的最晚结束时间for _, predecessor : range task.dependencies {earlyStart : s.calculateEarlyStart(predecessor) predecessor.durationif earlyStart maxEarlyStart {maxEarlyStart earlyStart}}//前置任务的的最晚结束时间即当前活动的最早开始时间task.earliestStart maxEarlyStartreturn maxEarlyStart
}
func (s *Schedule)calculateLateStart(task *Task,projectDuration int) int {if task.latestStart ! -1 {return task.latestStart}//如果当前活动没有后置任务当前任务的最晚开始时间设置为项目结束时间减去当前任务的持续时间if len(task.successors) 0 {task.latestStart projectDuration - task.durationreturn task.latestStart}//计算后置任务的最早开始时间minLateStart : projectDurationfor _,successor : range task.successors {lateStart : s.calculateLateStart(successor, projectDuration) - task.durationif lateStart minLateStart {minLateStart lateStart}}task.latestStart minLateStartreturn minLateStart
}
计算完每个任务的最早开始时间和最晚开始减后根据关键活动的定义找出关键路径。
func (s *Schedule)CriticalPath() ([]*Task,int) {criticalPath : make([]*Task,0)projectDuration : 0// 计算任务的最早开始时间,确定项目的最早结束时间for _,task : range s.tasks {task.earliestStart -1task.latestStart -1earlyStart : s.calculateEarlyStart(task)if earlyStart task.duration projectDuration {projectDuration earlyStart task.duration}}// 计算任务的最晚开始时间如果任务的最早开始时间等于最晚开始时间则为关键活动for _,task : range s.tasks {s.calculateLateStart(task, projectDuration)if task.earliestStart task.latestStart {criticalPath append(criticalPath, task)}}return criticalPath,projectDuration
}
以上就是用golang实现的关键路径算法Schedule是项目排期结构体由项目的活动序列组成。关键路径算法可以帮助项目管理者合理安排项目计划和资源分配以确保项目按计划完成并能及时发现和解决可能导致项目延误的问题。它被广泛应用于建筑、制造、软件开发等众多行业中。
