拓扑排序？不使用topsort

Question

我有一个名为activities.py的python列表

activities = [{'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 'Predecessors': None},
{'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 'Predecessors': ['Activity 1']},
{'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 'Predecessors': ['Activity 2', 'Activity 1']},
{'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 'Predecessors': ['Activity 2']},
{'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 'Predecessors': ['Activity 4']},
...

该列表代表一个由具有设定持续时间的活动组成的项目，并且还有一个“前序”键，指示在该活动开始之前必须完成哪些活动。该列表一直到活动 1001，但我刚刚包含了前 5 行。

我已经使用以下方法计算了所有活动的总时间：

def get_total_project_duration(activities: list) -> int:
    total_time = sum(item['Duration'] for item in activities)
    return total_time
    pass

但是，我想找出可能的最小“持续时间”，因为列表有一个“前辈”键，它允许多个活动同时启动，以尽可能减少时间。 我知道这可以使用拓扑排序来完成，但我想看看是否有一种方法可以仅使用默认库来完成同样的事情。

我已经尝试使用图表，但数据集太大，无法计算

Answer 1

您可以编写一个缓存的递归函数（例如使用

functools.cache

）来确定每个活动的最早可能结束时间，递归到前一个活动（如果有），并获取其中的

max

：

from functools import cache

act_dict = {a["Name"]: a for a in activities}

@cache
def earliest_finish(name):
    pred = max(map(earliest_finish, act_dict[name]["Predecessors"] or []), default=0)
    return pred + act_dict[name]["Duration"]

res = {a: earliest_finish(a) for a in act_dict}
print(res)
print(max(res.values()))

显示的五项活动的输出：

{'Activity 1': 5, 'Activity 2': 8, 'Activity 3': 23, 'Activity 4': 24, 'Activity 5': 44}
44

无论活动在列表中出现的顺序如何，这都有效。前驱根据需要计算，然后缓存。

Answer 2

我建议将您的活动存储在字典中，并以活动名称为键。然后，您可以循环遍历这些活动，根据之前计算的“完成”值向每个活动添加“完成”值（使用 FIFO 队列推迟前置活动不完整的活动）

输入：

activities = [{'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 'Predecessors': None},
{'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 'Predecessors': ['Activity 1']},
{'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 'Predecessors': ['Activity 2', 'Activity 1']},
{'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 'Predecessors': ['Activity 2']},
{'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 'Predecessors': ['Activity 4']} ]

流程：

from collections import deque

actDict = { act['Name']:act for act in activities }
links = deque(actDict.values())
while links:
    act   = links.popleft()
    preds = [ pred.get('Finish') for pred in
              map(actDict.get,act.get('Predecessors') or []) ]
    if None in preds:
        links.append(act)
    else:
        act['Finish'] = act['Duration'] + max(preds,default=0)

输出：

print(actDict)    

{'Activity 1':
   {'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 
    'Predecessors': None, 'Finish': 5},
 'Activity 2':
   {'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 
    'Predecessors': ['Activity 1'], 'Finish': 8},
 'Activity 3':
   {'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 
    'Predecessors': ['Activity 2', 'Activity 1'], 'Finish': 23},
 'Activity 4':
   {'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 
    'Predecessors': ['Activity 2'], 'Finish': 24},
 'Activity 5':
   {'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 
    'Predecessors': ['Activity 4'], 'Finish': 44}}