在描述一组任务的有向无环图中,我需要找到所有可以并行处理的任务。该图没有循环且规模较小(约1000个节点,2000条边),性能不是主要问题。
带有所需结果的示例:
- [] 是一个组。必须在继续之前处理组中的所有任务。 - [x & y] 表示 x 和 y 可以并行处理(x 和 y 并行)。 - x -> y 表示 x 和 y 必须按顺序处理(x 在 y 之前)。
我不想实际执行图形,而是构建一个尽可能并行的数据结构,同时保持顺序。算法的术语和名称对我来说不是很熟悉,所以我很难在网上找到类似的问题/解决方案。
带有所需结果的示例:
- [] 是一个组。必须在继续之前处理组中的所有任务。 - [x & y] 表示 x 和 y 可以并行处理(x 和 y 并行)。 - x -> y 表示 x 和 y 必须按顺序处理(x 在 y 之前)。
1
a -> [b & c] -> c
2
[a & e] -> b -> c -> [d & f]
3
[ [a -> b] & [e -> f] ] -> [ [c -> d] & g ]
我不想实际执行图形,而是构建一个尽可能并行的数据结构,同时保持顺序。算法的术语和名称对我来说不是很熟悉,所以我很难在网上找到类似的问题/解决方案。
a -> [ [b -> c -> e] & [d -> f] ] -> g -> h
或者a -> [ b & [d -> f] ] -> [ [c -> e] & g ] -> h
这个想法是一个任务必须在所有依赖项都准备就绪后才能运行。任何时候,如果有多个任务可以运行,则它们会并发运行。由于有多种解决方案,因此这似乎更像是一个优化问题,而不是我之前意识到的那样。在这里,第一个解决方案略微更好,因为它允许c
在等待f
之前开始处理。 - Anttig
在第一个解决方案中等待c->e
,而c
在第二个解决方案中等待d->f
。因此,如果您绝对需要这种格式,则需要定义某些指标,使得一种解决方案比另一种更好。例如,违规数量或序列长度。或者您可以为问题提供更多约束条件,例如任务具有单位长度。 - rex123d->e
,这会使它更加复杂(你能提出建议吗?)。但是,是的:通过将其压缩到所需的输出,您将不得不添加比原始图表中更多的限制。在您提供的第一种解决方案中,您让g
等待e
,这与它无关。而在第二个解决方案中,您让c
等待f
...那么,在您认为不可接受之前,可以添加多少此类额外依赖项到问题中? - trincot