依赖解析算法

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

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

• 具有可比性的 ID
• 依赖关系（软件包列表以及每个软件包的一组可接受的版本）
• 冲突（软件包列表以及每个软件包的一组与该版本一起导致问题的版本）
• Provides（软件包列表以及每个软件包还提供/包含的一组版本）

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

我现在希望，根据可用包的列表和当前状态，能够获取包列表中每个包的版本，同时考虑给定的约束（依赖项、冲突的包、其他包提供的包）并且返回每个软件包的版本列表。循环依赖是可能的。

如果无法达到有效状态，则可以更改现有包的版本，但只有在必要时才应这样做。如果无法达到有效状态，则应提供尽可能多的原因信息（告诉用户“如果删除 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++），请随意提及）

这是 NP 困难的

一些坏消息：这个问题是 NP 困难的，所以除非 P=NP，否则没有算法可以有效地解决它的所有实例。我将通过展示如何在多项式时间内转换 NP 困难问题的任何给定实例来证明这一点3SAT http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability转换为适合问题输入的依赖图结构，以及如何将该问题的任何依赖解析算法的输出转换回原始 3SAT 问题的解决方案，同样是在多项式时间内。逻辑基本上是，如果有某种算法可以在多项式时间内解决依赖解析问题，那么它也可以在多项式时间内解决任何 3SAT 实例 - 由于计算机科学家花了数十年的时间寻找这样的算法，但没有找到一个，据信这是不可能的。

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

首先，让我们制定一个稍微宽松的依赖解析问题版本，其中我们假设尚未安装任何软件包。我们想要的是一种算法，给定一个“目标”包，要么返回一组要安装的包版本，(a) 包含目标包的某个版本，(b) 满足目标包中每个包的所有依赖性和冲突属性。设置，或者如果没有一组包版本可以工作，则返回“IMPOSSIBLE”。显然，如果这个问题是 NP 困难的，那么更普遍的问题也是 NP 困难的，其中我们还指定了一组不可更改的已安装的软件包版本。

构建实例

假设我们有一个包含 n 个子句和 k 个变量的 3SAT 实例。我们将为每个变量创建 2 个包：一个对应于文字 x_k，另一个对应于文字 !x_k。 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)、(!p, !q, r) 和 (p, !q, r)：前 3 个版本完全满足以下条件之一文字 p、!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 制作为在每个方向上都带有冲突子句的单独包，而是将它们制作为同一包的两个不同版本！