algorithm - 找到最小的集合组以涵盖所有组合可能性

Question

我正在做一些关于组合算法的练习，并试图弄清楚如何解决下面的问题:

给定一组 25 位，设置(选择)15(不可置换且顺序无关紧要):

n!/(k!(n-k)!) = 3.268.760

现在对于这些可能性中的每一种构造一个矩阵，我将每个唯一的 25 位成员与所有其他 25 位成员交叉，其中在它们之间的关系中，必须至少有 11 个公共(public)设置位(只有 1，没有 0)。

让我尝试将其表示为二进制数据，因此第一个成员将是:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits)
0000000001011111111111111 second member
0000000001101111111111111 third member
0000000001110111111111111 and so on....
...
1111111111111110000000000 up to here. The 3.268.760 member.

现在将这些值交叉到 1 x 1 的矩阵上，我必须有 15 位公共(public)位。由于结果 >= 11，这是一个“有用”的结果。

对于 1 x 2，我们有 14 位公共(public)位，因此也是一个有效结果。

对所有成员执行此操作，最后，跨越 1 x 3.268.760 应该导致 5 位通用，因为它 < 11 它不是“有用的”。

我需要找出(通过数学或算法)覆盖所有具有 11 位公共(public)位的可能性所需的最少成员数。

换句话说，如果针对所有其他成员进行测试，一组 N 个成员可能在整个 3.268.760 x 3.268.760 宇宙中至少有 11 个共同位。

使用强力算法，我发现使用 81 个 25 位成员可以实现此目的。但我猜这个数字应该更小(接近 12)。

我试图使用强力算法在 3.268.760 上做出 12 个成员的所有可能变体，但可能性的数量它是如此之大，以至于需要一百多年的时间才能计算出来(3,156x10e69 组合)。

我在谷歌上搜索过组合数学，但有太多领域我不知道这些问题应该属于哪个领域。

因此，非常感谢有关组合学领域的任何指导，或针对这些问题的任何算法。

PS:仅供引用。两个成员的“相似度”使用以下方法计算:

(Not(a xor b)) and a

之后有一个小的递归循环来计算给定公共(public)位数的位数。

编辑:正如下面评论所 promise 的 (@btilly)，这里是关系的“分形”图像 或 link to image

对于小于 10 位的值，色阶范围从红色(15 位匹配)到绿色(11 位匹配)到黑色。

此图像只是 4096 个第一组的样本。

Answer 1

tl;dr:你想解决 dominating set在一个大的、极其对称的图上。 btilly 是正确的，你不应该期待一个确切的答案。如果这是我的问题，我会尝试从贪心解决方案开始进行本地搜索。选择一组并尝试通过更改其他组来摆脱它。这需要数据结构来跟踪哪些集合恰好被覆盖一次。

编辑:好的，这里有一个更好的下限想法。对于从 1 到最优解的值的每个 k，都有一个下限 [25 选择 15] * k/[k 组的最大联合覆盖率]。你的边界 12(根据我的计算实际上是 10，因为你忘记了一些邻居)对应于 k = 1。证明草图:用 m 组修复一个任意解决方案并考虑 m 中的 k 可以获得的最大覆盖率。构建分数解，其中将所选 k 的所有对称性一起平均并缩放，以便每个元素都被覆盖一次。该解决方案的成本是 [25 选择 15] * k/[这 k 个集合的最大联合覆盖范围]，它至少与我们所追求的下限一样大。但是，它仍然至少与原始 m 集解一样小，因为每个集的边际 yield 都在减少。

计算最大覆盖率通常很难，但是有一个因子 (e/(e-1))-approximation (≈ 1.58) 算法:greedy，听起来好像你可以快速实现(注意:你需要选择每次覆盖最多未覆盖的其他集合的集合)。通过将贪心解乘以 e/(e-1)，我们得到了 k 个元素的最大覆盖范围的上限，这足以为上一段中描述的下限提供动力。

警告:如果这个上限大于[25选15]，那么k就太大了!