算法来解决版本范围的依赖关系

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

这是satisfiability problem的变体。 osgi也必须处理这个问题。所以你可以看看osgi规范和/或实现，看看它们是如何解决它的。

Answer 2

此问题是经由来自3SAT以下还原NP难题。给定一个3CNF公式，对于每个变量，都有一个包含两个版本的组件，并且对于每个子句，都有一个包含三个版本的组件。我们想安装一个版本的“超级”组件，它取决于所有的子组件，但对版本不挑剔。对于每个子句，子句组件1取决于出现在子句中的第一个变量，如果文字是正数，则需要版本1，如果是负数，则为0。子句组件2取决于第二个变量等。我们可以安装超级组件，当且仅当公式是可满足的。

在这种减少的光，它是有道理的制定你的问题，因为constraint satisfaction。每个组件都是一个变量，其可能的值是该组件的版本，如果没有安装该组件，则加上“未安装”是一个选项。对于每个组件A的版本取决于组件B的版本，存在涉及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 =无，因为从不出现。既然B的选择是受限制的，那么我们可以推断B的依赖关系C等等。当没有更多的简化可以做时，我们必须猜测;一种策略是选择剩下最少版本的组件并递归尝试所有组件（回溯）。