6

我们有集合S 1 , S 2 , ..., S n。这些集合不必是不相交的。我们的任务是为每个集合选择一个有代表性的成员，使得选择的元素总数尽可能少。一个元素可能存在于多个集合中，并且可以代表它所包含的所有集合。有没有一种算法可以有效地解决这个问题？

4

4 回答 4

8

重述后更容易回答这个问题：让原始集合S 1，S 2，...，S n是宇宙的元素，让原始集合成员本身是集合：T 1，T 2，... , T m（其中T i包含元素 { S j }，它们是包含相应成员的原始集合）。

现在我们必须用集合T 1 , T 2 , ..., T m覆盖全域S 1 , S 2 , ..., S n。这正是Set cover problem。这是一个众所周知的 NP 难题，因此没有算法可以有效地解决它（除非 P=NP，正如理论家通常所说的那样）。从维基百科页面可以看到，有一个贪心逼近算法；它是有效的，但近似比不是很好。

于 2013-03-09T10:14:06.543 回答
2

不是要窃取 Evgeny 的荣耀，但这里有一种相当直接的方式，可能更严格地表明，海报问题的一般情况是 NP 难的。

考虑最小顶点覆盖问题，即从简单图( V , E ) 中的顶点V中找到最小集合X ，其中 E 中的每条边都与X中的至少一个顶点相邻。

一条边可以由一个无序的二元素集合 { v a , v b } 表示，其中v a和v b是V中的不同元素。请注意，表示为 { v a , v b } 的边e与v c相邻当且仅当v c是 { v a , v b } 的元素。

因此，最小顶点覆盖问题与找到V的最小大小子集X相同，其中由E中的一条边定义的每个边集 { v a , v b }包含X中的元素。

如果一个人有一种算法可以有效地解决原始陈述的问题，那么一个人就有一种算法可以有效地解决上述问题，因此也可以有效地解决最小顶点覆盖问题。

于 2013-03-13T15:45:57.600 回答
2

我假设“有效地”是指多项式时间。

Evgeny Kluev 是正确的，问题是 NP-hard。它的决策版本被称为命中集问题，并且在引入该概念后不久就被证明是我们现在所说的 NP 完全问题。虽然 Evgeny 的归约确实是从命中集合问题到集合覆盖问题，但不难看出显式的逆归约。

给定一个集合 C={C 1 ,C 2 ,...C m }，它的并集是 U={u 1 ,u 2 ,...,u n }，我们想要找到一个最小基数子集 C'，它的union 也等于 U。将初始问题中的S i定义为 {C j in C | u i是 C j } 的一个元素。S={S 1 ,S 2 ,...,S n }的最小命中集等于我们想要的 C'。

于 2013-03-13T15:50:24.810 回答
1

如果您可以使用接近最佳的解决方案（它们可能会为您提供最佳解决方案，但不一定），可以查看一些算法是模拟退火和遗传算法。模拟退火可以用于生产电子 CAD 自动贴装（因为我是 Wintek 自动贴装程序开发团队的一员）。

于 2013-03-15T21:52:09.167 回答