寻找大小为k的所有精确覆盖：大规模场景下的R语言求解方案问询

问题描述 #

给定集合S和有效子集集合U，需从U中找出所有恰好使用k个子集的S的精确覆盖。示例如下：

• 集合S = {1,2,3,4}
• 有效子集U = {{1,2,3,4},{1,2},{3,4},{1,4},{2,3},{1},{4}}
• k=1时，解为：{{1,2,3,4}}（共1种）
• k=2时，解为：{{{1,2},{3,4}}, {{1,4},{2,3}}}（共2种）
• k=3时，共1种解
• k≥4时，无解

实际场景与需求 #

实际应用中：

• 集合S包含500个元素
• U包含500,000个子集，每个子集的元素数量在1到8之间
• 已通过线性规划求得最小精确覆盖的大小为70，现需找出所有大小为70的精确覆盖

已尝试方法 #

• 线性规划循环：理论上可通过循环调用线性规划并添加已有解的约束来寻找新解，但推测该方法速度极慢，无法处理大规模数据。
• 改进版Dancing Links：在R语言中实现了添加深度限制（超过k则停止搜索）的版本，可处理小规模示例，但针对当前大规模数据进行深度搜索时出现严重卡顿。考虑过切换到C++实现或使用ZDD等高级数据结构优化，但希望获得其他替代方案。

线性规划实现代码 #

library(Rsymphony)

# mat为500×500,000的稀疏矩阵，元素均为1
dir <- rep("==", 500)
rhs <- rep(1, 500)
types <- rep("B", 500000)
score <- rep(-1, 500000)
max <- TRUE

soln <- Rsymphony_solve_LP(score, mat, dir, rhs, max = max, types = types)

可行思路征集 #

恳请提供针对该大规模场景的其他可行解决思路，优先考虑可在R语言环境中实现或集成的方案。

内容的提问来源于stack exchange，提问作者hinton888