8

我在一个表中存储了大约 2M 条记录。每条记录都有一个数字和大约 5K 个布尔属性。

所以桌子看起来像这样。

3, T, F, T, F, T, T, ...
29, F, F, T, F, T, T, ...
...
-87, T, F, T, F, T, T, ...
98, F, F, T, F, F, T, ...

我定义SUM(A, B)为 Ath 和 Bth 属性为真的数字的总和。例如，从上面的示例数据来看：SUM(1, 3) = 3 + ... + (-87)因为第 1 和第 3 个属性是 T 代表 3 和 -87

3, (T), F, (T), F, T, T, ...
29, (F), F, (T), F, T, T, ...
...
-87, (T), F, (T), F, T, T, ...
98, (F), F, (T), F, F, T, ...

并且SUM()可以采用任意数量的参数：SUM(1)并且SUM(5, 7, ..., 3455)都是可能的。

是否有一些智能算法可以找到可以产生最大结果的属性L列表SUM(L)？显然，暴力破解对于这个大数据集是不可行的。

如果有一种方法不仅可以找到最大值而且可以找到前 N 个列表，那就太棒了。

编辑 似乎没有蛮力就不可能找到答案。如果我改变问题以找到一个“好的估计”，会有一个好的方法吗？或者，如果我说 L 的基数固定为 10 左右，有没有办法计算 L？我会很高兴的。

4

4 回答 4

11

不幸的是，这个问题是NP-complete。您的选择仅限于使用近似算法找到一个好的但非最大的解决方案，或者使用分支定界并希望您不会达到指数运行时间。

NP 完备性的证明

为了证明您的问题是 NP 完全的，我们将集合覆盖问题简化为您的问题。假设我们有一组U元素N和一组S的M子集U，其中所有集合的并集S是U。集合覆盖问题要求这样的最小子集T，S使得 的每个元素U都包含在 的元素中T。如果我们有一个多项式时间算法来解决您的问题，我们可以解决集合覆盖问题，如下所示：

首先，构造一个包含M+N行和M属性的表。第一N行是“元素”行，每​​行对应于 的一个元素U。这些具有“足够负”的价值；-M-1应该足够了。对于元素 row i，j如果对应的元素不在jth 集合中，则 th 属性为真S。

最后M一行是“设置”行，每行对应于S. 这些都是有价值1的。对于 set row N+i，ith 属性为假，其他所有属性为真。

元素行的值足够小，以至于排除所有元素行的任何属性选择都优于任何包含任何元素行的属性选择。S由于is中所有集合的并集，因此U选择所有属性会排除所有元素行，因此属性的最佳选择是包含最多集合行而不包含任何元素行的属性。通过表的构造，如果相应集合的并集为U，则属性选择将排除所有元素行，如果是，则包含的属性越少，其得分越高。因此，属性的最佳选择直接对应于 的最小覆盖S。

如果我们有一个好的算法来选择产生最大和的属性，我们可以将它应用于这个表来生成任意的最小覆盖S。因此，您的问题与 NP 完全集覆盖问题一样困难，您不应浪费时间尝试提出一种有效的算法来生成完美的属性选择。

于 2013-07-07T10:55:23.017 回答
1

您可以尝试一种遗传算法方法，从一定（大量）随机属性组合开始，让最差的 x% 死亡并通过添加/删除属性来改变一定比例的剩余人口。

不能保证您会找到最佳答案，但很有可能在合理的时间内找到一个好的答案。

于 2013-07-07T09:44:17.613 回答
0

我没有想到解决这个问题的多项式算法。我只能建议你一个贪婪的启发式：

  1. 对于每个属性，计算它的，即如果单独expected_score选择它会给你的 SUM 带来的加数。在您的示例中，1 的分数是 3 - 87 = -84。

  2. 按expected_score非递增顺序对属性进行排序。

  3. 按照这个顺序，贪婪地添加L属性。调用actual_score该属性a实际为您的总和带来的分数（它可能比 更好或更差expected_score，具体取决于您在 中已有的属性L）。如果actual_score(a)不是严格正数，则丢弃a。

这不会给你最佳的L，但我认为一个“相当不错”。

于 2013-07-07T09:34:09.133 回答
0

注意：请参阅下面为什么这种方法不会给出最佳结果。

我的第一种方法是从特殊情况 L={} 开始（它应该给出所有整数的总和）并将其添加到解决方案列表中。从那里添加可能的属性作为限制。在第一次迭代中，依次尝试每个属性并记住那些给出更好结果的属性。在那次迭代之后，将记住的那些放入解决方案列表中。

在第二次迭代中，尝试为每个记住的属性添加另一个属性。记住所有改善结果的人。从记住的属性组合中删除重复项并将它们添加到解决方案列表中。请注意 {m,n} 与 {n,m} 相同，因此请跳过多余的组合以免破坏您的集合。

重复第二次迭代，直到没有更多可能的属性可以添加以改善最终总和。如果您随后按总和对解决方案列表进行排序，您将获得所请求的解决方案。

请注意，有大约 20G 的方法可以从 5k 中选择三个属性，因此您无法构建包含这些属性的数据结构，但您必须绝对按需生成它们。尽管如此，庞大的数量可以产生很多临时解决方案，因此您必须有效地存储它们，甚至可能存储在磁盘上。您可以利用这样一个事实，即您只需要前一次迭代的解决方案来进行下一次迭代，而不是之前的那些。

这里的另一个限制是您最终可能会得到少于 N 个最佳解决方案，因为所有低于 L={} 的解决方案都不会被考虑。在这种情况下，我会接受所有可能的解决方案，直到您有 N 个解决方案，并且只有在您拥有 N 个解决方案后，才会丢弃那些对最坏的解决方案没有改进的解决方案。

蟒蛇代码：

solutions = [{}]
remembered = [{}]
while remembered:
    tmp = remembered
    remembered = []
    for s in remembered:
        for xs in extensions(s):
            if score(xs) > score(s)
                remembered.append(xs)
    solutions.extend(remembered)

为什么这不起作用：

考虑由三个记录组成的临时解决方案

-2, T, F
-2, F, T
+3, F, F

这些的总和是-1。当我现在选择第一个属性时，我丢弃第二条和第三条记录，总和为 -2。选择第二个属性时，我丢弃了第一个和第三个，给出相同的总和 -2。当同时选择第一个和第二个属性时，我丢弃了所有三个记录，总和为零，这是一种改进。

于 2013-07-07T09:48:48.853 回答