linux - 对于任何 Linux Distro 的打包系统，找到可同时安装的包的最大数量

Question

一些包冲突，所以不可能一次安装所有可用的包。给定系统的可安装软件包的最大可能数量是多少？一种蛮力试错法是:

1. 列出所有可能的包名称，即 dglob -a > list
2. 由此，为每个可能的包创建子列表slist1 slist2 slist3 ... combination .在我的系统上 dglob -a | wc -l 返回 91327，这需要 unfeasibly large number files 的 (1.467×10^27492) .
3. 在每个列表上运行 apt-get install，rm 那些产生冲突的列表。
4. 按行数对剩余列表进行排序，并显示最长的一个。 wc -l slist* |头-n -1 |排序-g |尾部-1.

简单，但资源太重，所以也许有一些更可行的方法。

随之而来的是各种相关的问题，例如:

• 给定一个包 'foo'，如何找到不与 'foo' 冲突的可安装包的最大数量？

• 对于所有可能的包，哪个包的最大值最小(使其成为最“争吵”的包)？

(注意:该问题适用于 Debian、Red Hat 以及任何具有映射包冲突的打包系统的发行版或操作系统。任何适用平台的答案都是有效的。)

---

背景:

Debian 有数以万计的软件包。 dglob(来自 debian-goodies 包)对于快速计数很方便:

# show how many packages installed and available on the current system
echo $(dglob    | wc -l) packages installed of \
     $(dglob -a | wc -l) packages.

示例输出，(这两个数字可能会在更新和升级后定期波动，并且会因系统而异):

5107 packages installed of 91327 packages.

当然 5107 不是最大值，但必须有最大值。

Answer 1

在这种情况下，蛮力选项是唯一的选择。这是 a paper这将深入描述原因，但问题是包安装和依赖/冲突解决是一个 NP-Complete 问题。

如果每个 TRUE 答案都有一个易于检查的多项式大小的解释，则 NP 中就有问题。在这种情况下，这可以通过列出已安装的包和可用的包来完成。

如果问题的有效解决方案可以适用于 NP 中所有其他问题的有效解决方案，则 Debian 软件包安装属于 NP-hard。我将引用上面列出的论文，因为在这里证明它有点复杂，但它可以编码为 3-SAT .

由于 Debian 软件包安装是 NP 和 NP-hard，因此它是 NP-complete。

以下是 APT 中的 default 求解器试图避免 NP 完全性的一些方法:

• 使用启发式
• 对 or 组中第一个元素的偏好
• 严格的包版本约定
• 遇到重大冲突就放弃。

基本上，必须专门设计约束以使问题落入已知的易处理类别中，以解决 NP 完全问题，例如 HORN-SAT。

不幸的是，找到给定系统的最大可能安装包数量几乎排除了我所知道的所有已知的易处理类。

因此，在发现合适的易处理类或有人证明 P=NP 之前，蛮力是唯一的选择，也是一种昂贵的选择。