5

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

给定一组 25 位，设置（选择）15（不可置换和顺序 NON 很重要）：

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 x 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 第一组的样本。

4

2 回答 2

1

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

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

计算最大覆盖率通常很难，但是有一个因子 (e/(e-1))-近似 (≈ 1.58) 算法：贪婪，听起来好像你可以快速实现（注意：你需要选择每次覆盖最未被发现的其他集合）。通过将贪心解乘以 e/(e-1)，我们获得了 k 个元素的最大覆盖范围的上限，这足以支持上一段中描述的下限。

警告：如果这个上限大于 [25 选择 15]，那么 k 太大了！

于 2012-04-09T22:44:56.297 回答
0

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

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

我们的想法是始终选择下一个元素来匹配当前无法匹配的尽可能多的可能性。不幸的是，有超过 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 亿次操作。

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

于 2012-04-09T20:02:10.677 回答