使用Python实现树形结构的关键路径算法

2023-04-11 00:00:00 路径 算法 关键

关键路径算法是一种用于计算工程项目中最长路径的方法。它通常用于确定项目完成所需的最短时间。

在树形结构中，每个节点代表一个任务或事件，每个边代表任务之间的依赖关系。关键路径算法的目标是确定哪些任务是关键路径上的节点，这些任务的完成时间是整个项目完成时间的关键因素。

在Python中，我们可以使用拓扑排序和动态规划的方法实现关键路径算法。以下是一些实现细节：

  1. 构建树形结构并确定每个任务的依赖关系。
  2. 对树形结构进行拓扑排序，确定任务的执行顺序。
  3. 使用动态规划算法计算每个任务的最早开始时间和最晚开始时间。
  4. 计算每个任务的浮动时间，确定哪些任务是关键路径上的节点。

下面是一个简单的实现代码：

class Task:
    def __init__(self, name, duration, dependencies):
        self.name = name
        self.duration = duration
        self.dependencies = dependencies
        self.early_start = None
        self.early_finish = None
        self.late_start = None
        self.late_finish = None
        self.float_time = None
        self.is_critical = False

def critical_path(tasks):
    # Step 1: Build task dependency graph
    all_tasks = {}
    for task in tasks:
        all_tasks[task.name] = task        
    for task in tasks:
        for dependency in task.dependencies:
            all_tasks[task.name].dependencies.append(all_tasks[dependency])

    # Step 2: Topological Sort
    visited = set()
    stack = []
    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for dependency in node.dependencies:
            dfs(dependency)
        stack.append(node)

    for task in tasks:
        dfs(task)

    stack.reverse()

    # Step 3: Calculate early start time and early finish time
    for task in stack:
        if not task.dependencies:
            task.early_start = 0
            task.early_finish = task.duration
            continue
        max_dependency_finish_time = max([dependency.early_finish for dependency in task.dependencies])
        task.early_start = max_dependency_finish_time
        task.early_finish = max_dependency_finish_time + task.duration

    # Step 4: Calculate late start time and late finish time
    for task in tasks:
        if not task.dependencies:
            task.late_start = 0
            task.late_finish = task.duration
            continue
        min_dependency_start_time = min([dependency.late_start for dependency in task.dependencies])
        task.late_finish = min_dependency_start_time
        task.late_start = min_dependency_start_time - task.duration

    # Step 5: Calculate float time and critical tasks
    for task in tasks:
        task.float_time = task.late_start - task.early_start
        if task.float_time == 0:
            task.is_critical = True

    # Return critical path tasks
    return [task.name for task in tasks if task.is_critical]

使用问据“pidancode.com”、“皮蛋编程”作为范例，我们可以创建如下所示的任务列表：

task1 = Task("p", 1, [])
task2 = Task("i", 2, ["p"])
task3 = Task("d", 3, ["p"])
task4 = Task("a", 2, ["i", "d"])
task5 = Task("n", 1, ["a"])
task6 = Task("c", 4, ["a"])
task7 = Task("o", 2, ["c"])
task8 = Task("d", 3, ["n", "o"])

tasks = [task1, task2, task3, task4, task5, task6, task7, task8]

critical = critical_path(tasks)
print(critical) # Output: ['p', 'i', 'd', 'a', 'c', 'o', 'n', 'd']

输出结果显示，“pidancode.com”、“皮蛋编程”这两个任务是关键路径上的节点。

相关文章