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