找到最小的集合组来涵盖所有组合可能性

Question

我正在对组合算法进行一些练习,并试图弄清楚如何解决以下问题:

给定一组25位,设置(选择)15(不可置换和非有序):

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

现在,对于这些可能性中的每一种,构造一个矩阵,其中我将每个唯一的25位成员与所有其他25位成员交叉,其中在它之间的关系中必须存在至少11个公共设置位(仅一个,而不是零).

让我试着说明它代表二进制数据,所以第一个成员将是:

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×1的矩阵上交叉这些值,我必须共有15位.由于结果> = 11,因此它是"有用的"结果.

对于1 x 2,我们有14位通用,因此也是有效的结果.

对所有成员执行此操作,最后,跨越1 x 3.268.760应该导致5位共同,因为它<11它不是"有用".

我需要的是找出(通过数学或算法)最小数量的成员需要覆盖所有可能共有11位的成员.

换句话说,如果对所有其他成员进行测试,那么一组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

之后,有一个小的递归循环来计算给定公共位数的位.

编辑:正如在下面的评论中所承认的(@btilly)这里是关系的"分形"形象或链接到图像

对于小于10位的值,色标范围从红色(15位匹配)到绿色(11位匹配)到黑色.

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

Answer 1

这类问题非常难，你不应该指望能够找到确切的答案。

贪婪的解决方案应该产生“相当好的”答案。但是..如何贪心呢？

这个想法是始终选择下一个元素来匹配尽可能多的当前未匹配的可能性。不幸的是，有超过 300 万个可能的成员，您必须尝试与数百万个不匹配的成员进行匹配（请注意，您的下一个最佳猜测可能已经与候选集中的另一个成员匹配......），即使选择下一个元素也可能不可行。

所以我们必须贪婪地选择下一个元素。我们将选择每一位来最大化最终匹配所有当前未匹配元素的概率之和。

为此，我们需要一个二维查找表P，如果第一个成员中为 1 的第一个位在第二个成员中也为 1 P(n, m)，则两个随机成员将具有至少 11 位共同点的概率。这个包含 225 个概率的表应该预先计算。mn

该表可以使用以下规则轻松计算：

1. P(15, m)如果 则为 0 m < 11，否则为 1。

2. 为了n < 15：

   P(n, m) = P(n+1, m+1) * (15-m) / (25-n) + P(n+1, m) * (10-n+m) / (25-n)
   

现在让我们从几个彼此“非常远”的成员开始。我的建议是：

1. 前 15 位为 1，其余为 0。
2. 前 10 位为 0，其余为 1。
3. 前 8 位为 1，后 7 位为 1，其余为 0。
4. 位 1-4、9-12、16-23 为 1，其余为 0。

现在从您的宇宙（25 个选择 15）成员开始，消除所有与初始集合中的元素之一匹配的成员。

接下来我们进入算法的核心。

While there are unmatched members:
    Find the bit that appears in the most unmatched members (break ties randomly)
    Make that the first set bit of our candidate member for the group.
    While the candidate member has less than 15 set bits:
        Let p_best = 0, bit_best = 0;
        For each unset bit:
            Let p = 0
            For each unmatched member:
                p += P(n, m) where m = number of bits in common between
                             candidate member+this bit and the unmatched member
                             and n = bits in candidate member + 1
            If p_best < p:
                p_best = p
                bit_best = this unset bit
        Set bit_best as the next bit in our candidate member.
    Add the candidate member to our collection
    Remove all unmatched members that match this from unmatched members
The list of candidate members is our answer

我没有写过代码，因此我不知道这个算法会产生多好的答案。但假设它并不比你当前的更好，对于 77 个候选成员（我们作弊并从 4 个开始），你必须对不匹配的候选者进行 271 次传递（25 次找到第一位，24 次找到第二位，等等） 11 找到第 15 个，再加 1 个来删除匹配的成员）。那是 20867 个通行证。如果平均有 100 万个不匹配的成员，则相当于 200 亿次操作。

这不会很快。但在计算上应该是可行的。