12

我有一个依赖算法的问题，依赖类似于 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 的依赖冲突

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

由于不应该有很多数据，所以不要考虑性能。

提前致谢！

4

2 回答 2

12

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

鉴于这种减少，将您的问题表述为约束满足是有意义的. 每个组件都是一个变量，其可能的值是该组件的版本，如果没有安装该组件是一个选项，则加上“未安装”。对于每个版本依赖于组件 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 等。当没有更多的简化要做时，我们必须猜测；一种策略是选择剩余版本最少的组件并递归地尝试所有组件（回溯）。

于 2013-05-02T11:37:39.163 回答
1

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

于 2013-04-09T09:43:41.660 回答