算法解析基于版本范围的依赖

Question

我在依赖算法上有一个问题,依赖类似于maven依赖,除了它是基于严格的版本范围.

例如:

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2

现在,我想在安装组件A,版本1和组件D,版本1时获得依赖关系.因为它们都依赖于组件B,C所以我需要一个正确的算法来获得正确的B和C版本

此外,我可能需要升级组件A和D.例如,现在我有以下新版本:

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4

现在我需要一个算法来获取正确的A和D版本,我可以升级到它们的所有依赖项.这里的一个问题是组件A,版本3和组件D,版本2具有组件B的依赖冲突

是否存在解决此类问题的算法？或类似(更容易)的问题.你有什么建议吗？

由于不应该有大量数据,所以不要考虑性能.

提前致谢!

Answer 1

通过3SAT的以下减少,这个问题是NP难的.给定3CNF公式,对于每个变量,有一个包含两个版本的组件,对于每个子句,都有一个包含三个版本的组件.我们想安装一个版本的"超级"组件,它取决于所有子句组件,但对版本并不挑剔.对于每个子句,子句组件1依赖于在子句中出现的第一个变量,如果文字是正数则需要版本1,如果是负数则需要0.子句组件2取决于第二个变量等.当且仅当公式可满足时,我们才能安装超级组件.

鉴于这种减少,将问题表述为约束满足是有意义的.每个组件都是一个变量,其可能的值是该组件的版本,如果没有安装该组件,则为"未安装"是一个选项.对于具有依赖于组件B的版本的版本的每个组件A,存在涉及A和B的变量的约束,将版本的选择限制为其域的产品的特定子集.对于第一个示例中的A和B,这是{(1,1),(1,2),(1,3)},因为版本1取决于B版本1~3.如果A的版本2也可用,则该约束将是{(1,1),(1,2),(1,3),(2,3),(2,4),(2,5) }.如果我们不必安装A或B,那么{(none,none),(none,1),(none,2),(none,3),(none,4),(none,5), (1,1),(1,2),(1,3),(2,3),(2,4),(2,5)}.

由于您的实例很小,您可能需要完整的回溯搜索,可能需要约束传播.约束传播的常见算法是AC-3,它强制执行弧一致性,即根据已消除的内容从考虑中删除明显不起作用的所有版本.例如,给定约束{(1,1),(1,2),(1,3)},我们可以消除B = none,因为没有出现.现在B的选择受到限制,我们可以推断B的依赖关系C等.当没有更多的简化要做时,我们必须猜测; 一种策略是选择剩下最少版本的组件并递归尝试所有这些(回溯).

Answer 2

这是可满足性问题的一个变体。osgi 也必须处理这个问题。因此，您可以查看 osgi 规范和/或实现，看看他们是如何解决这个问题的。