algorithm - 包含所有给定元素的最小数量的容器

Question

假设C指的是一组容器{c1,c2,c3....cn}，其中每个容器都包含一组有限的整数{i1,i2,i3...im}。此外，假设一个整数可能存在于多个容器中。给定一个有限的整数集 S {s1,s2,s3...sz}，找到 C 的最小子集的大小包含 S 中的所有整数。

请注意，可能有数千个容器，每个容器都有数百个整数。因此，暴力解决这个问题的速度很慢。

我尝试使用贪心算法解决问题。也就是每次我都选择集合S中整数个数最多的容器，但是都失败了!

任何人都可以为这个问题提出一个快速算法吗？

Answer 1

这是众所周知的set cover problem .是NP-hard — 事实上，它的决策版本是典型的 NP 完全问题之一，并且是 Karp's 1972 paper 中包含的 21 个问题之一。 - 因此没有有效的算法是已知的。除非您可以为问题确定一些特殊的额外结构，否则您将不得不对一个近似结果感到满意:即 C 的一个子集，其并集包含 S，但不一定是最小这样的 C 子集。

greedy algorithm这可能是您最好的选择:它找到的集合集合的大小不超过最小集合大小的 O(log |C|) 倍。

你说你无法让贪婪算法起作用。我认为这可能是因为您未能正确实现它。你这样描述你的算法:

each time I select the container with the largest number of integers in the set S

但通常的贪心算法的规则是在每个阶段选择集合 S 中整数数量最多的容器，目前没有在任何容器中选择。