依赖解析算法
Algorithm for dependency resolution
我正在编写一个包管理器，为此我希望依赖项解析尽可能强大。
每个包都有一个版本列表，每个版本包含以下信息：
- 可比较的 ID
- Dependencies（包列表和每个包的一组可接受版本）
- 冲突（包列表和每个包的一组版本，这些版本会导致与此版本一起出现问题）
- 提供（一个包列表和每个包的一组版本，这个包也provides/contains）
对于当前状态，我有一个软件包列表及其当前版本。
我现在想，在给定可用包列表和当前状态的情况下，能够为包列表中的每个包获取一个版本，同时考虑给定的约束（依赖性、冲突包、提供的包由其他包）并获取每个包的版本列表。循环依赖是可能的。
如果无法达到有效状态，则可能会更改现有包的版本，但只有在必要时才应这样做。如果无法达到有效状态，应该提供尽可能多的原因信息（告诉用户 "it could work if you remove X" 等）。
如果可能，也应该可以 "lock" 将包升级到特定版本，在这种情况下，包的版本可能不会更改。
我要完成的工作与现有的包管理器已经在做的非常相似，不同之处在于不一定需要使用最新版本的包（大多数包管理器似乎都在做的假设） .
到目前为止，我唯一的想法是为相关包的所有可能版本构建一个包含所有可能状态的结构，然后删除无效状态。我真的希望这不是唯一的解决方案，因为它感觉非常 "brute force"-ish。在大约 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-hard
一些坏消息：这个问题是 NP 难的，所以除非 P=NP，否则没有算法可以有效地解决它的所有实例。我将通过展示如何在多项式时间内将 NP-hard 问题 3SAT 的任何给定实例转换为适合问题输入的依赖图结构，以及如何将任何依赖项的输出转换来证明这一点该问题的解决算法再次在多项式时间内回到原始 3SAT 问题的解决方案。逻辑基本上是，如果有某种算法可以在多项式时间内解决你的依赖关系解决问题，那么它也可以在多项式时间内解决任何 3SAT 实例——而且由于计算机科学家花了几十年的时间寻找这样的算法但没有找到，这被认为是不可能的。
我在下文中假设在任何时候最多只能安装一个版本的任何软件包。 （这相当于假设同一包的每对不同版本之间存在隐式冲突。）
首先，让我们制定一个稍微宽松的依赖项解决问题版本，其中我们假设没有安装任何包。我们想要的只是一个算法，给定一个 "target" 包，或者 returns 一组要安装的包版本，(a) 包含目标包的某个版本，并且 (b) 满足所有依赖性和冲突集合中每个包的属性，或者 returns "IMPOSSIBLE" 如果没有一组包版本将起作用。显然，如果这个问题是 NP-hard，那么更普遍的问题也是如此，我们还指定了一组已安装的包版本，这些版本不会被更改。
构建实例
假设我们有一个包含 n 个子句和 k 个变量的 3SAT 实例。我们将为每个变量创建 2 个包：一个对应于文字 x_k，一个对应于文字 !x_k。 x_k 包将与 !x_k 包发生冲突，反之亦然，确保包管理器最多安装这两个包中的一个。所有这些 "literal" 包都只有一个版本，没有依赖项。
对于每个子句，我们还将创建一个 "parent" 包，以及一个 "child" 包的 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), and (p, !q, r)：前三个版本正好满足其中一个文字 p、!q 或 r；接下来的 3 个版本恰好满足 2；最后一个满足所有 3.
最后，我们创建了一个"root"包，它有n个父子句包作为它的依赖。这将是我们要求包管理器安装的包。
如果我们 运行 包管理器在这组 2k + 8n + 1 个包版本上，要求它安装根包，它会 return "IMPOSSIBLE"，或者要安装的软件包版本列表。在前一种情况下，3SAT 问题是不可满足的。在后一种情况下，我们可以很容易地提取变量的值：如果安装了 x_k 的文字包，则将 x_k 设置为 true；如果安装了文字包 !x_k，请将 x_k 设置为 false。 （请注意，不会有任何没有安装任何文字包的变量：每个变量至少出现在一个子句中，每个子句产生 7 个子包版本，其中至少一个必须安装，并且将强制安装一个该变量的两个文字中的一个。）
连一些限制都很难
这个构造没有使用任何预安装的包或 "Provides" 信息，所以即使这些是不允许的，问题仍然是 NP-hard。更有趣的是，鉴于我们假设一次最多可以安装任何包的一个版本，即使我们不允许冲突，问题仍然是 NP-hard ：文字 x_k 和 !x_k 在每个方向上使用冲突子句分隔包，我们只是使它们成为同一包的两个不同版本！
我正在编写一个包管理器，为此我希望依赖项解析尽可能强大。
每个包都有一个版本列表，每个版本包含以下信息：
- 可比较的 ID
- Dependencies（包列表和每个包的一组可接受版本）
- 冲突（包列表和每个包的一组版本，这些版本会导致与此版本一起出现问题）
- 提供（一个包列表和每个包的一组版本，这个包也provides/contains）
对于当前状态，我有一个软件包列表及其当前版本。
我现在想，在给定可用包列表和当前状态的情况下，能够为包列表中的每个包获取一个版本，同时考虑给定的约束（依赖性、冲突包、提供的包由其他包）并获取每个包的版本列表。循环依赖是可能的。
如果无法达到有效状态，则可能会更改现有包的版本，但只有在必要时才应这样做。如果无法达到有效状态，应该提供尽可能多的原因信息（告诉用户 "it could work if you remove X" 等）。
如果可能，也应该可以 "lock" 将包升级到特定版本，在这种情况下，包的版本可能不会更改。
我要完成的工作与现有的包管理器已经在做的非常相似，不同之处在于不一定需要使用最新版本的包（大多数包管理器似乎都在做的假设） .
到目前为止，我唯一的想法是为相关包的所有可能版本构建一个包含所有可能状态的结构，然后删除无效状态。我真的希望这不是唯一的解决方案，因为它感觉非常 "brute force"-ish。在大约 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-hard
一些坏消息：这个问题是 NP 难的，所以除非 P=NP，否则没有算法可以有效地解决它的所有实例。我将通过展示如何在多项式时间内将 NP-hard 问题 3SAT 的任何给定实例转换为适合问题输入的依赖图结构，以及如何将任何依赖项的输出转换来证明这一点该问题的解决算法再次在多项式时间内回到原始 3SAT 问题的解决方案。逻辑基本上是，如果有某种算法可以在多项式时间内解决你的依赖关系解决问题，那么它也可以在多项式时间内解决任何 3SAT 实例——而且由于计算机科学家花了几十年的时间寻找这样的算法但没有找到，这被认为是不可能的。
我在下文中假设在任何时候最多只能安装一个版本的任何软件包。 （这相当于假设同一包的每对不同版本之间存在隐式冲突。）
首先，让我们制定一个稍微宽松的依赖项解决问题版本，其中我们假设没有安装任何包。我们想要的只是一个算法，给定一个 "target" 包，或者 returns 一组要安装的包版本，(a) 包含目标包的某个版本，并且 (b) 满足所有依赖性和冲突集合中每个包的属性，或者 returns "IMPOSSIBLE" 如果没有一组包版本将起作用。显然，如果这个问题是 NP-hard，那么更普遍的问题也是如此，我们还指定了一组已安装的包版本，这些版本不会被更改。
构建实例
假设我们有一个包含 n 个子句和 k 个变量的 3SAT 实例。我们将为每个变量创建 2 个包：一个对应于文字 x_k，一个对应于文字 !x_k。 x_k 包将与 !x_k 包发生冲突，反之亦然，确保包管理器最多安装这两个包中的一个。所有这些 "literal" 包都只有一个版本，没有依赖项。
对于每个子句，我们还将创建一个 "parent" 包，以及一个 "child" 包的 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), and (p, !q, r)：前三个版本正好满足其中一个文字 p、!q 或 r；接下来的 3 个版本恰好满足 2；最后一个满足所有 3.
最后，我们创建了一个"root"包，它有n个父子句包作为它的依赖。这将是我们要求包管理器安装的包。
如果我们 运行 包管理器在这组 2k + 8n + 1 个包版本上，要求它安装根包，它会 return "IMPOSSIBLE"，或者要安装的软件包版本列表。在前一种情况下，3SAT 问题是不可满足的。在后一种情况下，我们可以很容易地提取变量的值：如果安装了 x_k 的文字包，则将 x_k 设置为 true；如果安装了文字包 !x_k，请将 x_k 设置为 false。 （请注意，不会有任何没有安装任何文字包的变量：每个变量至少出现在一个子句中，每个子句产生 7 个子包版本，其中至少一个必须安装，并且将强制安装一个该变量的两个文字中的一个。）
连一些限制都很难
这个构造没有使用任何预安装的包或 "Provides" 信息，所以即使这些是不允许的，问题仍然是 NP-hard。更有趣的是，鉴于我们假设一次最多可以安装任何包的一个版本，即使我们不允许冲突，问题仍然是 NP-hard ：文字 x_k 和 !x_k 在每个方向上使用冲突子句分隔包，我们只是使它们成为同一包的两个不同版本！