一个集合的每个集合中至少出现一个所需的元素数

Question

我有一个 L 列表 l[i] 元素 e。我正在寻找一种算法，该算法可以找到元素的最小集合 S_min，使得 S_min 中至少有一个成员发生在每个 l.

我不仅想找到一个简单的算法来为我做这件事，而且想知道这类问题实际上被称为什么。我确定那里有东西

我已经实现了蛮力算法，首先将所有这些元素添加到 S_min 中，这些元素出现在 len(l[i] )=1。剩下的就是简单的试错。

Answer 1

您描述的问题是超图中的 vertex cover problem，这是一个优化问题，在一般情况下是 NP-hard，但允许适用于适当有界实例的近似算法。