algorithm - 依赖解析算法

Question

我必须解决一个依赖问题。情况如下:

我有一个包列表及其相应的依赖项:

pkg1: []
pkg2: [pkg1]
pkg3: [pkg1, pkg2]
pkg4: [pkg1 | pkg 3]
pkg5: [pkg1 | pkg2 | pkg3]

注意“|”两个或多个依赖之间等价于“或”

我的目标是让每个包计算安装它所需的最小依赖集。

例如:

minimum_set(pkg)

应该返回

pkg1, pkg2

Answer 1

某种蛮力是不可避免的，因为即使是这个问题的非常有限的形式也是 NP 完全的。

具体来说，即使除其中一个包之外的所有包的依赖列表仅由 OR 连接的术语组成，我们也可以简单地减少 NP-complete Hitting Set问题。假设我们有一个 Hitting Set 的实例，X 是包含元素 x_1, ..., x_n 的基础集，S 是 X 的 k 个子集 S_1, ..., S_k 的集合，每个 i 都有 S_i\subseteq X，我们想要命中:然后对于基础集合 X 中的每个元素 x_i，制作一个没有依赖项的包 x_i，并且对于每个集合 S_j\subseteq X，制作一个包 s_j，它具有所有包 x_k\in S_j 作为其依赖项, 由 OR 运算符连接。最后再创建一个“根”包 r，它具有 k 个包 s_1, ..., s_k 作为其依赖项，由 AND 连接。现在，查找 minimum_set(r) 将为原始 HS 问题找到最小大小的命中集——这些是与选择安装的包 x_i 的子集相对应的基础集元素。因此，如果您能以某种方式在多项式时间内实现 minimum_set()，那么您就已经在多项式时间内解决了 Hitting Set 和所有其他 NP 完全问题。