对于任何Linux Distro的打包系统,请查找可同时安装的程序包的最大数量

Question

有些软件包冲突,因此无法一次安装所有可用软件包.给定系统的可安装包的最大可能数量是多少？蛮力的试错方法是:

1. 列出每个可能的包名,即 dglob -a > list
2. 从中,制作slist1 slist2 slist3 ...每个可能的包组合的子列表.在我的系统上dglob -a | wc -l返回91327,这将需要一个不可行的大数 (1.467×10 ^ 27492)的文件.
3. apt-get install在每个列表上运行,以及rm那些产生冲突的列表.
4. 按行数对剩余列表进行排序,并显示最长的列表. wc -l slist* | head -n -1 | sort -g | tail -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

在这种情况下，暴力选项是唯一的选择。这里有一篇论文将深入描述原因，但问题是软件包安装和依赖/冲突解决是一个 NP 完全问题。

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

如果问题的有效解决方案可以适应 NP 中所有其他问题的有效解决方案，那么 Debian 软件包安装就是 NP 困难的。我将遵循上面列出的论文，因为在这里证明它有点复杂，但它可以编码为3-SAT。

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

default以下是APT 中的求解器尝试避免 NP 完备性的一些方法：

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

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

不幸的是，find the maximum possible number of installable packages for a given system几乎排除了我所知道的所有已知的易处理的类别。

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