抽象问题:
我有一个有向无环图(DAG)，它包含查询时排他的顶点子集(每个子集只有一个项目应该出现在查询结果中)。当我查询图结构时，我想获得从给定顶点流出的顶点集，而只从图中已知顶点的子集中选择单个项目。
具体问题:
我有一个DAG存储我的程序集(顶点)和它们的依赖关系(边)。给定一个程序集或一组程序集，我需要查询以获得所有涉及的程序集及其依赖项。困难的部分是每个程序集都有多个版本，并且只能将程序集的一个实例加载到进程中。给定程序集的依赖关系在程序集的不同版本之间变化。
这个问题或一组问题有一个名称吗?一个标准的算法，我可以研究找到一个解决方案?
可能的解决方案:
一个传递闭包似乎是一个很好的解决方案，但是从子集(汇编版本)中选择的项目将根据通过图的路径而改变，可能通过多个分支，所以你几乎需要跟踪通过图的路径来生成传递闭包。
一个图形数据库可能会有很大的帮助，但我们希望现在避免走这条路，除非我们绝对有必要。
我认为从给定选择流的顶点集看起来令人困惑，因为实际上存在潜在的优化或满意度问题:给定汇编a，您可以通过B1或B2或B3满足其依赖关系，然后每个这些选择都有自己的连锁后果。
如果我们把它看作一个逻辑满足问题，那么我们可以考虑这样一个问题，其中程序集只有两个版本，例如A1或A2。然后，诸如(a或b或不c)之类的条款将转化为需要A1或B1或C2的上层装配(可能间接通过X1, X2和X3)，而条款的结合将转化为需要所有上层装配的上层装配。所以我认为如果你能有效地解决一般问题你就能有效地解决3-SAT，然后P = NP。
奇怪的是，如果你没有限制，你只允许每种类型的一个组装(A1或A2或A3，但一次不止一个)，那么这个问题很容易转化为Horn子句(Knuth Vol 4 section 7.1.1 p 57)，其中可满足性问题可以有效地解决。要做到这一点，你要用自然变量的倒数，所以X1意味着A1不包括在内。然后，如果您将Horn子句版本视为一种放松问题的方式，通过忽略每个汇编最多只能支持一个版本的约束，您得到的是一种机制，它告诉您某些汇编版本A1 不能在解决方案中，因为X1 =非A1在Horn解决方案的核心中为真，因此在每个令人满意的分配中都为真。