algorithm - 寻找最小集合覆盖的最快算法

Question

找到最小集合覆盖的最省时和正确的算法是什么？我不需要代码本身。我想要一个关于它是如何工作的解释或伪代码。
例如，我们有

Set S = {1,2,3,..,12}

Subsets S1 = {1,2,3,4,5,6}, S2 = {5,6,7,8,9}, S3 = {1,4,7,10}, S4={2,5,7,8,11}

S5 = {3,6,9,12}, S6 = {10,11}

最小设置封面为 S3 U S4 U S5。提前致谢！

Answer 1

如评论中所述，设置封面是 NP 难的。我相信，对于“自然”实例，实践中最好的精确方法是基于整数编程。编写一个好的整数程序求解器需要相当多的技巧，因此您可能只想使用求解器库。