-1

这不是家庭作业，而是我在研究过程中遇到的一个问题。我需要知道这个问题是否是 NP 难的。在第一种情况下，我需要一个近似算法，而在后一种情况下，我需要一个有效的算法，为我提供最佳解决方案。

非正式描述：

想象 p 个人使用一些 t 工具。每个人只使用几种工具，但不是全部。有人写下谁使用了哪个工具。问题：如何找到最大的一组人，每个人至少使用了 k 个其他人也使用的工具？【之前的问题描述：和大家一样的工具？】工具数量限制为t'

我对此问题进行了正式描述，这可能会有所帮助：

令 G=(P,T,E) 是一个二分图，其中 P 代表人的集合，T 代表工具的集合。如果该人使用该工具，则在 P 中的节点 p 和 T 中的节点 t 之间存在一条边。目标是找到满足以下条件的集合 P'，T'： 1) 从 P' 中的任何 p'，T' 中的任何 t' 都可以通过一条边到达。2）|P'|，即P'中的节点数最大。

一种低效的方法是获取每个子集 P' 并计算与 P' 中的 p' 相关联的每个 t' 的交集。不幸的是，此类子集的数量呈指数增长，计算很快变得难以处理。

非常感谢！

4

2 回答 2

1

要找到最大的一组人，每个人都使用与其他人相同的工具，您只需要按他们使用的工具集对人员进行分组。

换句话说：

  • 创建地图：从（一组工具）到（使用这组工具的人数）
  • 找到数量最多的工具集。

这绝对是多项式。

例如：

假设出工具集是{爪锤，卷尺，美工刀，水分计，凿子，水平仪，螺丝刀，钉组，滑动斜面，布局正方形}（来源）

我们将创建一个从位集（表示为字符串的整数）到整数（使用这组工具的人数）的映射。

现在，如果 Dan 的工具是 {Claw Hammer, Utility Knife, Sliding Bevel}，我们将添加到跟随我们的地图：

键：1010000010，值：1。

要添加另一个人，我们将首先计算密钥。如果 Dave 使用与 Dan 相同的工具，我们将获得相同的密钥，因此我们将增加计数：

键：1010000010，值：2。

--

  • 从一个人的工具列表构建一个位集是O(T)
  • 搜索映射中是否已经存在这样的键是O(log(P)∙T)（O(T)是比较两个长度为 T 的字符串的最坏情况。由于键已排序，因此可能要好得多。还有 O （log(P) 忽略了迭代构造）。
  • 增加计数是O(1)，或者 - 向地图添加新键是O(log(P))（实际上它更好，因为地图是迭代构建的）。

总而言之 - 您可以为O(P∙log²(P)∙T)中的所有人构建集合。同样，你可以做得更好，但这只是为了证明它是多项式的。

找到具有最高计数的键是 O(P) - 遍历包含 P 个较少键的地图。

于 2014-06-27T18:12:04.577 回答
1

绝对不是 NP - 难。我会建议一种贪婪的方法。只需找到编号最大的工具即可。使用它的人。假设最大的此类组使用 2 个工具 A 和 B，该数量永远不会大于 max（使用 A 或 B 的人数）。

于 2014-06-27T19:14:16.077 回答