解决基于版本范围依赖的算法 [英] 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 和C

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 和组件 D，版本 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-hard，通过 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，那么 {(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 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 = none，因为 none 永远不会出现.现在 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屋！