例如

• 设S = {1,2,3,4}
• 有效子集U = {{1,2,3,4},{1,2},{3,4},{1,4},{2,3},{1},{4}}
• 当k = 1 时，有 1 个解 {1,2,3,4}
• 当k = 2 时，有 2 个解 {{{1,2}{3,4}},{{1,4}{2,3}}}
• 当k = 3 时，有 1 个解
• 当k >= 4 时无解

问题

在我的现实生活示例中，集合S有 500 个元素，U有 500,000 个子集。每个子集都有 1 到 8 个元素。使用线性程序，我发现最小精确覆盖的大小为 70。我正在寻找大小为 70 的所有覆盖。理论上，我可以循环线性程序，为现有解决方案添加约束，以便找到新的解决方案。我怀疑这会很慢。

我还尝试了 R 中修改的跳舞链接方法，如果深度大于k ，则带有停止点。这适用于较小的示例，但似乎会陷入更深入的搜索。我可以通过切换到 C++ 或使用更高级的数据结构（例如 ZDD）来添加一些改进。

任何替代方法的建议将不胜感激。

尝试线性优化

下面的代码是我如何使用线性规划找到最小覆盖范围

library(Rsymphony) …