依赖性解析算法 [英] Algorithm for dependency resolution

问题描述

我正在编写一个程序包管理器，为此，我希望依赖性解析尽可能强大。

I'm in the process of writing a package manager, and for that I want the dependency resolution to be as powerful as possible.

每个程序包都有一个列表版本，并且每个版本包含以下信息：

Each package has a list of versions, and each version contains the following information:

• 可比较的ID


• 依赖关系（软件包列表，每个软件包都有一组可接受的版本）


• 冲突（软件包列表，每个软件包都有一组与此版本一起引起问​​题的版本）


• 提供（软件包列表，对于每个软件包，此软件包还提供/包含的一组版本）

• A comparable ID
• Dependencies (a list of packages and for each package a set of acceptable versions)
• Conflicts (a list of packages and for each package a set of versions that cause issues together with this version)
• Provides (a list of packages and for each package a set of versions that this package also provides/contains)

对于当前状态，我列出了软件包及其当前版本。

For the current state I have a list of packages and their current versions.

我现在希望在给定可用软件包列表和当前状态的情况下，能够在考虑到给定约束的情况下获得软件包列表中每个软件包的版本（dependenc ，冲突的软件包，其他软件包提供的软件包）并获取每个软件包的版本列表。可能存在循环依赖项。

I now want to, given the list of available packages and the current state, be able to get a version for each package in a list of packages, taking the given constraints into account (dependencies, conflicting packages, packages provided by other packages) and get back a list of versions for each of these packages. Circular dependencies are possible.

如果无法达到有效状态，则可以更改现有软件包的版本，尽管只有在必要时才进行更改。如果不可能达到有效状态，则应提供足够的原因信息（告诉用户如果删除X，它可以工作等）。

If no valid state can be reached, the versions of the existing packages may be changed, though this should only be done if necessary. Should it not be possible to reach a valid state as much information to the reason should be available (to tell the user "it could work if you remove X" etc.).

如果可能的话，还应该可以将软件包锁定到特定版本，在这种情况下，可以不更改软件包的版本。

If possible it should also be possible to "lock" packages to a specific version, in which case the version of the package may NOT be changed.

我要完成的工作与现有软件包管理器已经完成的工作非常相似，不同之处在于不必使用最新版本的软件包（假设大多数软件包经理似乎是这样做的。）

What I'm trying to accomplish is very similar to what existing package managers already do, with the difference that not necessarily the latest version of a package needs to be used (an assumption which most package managers seem to do).

到目前为止，我唯一的想法是针对所涉及的软件包的所有可能版本构建所有可能状态的结构，然后删除无效状态。我真的希望这不是唯一的解决方案，因为它感觉像是蛮力般的。将大约500个可用软件包（每个版本包含大约100个版本）和安装大约150个软件包的时间保持在几秒钟之内（尽管越快越好）。

The only idea I have so far is building a structure of all possible states, for all possible versions of the packages in question, and then removing invalid states. I really hope this is not the only solution, since it feels very "brute force"-ish. Staying under a few seconds for ~500 available packages with ~100 versions each, and ~150 installed packages would be a good goal (though the faster the better).

I不相信这是一个特定于语言的问题，但是为了更好地说明它，下面是一些伪代码：

I don't believe this is a language-specific question, but to better illustrate it, here is a bit of pseudecode:

struct Version
    integer id
    list<Package, set<integer>> dependencies
    list<Package, set<integer>> conflicts
    list<Package, set<integer>> provides

struct Package
    string id
    list<Version> versions

struct State
    map<Package, Version> packages
    map<Package, boolean> isVersionLocked

State resolve(State initialState, list<Package> availablePackages, list<Package> newPackages)
{
    // do stuff here
}

（如果您应该有实际的代码或知道执行此操作的现有实现（使用任何语言，则首选C ++ ）随时提一下它）

(if you should have actual code or know about an existing implementation of something that does this (in any language, C++ preferred) feel free to mention it anyway)

推荐答案

这是NP难题

一些坏消息：这个问题是NP问题，所以除非P = NP，否则没有算法可以有效地解决所有问题。我将通过展示如何在多项式时间内转换NP难题的任何给定实例来证明这一点 3SAT 转换为适合您问题输入的依存关系图结构，以及如何在多项式时间内再次将对该问题的任何依存关系解析算法的输出转换回原始3SAT问题的解决方案。逻辑基本上是，如果有某种算法可以在多项式时间内解决您的依存关系解决问题，那么它也可以在多项式时间内解决任何3SAT实例-并且由于计算机科学家花了数十年的时间却一直在寻找这种算法，

It's NP-hard

Some bad news: This problem is NP-hard, so unless P=NP, there is no algorithm that can efficiently solve all instances of it. I'll prove this by showing how to convert, in polynomial time, any given instance of the NP-hard problem 3SAT into a dependency graph structure suitable for input to your problem, and how to turn the output of any dependency resolution algorithm on that problem back into a solution to the original 3SAT problem, again in polynomial time. The logic is basically that if there was some algorithm that could solve your dependency resolution problem in polynomial time, then it would also solve any 3SAT instance in polynomial time -- and since computer scientists have spent decades looking for such an algorithm without finding one, this is believed to be impossible.

我将在下文中假设最多可以随时安装任何软件包的一个版本。 （这等效于假定同一软件包的每对不同版本之间都存在隐式冲突。）

