图调度交集
Graph scheduling intersection
我需要计算工作流（有向无环图）中所有可能的交集。我试图找到有效的算法，但找不到。好像是并行调度理论。
例如我有图：
我不知道每个节点的执行时间，所以我需要找到所有的交叉点：
- 一个
- B C
- B E F
- B E G
- BG
- 乙H
- D C
- D E F
- D E G
- D G
- D H
- H
- 和其他可能的集合（评论后更新）
如何计算这个交点？
为了部分回答这个问题，对于问题中的问题，没有有效的算法（在 运行 时间范围的意义上，它在输入的编码长度中是多项式限制的）以下 class 个示例。
设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}，每个 i in {1,...,n} 的处理时间为 1 或 2； s 和 t 的处理时间无关紧要。这意味着潜在的每个任务组合 t_{i}，对于每个 i in {1,...,n}，可以同时 运行；然而，所有任务组合集合的基数 t_i（即 {t_1,...,t_n} 的 power set）是 2^n，它在 n 中不受多项式限制.
话虽这么说，也许通常的 'polynomial runtime bound' 概念在这里并不适用，因为输出的大小已经不是输入大小的多项式界限。
我需要计算工作流（有向无环图）中所有可能的交集。我试图找到有效的算法，但找不到。好像是并行调度理论。
例如我有图：
我不知道每个节点的执行时间，所以我需要找到所有的交叉点：
- 一个
- B C
- B E F
- B E G
- BG
- 乙H
- D C
- D E F
- D E G
- D G
- D H
- H
- 和其他可能的集合（评论后更新）
如何计算这个交点？
为了部分回答这个问题，对于问题中的问题，没有有效的算法（在 运行 时间范围的意义上，它在输入的编码长度中是多项式限制的）以下 class 个示例。
设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}，每个 i in {1,...,n} 的处理时间为 1 或 2； s 和 t 的处理时间无关紧要。这意味着潜在的每个任务组合 t_{i}，对于每个 i in {1,...,n}，可以同时 运行；然而，所有任务组合集合的基数 t_i（即 {t_1,...,t_n} 的 power set）是 2^n，它在 n 中不受多项式限制.
话虽这么说，也许通常的 'polynomial runtime bound' 概念在这里并不适用，因为输出的大小已经不是输入大小的多项式界限。