Bry*_*son 6 algorithm graph-theory dependency-management directed-acyclic-graphs
抽象术语的问题:
我有一个有向无环图(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 解决方案的核心中为真，因此在每个令人满意的分配中都为真。