算法：如何找到最少的标签以涵盖所有项？

Question

我认为这可能是NP完全问题，但还是问一下。贪心算法在我的脑海中似乎不起作用。

给定一组具有1个或多个标签的项目，我想找到覆盖所有项目的最小标签集。

编辑：请参见此处的“解决方案”。

- mpen

---

仅供参考，朴素算法为n*2^k。只需迭代标签的幂集并检查每个已标记项是否被当前集合覆盖即可。其中n是已标记项的数量，k是标签的数量。 - aaronasterling

所以......给定1000个项目和3000个标签......我要考虑1.2e906个操作......也就是说，无法解决......那个计划就此作罢。 - mpen

@Mark，获取最优解的最朴素方法是n*2^k。不过我不确定是否有更好的方法。如果你只想要一个近似解，那么它可能可以大大改进。 - aaronasterling

@Mark：如果你知道某些标签/子集比其他标签/子集更大，那么你可以贪心地尝试先使用这些标签/子集的解决方案，并跳过必须由比已知最佳解决方案更多的集合组成的未尝试的解决方案。这一切都与修剪有关，取决于标签的分布，可能很容易快速解决。但要注意如何对条件剩余集合的子集进行排名。交集操作需要快速执行。 - Potatoswatter

@Mark - 听起来很轻率，但如果你有一种快速的方法来知道哪个集合是正确的添加方法，你就不需要一个近似算法。无论如何，选择使用正确的近似方法将在很大程度上取决于实际应用中集合成员和集合大小的分布情况。 - Jonathan Dursi

Answer 1

这是集合覆盖问题，它是NP完全问题。每个标签定义了你的物品清单的一个子集，你希望找到最少数量的子集（标签），其并集等于完整的物品清单。

- Jim Lewis

---

知道它会有一个名字...只是不知道它被称为什么。现在我可以进一步调查了，谢谢 :) - mpen