algorithm - 在 n 个集合中至少有一个元素的最小集合

Question

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

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

不是贪心问题，想想{1},{1,3},{1,3,4},{2,3,4},{2,3},{2}解决方案是 {1,2}尽管3频率最大。

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

Answer 1

这听起来像 minimum vertex cover problem , 这是 NP 完全的。

让每个值都是一个顶点，如果两个顶点共存于同一个集合中的某个地方，则它们是相邻的。通过这种构造，任何集合中的任何元素与覆盖顶点的距离最多为 1，因此最小顶点覆盖将覆盖集合。另一种思考方式，如果一个集合不包含覆盖顶点，则集合中必须至少有一条边不包含构造覆盖顶点。然而，这与覆盖属性相矛盾，因此每个集合都将包含一个覆盖顶点。