代码之家 › 专栏 › 技术社区 › Jan Gary

依赖解析算法

dependency-management algorithm

Jan Gary · 技术社区 · 11 年前

我正在编写一个包管理器,为此,我希望依赖关系解析尽可能强大。

每个包都有一个版本列表,每个版本都包含以下信息:

可比ID
依赖关系 (软件包列表和每个软件包的一组可接受版本)
冲突 (软件包列表,以及每个软件包的一组与此版本一起导致问题的版本)
提供 (软件包列表以及每个软件包的一组版本,该软件包还提供/包含这些版本)

对于当前状态,我有一个包及其当前版本的列表。

我现在希望,在给定可用包列表和当前状态的情况下,能够获得包列表中每个包的版本,同时考虑到给定的约束(依赖关系、冲突包、其他包提供的包),并获得这些包中每个包版本的列表。循环依赖关系是可能的。

如果无法达到有效状态,则可能会更改现有包的版本,但这只应在必要时进行。如果无法达到有效状态,则应提供尽可能多的原因信息(告诉用户“如果删除X,它可能会工作”等)。

如果可能,还可以将包“锁定”到特定版本,在这种情况下,包的版本可能不会更改。

我试图完成的工作与现有的包管理器已经完成的工作非常相似,不同之处在于不一定需要使用包的最新版本(大多数包管理器似乎都这样做)。

到目前为止,我唯一的想法是为所讨论的包的所有可能版本构建一个包含所有可能状态的结构,然后删除无效状态。我真的希望这不是唯一的解决方案,因为它感觉很“蛮力”。在几秒钟内保持约500个可用包(每个包约100个版本)和约150个已安装包将是一个不错的目标(尽管速度越快越好)。

我不认为这是一个特定于语言的问题,但为了更好地说明这一点,这里有一些伪代码:

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++都是首选),请随意提及)

1 回复 | 直到 11 年前

j_random_hacker 11 年前

这是NP难

一些坏消息:这个问题是NP难的,所以除非P=NP,否则没有算法可以有效地解决它的所有实例。我将通过演示如何在多项式时间内转换NP难问题的任何给定实例来证明这一点 3SAT 以及如何将该问题的任何依赖性解决算法的输出转换为原始3SAT问题的解决方案,同样是在多项式时间内。逻辑基本上是,如果有某种算法可以在多项式时间内解决依赖性解决问题,那么它也可以在多项式内解决任何3SAT实例——由于计算机科学家花了几十年时间寻找这样的算法,但没有找到一个,这被认为是不可能的。

在下文中,我将假设任何时候最多可以安装一个版本的软件包。(这相当于假设同一包的每对不同版本之间存在隐式冲突。)

首先,让我们对依赖性解决问题制定一个稍微宽松的版本,假设没有安装任何包。我们需要的是一种算法,在给定“目标”包的情况下,要么返回一组要安装的包版本,(a)包括目标包的某个版本,(b)满足该组中每个包的所有依赖性和冲突属性,或者如果没有包版本集可以工作,则返回“IMPOSSIBLE”。显然,如果这个问题是NP难的,那么更一般的问题也是如此,在这个问题中,我们还指定了一组已安装的软件包版本,这些版本是不可更改的。

构造实例

假设我们得到一个包含n个子句和k个变量的3SAT实例。我们将为每个变量创建两个包:一个对应于文字x_k,另一个对应文字!x_。x_k包将与!x_k包,反之亦然,确保包管理器最多安装这两个包中的一个。所有这些“文字”包都只有一个版本,没有依赖关系。

对于每个子句,我们还将创建一个单独的“父”包和7个版本的“子”包。每个父包将依赖于其子包的7个版本中的任何一个。子包对应于从一组3个项中选择至少一个项的方式,并且每个子包对相应的文本包具有3个依赖项。例如,子句(p,!q,r)的子包版本将依赖于文字包(p,q,!r)、(!p,!q,!r,(!p、q,r,)、(p、!q、!r),(p、q、r)、!q或r;接下来的3个版本正好满足2个;最后一个满足所有3。

最后,我们创建了一个“根”包,它将所有n个父子句包作为其依赖项。这将是我们要求包管理器安装的包。

如果我们在这组2k+8n+1包版本上运行包管理器,要求它安装根包,它将返回“IMPOSSIBLE”或要安装的包版本列表。在前一种情况下,3SAT问题无法令人满意。在后一种情况下,我们可以很容易地提取变量的值:如果安装了x_k的文字包,请将x_k设置为 true ; 如果是文字包!x_k已安装,将x_k设置为 false 。(请注意,不会有任何变量安装了两个文本包:每个变量至少出现在一个子句中,每个子句生成7个子包版本,其中至少一个必须安装,这将强制安装该变量的两个文本之一。)

甚至有些限制也很难

这种构造不使用预先安装的软件包或“提供”信息,因此即使这些软件包不被允许,问题仍然是NP难题。更有趣的是,考虑到我们假设一次最多可以安装一个版本的任何软件包,问题仍然是NP难题 即使我们不允许冲突 :而不是使文字x_k和!x_k在每个方向上都有冲突子句的独立包,我们只是将它们作为同一个包的两个不同版本!