algorithm - 图调度交集

Question

我需要计算工作流(有向无环图)中所有可能的交叉点。我试图找到有效的算法，但找不到。看起来像是并行调度理论。

例如我有图表:

我不知道每个节点的执行时间，所以我需要找到所有的交叉点:

1. 一个
2. BC
3. B E F
4. B E G
5. BG
6. BH
7. D C
8. D E F
9. 德格
10. DG
11. DH
12. H
13. 和其他可能的集合(评论后更新)

我如何计算这个交叉点？

Answer 1

为了部分回答问题，对于问题中的问题，以下类示例没有有效的算法(在运行时限制的意义上，它在输入的编码长度中有多项式限制)。

令n 为非负整数。创建一个任务有向图 G=(V,E) 与 n+2 节点如下。令s为构成第一层的源节点，令t_1,...,t_n为第二层的n个中间节点，以及设 t 为第三层的终端节点，即

V := { s } union { t_i : i in { 1,...,n } } union { t }

并将第一层连接到第二层，将第二层连接到第三层，即

E := { ( s, t_i ) : i in { 1,...,n } } union { ( t_i, t ) : { 1,...,n } }

这直观地意味着源连接到所有任务，所有任务都连接到终端。假设所有任务 t_{i}，对于 {1,...,n} 中的每个 i，处理时间为 1 或 2； s 和 t 的处理时间无关紧要。这意味着对于 {1,...,n} 中的每个 i，潜在的任务 t_{i} 的每个组合都可以同时运行；然而，任务 t_i 的所有组合集合的基数(即 {t_1,...,t_n} 的 power set)是 2^ n，它在 n 中不是多项式有界的。

话虽如此，“多项式运行时界限”的通常概念可能不适用于此处，因为输出的大小已经不是输入大小的多项式界限。