对于任何 Linux 发行版的软件包管理系统，请找到最大可同时安装软件包数量。

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有数万个软件包。从debian-goodies软件包中使用dglob方便快捷地获取软件包计数：

# 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当然不是最大值，但一定存在一个最大值。

- agc

---

奇怪的是，对于这个问题，软件包的内容完全无关紧要。既然没有区别，那么如果您愿意，让我们假设存在一个Debian发行版，其中仅包含专门用于软件开发的Debian软件包子集。如何可行地找到最大数量的可安装软件包的问题将不会改变。（此外，请参见OP的第一行，其中以“注意：...”开头，预计并部分回答了您关于mp3播放器的问题。） - agc

将其视为一种图论和逻辑问题，将其映射到给定的软件包数据集上，并确定该问题是否可以使用手头的编程工具解决。这不是一个严格的Debian难题，它也可能出现在Red Hat .rpm文件、任何发行版的软件包系统或任何存在冲突软件包树的操作系统和平台上。在抽象层面上解决一个问题，就能够解决所有问题。或许需要澄清这个问题... - agc

正如你所说，这是一个逻辑和图论的普遍问题，你可能想在数学（或类似网站）上提出这个问题。 - umläute

只考虑冲突，你有一个NP完全最小顶点覆盖问题的实例。你想选择一个最小的软件包集合来不安装，其中包括每个冲突对的至少一个成员。如果您还考虑“依赖”关系，该问题将更加有趣：A与B冲突，但有10个软件包依赖于A，而7个软件包依赖于B，但也许消除这10个软件包也会解决其他一些冲突，而消除这7个则在其他地方没有太大收益... - user2404501

这很有道理...为了每个冲突对中的每个软件包构建完整的下游依赖项列表，并将这些列表的笛卡尔积形成一个更大的冲突列表。然后你就有了一个普通的最小顶点覆盖问题。但是，图形变得更大了，所以这可能不是最有效的方法。 - user2404501

Answer 1

在这种情况下，暴力破解是唯一的选择。这里有一篇论文，描述了为什么要这样做，但问题在于软件包安装和依赖/冲突解决是NP完全问题。

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

如果问题的有效解决方案可以适应NP中每个其他问题的有效解决方案，则Debian软件包安装是NP难的。我将参考上述论文，因为在此证明有点复杂，但它可以编码为3-SAT。

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

以下是APT中“默认”求解器避免NP完整性的一些方法：

• 使用启发式算法
• 首选或组中的第一个元素
• 严格的软件包版本约定
• 遇到主要冲突时放弃。

基本上，约束条件必须特别设计才能使问题落入已知可处理的 NP-完全问题类别之一，例如HORN-SAT。

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

因此，暴力搜索是唯一的选择，也是一种昂贵的选择，直到发现合适的可处理类别或有人证明 P=NP。

- gdahlm