-1

我有一个依赖项列表（或者更好的是没有循环的 DAG）：

输入（例如）：

Item A depends on nothing
Item B depends on C, E
Item C depends on A
Item D depends on E
Item E depends on A

我正在寻找的是：“项目的最佳*并行顺序是什么？”

*最好的意思是：最大并发级别

结果（例如）：

[A], [E, C], [D, B]

最好的方法似乎是基于依赖关系获取订单的伪代码，但我想我错过了一个基本算法。

4

3 回答 3

1

这看起来很像https://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique和https://en.wikipedia.org/wiki/Critical_path_method

假设您希望以最大的并发级别尽快完成工作，一旦您组织好事情，使其花费的时间不超过关键路径，您就有了最好的解决方案 - 如果有您可以运行的并行任务的数量没有限制，您只需在所有依赖项完成后立即安排每个操作即可获得关键路径。

于 2011-07-21T04:13:58.177 回答
1

我不确定您是否真的想要您认为想要的那种答案。例如，在您的场景中，如果 D 和 E 比 C 快，您可能会在项目 C 之前完成项目 D，因此您获得的列表列表不一定能说明整个故事。

如果您必须实际实施这种工作流程，而不是提前预测工作流程，那么很容易做到最佳；每当一个任务完成时，只需扫描所有剩余的任务并并行启动任何满足依赖关系的任务。如果您想提前计算它，那么也许您想重新考虑结果的结构？

于 2011-07-20T21:35:00.657 回答
0 
  GetLists(tasks[1..m], depends[1..m])
   1. topological_sort(tasks)
   2. cumulative = set()
   3. lists = queue()
   4. i = 0
   5. while |cumulative| != m do
   6.    temp = set()
   7.    while depends[i] is a subset of cumulative do
   8.       temp = temp union {tasks[i]}
   9.       i = i + 1
  10.    cumulative = cumulative union temp
  11.    lists.enqueue(temp)

类似的东西可能会奏效。请注意，lynchpin 正在执行“拓扑排序”以确保您获得终止。另请注意，该算法仅适用于具有有效解决方案的输入集。如果没有解决方案，这将永远循环。很容易修复，但你可以处理。

一个例子：A 不依赖任何东西，B 和 C 依赖于 A，E 依赖于 A 和 C，D 依赖于 C 和 B。

  Topological sort: A, B, C, D, E.
  cumulative = {}
  lists = []
  i = 0
  |cumulative| = 0 < 5 so...
     temp = {}
     depends[A] = {} is a subset of {} so
        temp = {A}
        i = 1
     depends[B] = {A} is not a subset of {}, so break
     cumulative = {A}
     lists = [{A}]
  |cumulative| = 1 < 5 so...
     temp = {}
     depends[B] = {A} is a subset of {A}, so
        temp = {B}
        i = 2
     depends[C] = {A} is a subset of {A}, so
  ...

你明白了。

于 2011-07-20T21:51:58.060 回答