算法解决基于版本范围的依赖关系问题

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的依赖冲突。

是否存在解决这种问题的现有算法？或类似（更简单）的问题。您有任何建议吗？

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

提前感谢！

- Xilang

---

对于一个简单的解决方案，你可以使用拓扑排序吗？你可以开始构建一个图，其中每个节点都是{节点ID，版本号}。之后进行拓扑排序以获取依赖关系顺序。 - trequartista

谢谢，但在我的案例中，依赖项只需要解决一个组件版本，因此如果构建一个图形，对于具有相同节点ID的节点，输出列表必须仅输出一个节点; 对于某些节点，它们的版本可能会发生冲突，因此这样的节点可能永远不会出现在输出列表中。如何解决这个问题？ - Xilang

不好意思，我的意思是每个节点都有节点ID和版本ID。例如：{组件A，版本1}和{组件A，版本2}是不同的节点。因此，举个例子： - trequartista

例如：“组件A，版本1依赖于：组件B，版本1〜3;” 将翻译为 {Component A version 1} 和 {component B version 1}之间的边缘，{Component A version 1} 和 {component B version 2}之间的边缘，以及{Component A version 1} 和 {component B version 3}之间的边缘。您可以通过这种方式构建有向图，并进行拓扑排序（或其变体）以解决依赖项，从而给出{组件ID和版本号}作为父级。 - trequartista

一个好的系统依赖关系形成了一棵树（无环图），在这种情况下，如果您选择任何组件，您都有自己的依赖树。拓扑排序可以转化为受限数据结构，因此您将形成解决方案而不是尝试找到它。 - Khaled.K

Answer 1

以下是从3SAT中通过约简演变而来的NP难问题。对于给定的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等等。当没有更多的简化可以做时，我们必须猜测；一种策略是选择剩余版本最少的组件，并递归尝试所有这些版本（回溯）。

- David Eisenstat

Answer 2

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

- SpaceTrucker