在n个集合中至少包含一个元素的最小集合 [英] Minimal set that have at least one element in n sets

问题描述

我正在解决算法问题并设法分解它.这是我遇到的子问题:

I'm solving an algorithmic problem and managed to decompose it. Here is the sub problem I have:

我有n个集合，比如说 {1,2}，{2,3}，{3,4} ，我需要找到最小的集合，每个集合中至少有一个元素这n个集合，这里的解决方案是: {2,3} .

I have n sets, let's say {1,2},{2,3},{3,4} I need to find the smallest set that have at least one element in every of these n sets, the solution here is: {2,3}.

这不是一个贪婪的问题，请考虑 {1}，{1,3}，{1,3,4}，{2,3,4}，{2,3}，{2} 解决方案是 {1,2} ，即使 3 的频率最高.

It's not a greedy problem, think about {1},{1,3},{1,3,4},{2,3,4},{2,3},{2} the solution is {1,2} even though 3 have the biggest frequency.

也许该算法也有一个通用名称，我尝试搜索但没有找到有用的东西.

Maybe there is also a common name for that algorithm, I tried to search but didn't manage to find anything useful.

推荐答案

这听起来像最低顶点覆盖问题，它是NP完全的.

This sounds like the minimum vertex cover problem, which is NP-complete.

让每个值都是一个顶点，并且如果两个顶点在某个位置的同一集合中共存，则它们是相邻的.通过这种构造，任何组中的任何元素都将与覆盖顶点之间的距离最大为1，因此，最小顶点覆盖将覆盖这些组.另一种思考的方式是，如果一组不包含覆盖顶点，则该构造中必须至少有一个不通过构造包含覆盖顶点的边.这与Cover属性相矛盾，但是，因此每个集合都将包含一个Cover顶点.

Let each of the values be a vertex and two vertices are adjacent if they coexist in the same set somewhere. By this construction, any element in any set will be at most distance 1 away from a cover vertex, therefore a minimum vertex cover will cover the sets. Another way to think about it, if a set does not contain a cover vertex, then there must be at least one edge in the set that doesn't include a cover vertex by construction. This contradicts the cover property, however, therefore every set will contain a cover vertex.

这篇关于在n个集合中至少包含一个元素的最小集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！