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

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

现在，当我想安装版本 1 的组件 A 和版本 1 的组件 D 时，我想获得依赖项。因为它们都依赖于组件 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-hard 问题。给定一个 3CNF 公式，对于每个变量，都有一个具有两个版本的组件，对于每个子句，都有一个具有三个版本的组件。我们想安装一个“ super ”组件的一个版本，它依赖于所有的子句组件，但对版本不挑剔。对于每个子句，子句组件 1 取决于出现在子句中的第一个变量，如果文字为正则需要版本 1，如果为负则为 0。子句组件 2 取决于第二个变量等。当且仅当公式可满足时，我们才能安装 super 组件。

鉴于这种减少，将您的问题表述为 constraint satisfaction 是有意义的.每个组件都是一个变量，其可能的值是该组件的版本，如果没有安装该组件是一个选项，则加上“未安装”。对于版本依赖于组件 B 版本的每个组件 A，存在涉及 A 和 B 变量的约束，将版本选择限制在其域产品的特定子集中。对于第一个示例中的 A 和 B，这是 {(1, 1), (1, 2), (1, 3)}，因为 A 版本 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，因为 none 永远不会出现。现在 B 的选择受到限制，我们可以推断 B 的依赖 C 等。当没有更多的简化要做时，我们必须猜测；一种策略是选择剩余版本最少的组件并递归尝试所有这些组件(回溯)。