算法来解决版本范围基于依赖 [英] algorithm to resolve version scope based dependency

问题描述

我有一个依赖的算法有问题，依赖类似于到Maven的依赖，但它是一个基于严格的版本范围。

I have a problem on a dependency algorithm, the dependency is similar to maven dependency, except it's strict version scope based.

例如：

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和ç

Now, I want to get dependencies when I want to install component A, version 1 and component D, version 1. Because they are all depend on component B,C so I need a correct algorithm to get correct version of B and C

进一步，我可能需要升级组件A和D.例如，现在我有以下新的版本：

Further more, I may need to upgrade component A and D. For example, now I have below new versions:

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和组件研发，版本2份B的依赖关系冲突

Now I need a algorithm to get the correct version of A and D which I can upgrade to and all their dependencies. One problem here is Component A, version 3 and Component D, version 2 has dependency conflict of component B

有现有的算法来解决这样的问题？或类似的（容易）的问题。你有什么建议吗？

Is there existing algorithm to resolve such problem? Or similar(easier) problem. Do you have any suggestion?

由于不应该有大量的数据，所以不考虑性能。

As there should not be lots of data, so don't consider the performance.

在此先感谢！

推荐答案

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

This problem is NP-hard via the following reduction from 3SAT. Given a 3CNF formula, for each variable, there is a component with two versions, and for each clause, there is a component with three versions. We would like to install one version of a "super" component, which depends on all of the clause components but is not picky about versions. For each clause, clause component 1 depends on the first variable to appear in the clause, with version 1 required if the literal is positive, and 0 if it's negative. Clause component 2 depends on the second variable, etc. We can install the super component if and only if the formula is satisfiable.

在本光减少，这是有道理的制定您的问题，约束满足。每个部件是一个变量，其可能的值是该组件的版本，再加上未安装，如果不具有安装的组件是一个选项。为与依赖于一个版本的组分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，则{（无，无），（无，1），（无，2），（无，3），（无，4），（无，5） （1，1），（1,2），（1,3），（2,3），（2,4），（2,5）}

In light of this reduction, it makes sense to formulate your problem as constraint satisfaction. Each component is a variable whose possible values are the versions of that component, plus "not installed" if not having that component installed is an option. For every component A with a version that depends on a version of component B, there is a constraint involving the variable for A and B, restricting the choices of versions to a particular subset of the product of their domains. For A and B in the first example, this is {(1, 1), (1, 2), (1, 3)}, since A version 1 depends on B versions 1~3. If version 2 of A were available as well, this constraint would be {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}. If we didn't have to install A or B, then {(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等推论当没有更多的简化，剩下的事情，我们必须猜测;一种策略是选择与左最少版本的组件和递归尝试所有这些（回溯）的

Since your instances are small, you probably want a complete backtracking search, possibly with constraint propagation. A common algorithm for constraint propagation is AC-3, which enforces arc consistency, namely, removing from consideration all versions that clearly won't work, based on what's been eliminated. For example, given the constraint {(1, 1), (1, 2), (1, 3)}, we can eliminate B = none, since none never appears. Now that the choices for B are restricted, we can make inferences about B's dependency C, etc. When there's no more simplification left to do, we have to guess; one strategy is to pick the component with the fewest versions left and recursively try all of them (backtracking).

这篇关于算法来解决版本范围基于依赖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！