I'll assume in the following that at most one version of any package can be installed at any time. (This is equivalent to assuming that there are implicit conflicts between every pair of distinct versions of the same package.)

首先，让我们制定一个稍微宽松的依赖关系解决方案版本我们假设尚未安装任何软件包的问题。我们想要的是一种算法，给定一个目标程序包，或者返回一组要安装的程序包版本，其中（a）包括目标程序包的某个版本，并且（b）满足目标程序包中每个程序包的所有依赖性和冲突属性。设置，如果没有一组软件包版本将返回 IMPOSSIBLE。显然，如果此问题是NP困难的，那么更普遍的问题也是如此，在该问题中，我们还指定了一组已经安装的不更改的软件包版本。

First, let's formulate a slightly relaxed version of the dependency resolution problem in which we assume that no packages are already installed. All we want is an algorithm that, given a "target" package, either returns a set of package versions to install that (a) includes some version of the target package and (b) satisfies all dependency and conflict properties of every package in the set, or returns "IMPOSSIBLE" if no set of package versions will work. Clearly if this problem is NP-hard, then so is the more general problem in which we also specify a set of already-installed package versions that are not to be changed.

假设我们给一个3SAT实例，其中包含n个子句和k个变量。我们将为每个变量创建2个包：一个对应于字面量x_k，另一个对应于字面量！x_k。 x_k软件包将与！x_k软件包发生冲突，反之亦然，从而确保软件包管理器将最多安装这两个软件包之一。所有这些文字包都只有一个版本，没有依赖性。

Suppose we are given a 3SAT instance containing n clauses and k variables. We will create 2 packages for each variable: one corresponding to the literal x_k, and one corresponding to the literal !x_k. The x_k package will have a conflict with the !x_k package, and vice versa, ensuring that at most one of these two packages will ever be installed by the package manager. All of these "literal" packages will have just a single version, and no dependencies.

对于每个子句，我们还将创建一个父包和7个版本一个子包。每个父软件包将依赖于其子软件包的7个版本中的任何一个。子程序包对应于​​从3个项目中选择至少一个的方式，每个子程序包都对相应的文字程序包具有3个依赖性。例如，子句（p，！q，r）的子包版本将依赖于文字包（p，q，！r），（！p，！q，！r），（！p，q， r），（p，！q，！r），（p，q，r），（！p，！q，r）和（p，！q，r）：前三个版本恰好满足以下条件之一字面量p，！q或r;接下来的3个版本恰好满足2个；最后一个满足所有3。

For each clause we will also create a single "parent" package, and 7 versions of a "child" package. Each parent package will be dependent on any of the 7 versions of its child package. Child packages correspond to ways of choosing at least one item from a set of 3 items, and will each have 3 dependencies on the corresponding literal packages. For example, a clause (p, !q, r) will have child package versions having dependencies on the literal packages (p, q, !r), (!p, !q, !r), (!p, q, r), (p, !q, !r), (p, q, r), (!p, !q, r), and (p, !q, r): the first 3 versions satisfy exactly one of the literals p, !q or r; the next 3 versions satisfy exactly 2; and the last satisfies all 3.

最后，我们创建一个 root包，其中包含所有n个parent子句包作为其依赖项。这将是我们要求软件包管理器安装的软件包。

Finally, we create a "root" package, which has all of the n parent clause packages as its dependencies. This will be the package that we ask the package manager to install.

如果我们在这套2k + 8n + 1个软件包版本上运行软件包管理器，请安装根软件包，它将返回 IMPOSSIBLE或要安装的软件包版本列表。在前一种情况下，3SAT问题是无法满足的。在后一种情况下，我们可以轻松提取变量的值：如果已安装x_k的文字包，则将x_k设置为 true ;如果已安装文字包！x_k，请将x_k设置为 false 。 （请注意，没有安装任何文字包都不会有任何变量：每个变量至少出现在一个子句中，并且每个子句都产生7个子软件包版本，其中至少一个必须安装，并且将强制安装一个

If we run the package manager on this set of 2k + 8n + 1 package versions, asking it to install the root package, it will either return "IMPOSSIBLE", or a list of package versions to install. In the former case, the 3SAT problem is unsatisfiable. In the latter case, we can extract values for the variables easily: if the literal package for x_k was installed, set x_k to true; if the literal package !x_k was installed, set x_k to false. (Note that there won't be any variables with neither literal package installed: each variable appears in at least one clause, and each clause produces 7 child package versions, at least one of which must be installed, and which will force installation of one of the two literals for that variable.)

预先安装的程序包或提供信息的任何使用，因此即使不允许使用这些程序，问题仍然是NP难题。更有趣的是，假设我们一次最多可以安装任何软件包的一个版本，即使我们不允许发生冲突，问题仍然是NP困难的 ：而不是将字面量x_k和！x_k在各个方向上带有冲突子句的单独软件包，我们只使它们成为同一软件包的两个不同版本！

This construction doesn't make any use of pre-installed packages or "Provides" information, so the problem remains NP-hard even when those aren't permitted. More interestingly, given our assumption that at most one version of any package can be installed at a time, the problem remains NP-hard even if we don't permit conflicts: instead of making the literals x_k and !x_k separate packages with conflict clauses in each direction, we just make them two different versions of the same package!

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