依赖解析算法

Question

我正在编写包管理器,为此我希望依赖解析尽可能强大.

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

• 可比身份证
• 依赖关系(包列表以及每个包的一组可接受的版本)
• 冲突(包的列表以及每个包的一组导致与此版本一起出现问题的版本)
• 提供(包的列表以及每个包的一个版本,该包也提供/包含)

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

我现在想,在给定可用包列表和当前状态的情况下,能够在包列表中获取每个包的版本,考虑给定的约束(依赖性,冲突包,其他包提供的包)和获取每个软件包的版本列表.循环依赖是可能的.

如果无法达到有效状态,则可以更改现有软件包的版本,但这只应在必要时进行.如果无法获得有效状态,应尽可能多地获取原因信息(告诉用户"如果删除X则可以正常工作"等).

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

我想要完成的工作与现有的包管理器已经完成的工作非常相似,区别在于不一定需要使用最新版本的包(大多数包管理器似乎都在做的假设).

到目前为止,我唯一的想法是为所有可能版本的包构建所有可能状态的结构,然后删除无效状态.我真的希望这不是唯一的解决方案,因为它感觉非常"蛮力" - 非常.保持在几秒钟内可以获得~500个可用的包,每个包含约100个版本,并且~150个已安装的包将是一个很好的目标(尽管越快越好).

我不相信这是一个特定于语言的问题,但为了更好地说明它,这里有一些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++首选),请随时提及它)

Answer 1

这是NP难的

一些坏消息:这个问题是NP难的,所以除非P = NP,否则没有算法可以有效地解决它的所有实例.我将通过展示如何在多项式时间内将NP-hard问题3SAT的任何给定实例转换为适合于输入问题的依赖图结构以及如何将任何依赖性解析算法的输出转换为该问题来证明这一点.问题回到原始3SAT问题的解决方案,再次在多项式时间.逻辑基本上是,如果有一些算法可以解决多项式时间内的依赖性解决问题,那么它也可以在多项式时间内解决任何3SAT实例 - 并且由于计算机科学家花费数十年时间寻找这样的算法而没有找到一个,这被认为是不可能的.

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

首先,让我们制定一个略微放松的依赖解析问题版本,我们假设没有安装任何软件包.我们想要的是一个算法,给定一个"目标"包,或者返回一组包版本来安装(a)包括某个版本的目标包,以及(b)满足所有包的所有依赖和冲突属性.如果没有任何软件包版本可用,则设置或返回"IMPOSSIBLE".显然,如果这个问题是NP难的,那么更普遍的问题也是如此,我们还指定了一组已经安装的不需要更改的软件包版本.

构造实例

假设我们被赋予一个包含n个子句和k个变量的3SAT实例.我们将为每个变量创建2个包:一个对应于文字x_k,另一个对应于文字!x_k.x_k包与!x_k包有冲突,反之亦然,确保包管理器最多安装这两个包中的一个.所有这些"文字"包只有一个版本,没有依赖.

对于每个子句,我们还将创建一个"父"包和7个版本的"child"包.每个父包都将依赖于其子包的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):前3个版本恰好满足其中一个版本文字p,!q或r; 接下来的3个版本恰好满足2; 最后满足所有3.

最后,我们创建一个"root"包,它包含所有n个父子句包作为其依赖项.这将是我们要求包管理器安装的包.

如果我们在这组2k + 8n + 1软件包版本上运行软件包管理器,要求它安装根软件包,它将返回"IMPOSSIBLE"或要安装的软件包版本列表.在前一种情况下,3SAT问题是不可满足的.在后一种情况下,我们可以轻松地提取变量的值:如果安装了x_k的文字包,则将x_k设置为true; 如果安装了文字包!x_k,请将x_k设置为false.(请注意,没有任何变量既没有安装文字包:每个变量都出现在至少一个子句中,每个子句生成7个子包版本,其中至少有一个必须安装,并且会强制安装一个该变量的两个文字.)

甚至一些限制也很难

这种结构不会使用预先安装的软件包或"提供"信息,因此即使不允许这些问题,问题仍然是NP难的.更有趣的是,考虑到我们假设一次可以安装任何软件包的最多一个版本,即使我们不允许冲突,问题仍然是NP难的:而不是使文字x_k和!x_k分离具有冲突条款的包在每个方向,我们只是让它们成为同一个包的两个不同版本!