9

是否有任何有效的技术来进行以下求和？

给定一个包含n 个整数A={X1,X2,…,Xn}的有限集A，其中Xi是一个整数。现在有A的n个子集，用A1, A2, ... , An表示。我们要计算每个子集的总和。有没有一些有效的技术？

（请注意，n通常大于A的所有子集的平均大小。）

例如，如果A={1,2,3,4,5,6,7,9} , A1={1,3,4,5} , A2={2,3,4} , A3= .. ... _ 计算A1和A2总和的简单方法需要 5 个 Flops 进行加法：

和(A1)=1+3+4+5=13

和(A2)=2+3+4=9

...

现在，如果先计算 3+4，然后记录它的结果 7，我们只需要 3 个 Flops 进行加法：

和(A1)=1+7+5=13

和(A2)=2+7=9

...

一般情况下呢？有没有什么有效的方法可以加快计算速度？谢谢！

4

5 回答 5

2

假设“加法”不仅仅是一个ADD操作，而是一些涉及两个整数操作数的非常密集的函数，那么一个明显的方法是缓存结果。

您可以通过合适的数据结构来实现这一点，例如包含由两个操作数组成的键和作为值的答案的键值字典。

但正如您C在问题中指定的那样，最简单的方法是n按n整数数组，其中的解决方案x + y存储在array[x][y].

然后，您可以重复迭代子集，并为每对操作数检查数组中的适当位置。如果不存在任何值，则必须对其进行计算并将其放入数组中。然后该值替换子集中的两个操作数并进行迭代。

如果操作是可交换的，则操作数应在查找数组之前进行排序（即第一个索引始终是两个操作数中的最小值），因为这将最大化“缓存”命中。

于 2012-04-30T12:35:53.877 回答
2

对于某些子集的选择，如果您不介意进行一些（可能很昂贵的）预计算，那么有一些方法可以加快计算速度，但不是全部。例如，假设您的子集是 {1,2}, {2,3}, {3,4}, {4,5}, ..., {n-1,n}, {n,1}; 那么幼稚的方法对每个子集使用一个算术运算，显然你不能做得比这更好。另一方面，如果您的子集是 {1}, {1,2}, {1,2,3}, {1,2,3,4}, ..., {1,2,..., n} 那么你可以使用 n-1 算术运算，而天真的方法要糟糕得多。

这是进行预计算的一种方法。它并不总能找到最佳结果。对于每对子集，将转换成本定义为 min（对称差异的大小，Y - 1 的大小）。（X 和 Y 的对称差是 X 或 Y 中的一组事物，但不是两者。）因此，转换成本是计算 Y 元素之和所需的算术运算次数，给定X的。将空集添加到子集列表中，并使用 Edmonds 算法 (http://en.wikipedia.org/wiki/Edmonds%27_algorithm) 或更快但更复杂的变体之一计算最小成本有向生成树那个主题。现在确保当您的生成树有一条边 X -> Y 时，您在 Y 之前计算 X。（这是一种“拓扑排序”，可以有效地完成。

当您有 {1,2}, {3,4}, {1,2,3,4}, {5,6}, {7,8}, {5,6 ,7,8}。在使用上述过程确定您的操作顺序之后，您可以进行优化传递，您可以找到更便宜的方法来评估每个集合的总和，给定已经计算的总和，这在实践中可能会给出相当不错的结果。

我怀疑，但没有试图证明，为给定的一组子集找到一个最佳过程是 NP-hard 或更糟的。（它当然是可计算的；您可能进行的计算集是有限的。但是，从表面上看，它可能非常昂贵；您可能正在跟踪大约 2^n 部分和，添加任何一个他们在每个步骤中与其他任何步骤，并且最多有大约 n^2 步骤，对于 (2^2n)^(n^2) = 2^(2n^3) 操作的超幼稚成本来尝试每种可能性。 )

于 2012-04-30T12:42:00.057 回答
1

一种常见的优化技术是预先计算中间结果。在您的情况下，您可以使用 2 个加数预先计算所有总和，A并将它们存储在查找表中。这将产生|A|*|A+1|/2表条目，其中|A|是 的基数A。

为了计算 Ai 的元素总和，您：

  • 查找Ai的前两个元素之和并保存在tmp中
  • 而 Ai 中还有一个元素 x：
  • 查找 tmp 和 x 的总和

为了A1 = {1,3,4,5}从您的示例中计算元素总和，请执行以下操作：

  • 查找（1,3）= 4
  • 查找（4,4）= 8
  • 查找（8,5）= 13

请注意，计算任何给定 Ai 的总和不需要求和，因为在预先计算查找表时已经进行了所有工作。

如果将查找表存储在哈希表中，则lookup()在 O(1) 中。


这种方法的可能优化：

  • 在计算求和结果的同时构建查找表；因此，您只计算您实际需要的那些总和。您的查找表现在是一个缓存。
  • 如果您的加法操作是可交换的，您可以通过仅存储较小的和先出现的那些总和来节省一半的缓存大小。然后修改lookup()这样lookup(a,b)= lookup(b,a)if a > b。
于 2012-04-30T12:36:19.090 回答
0

如果假设求和是耗时的操作，您可以找到每对子集的LCS（通过假设它们按照注释中提到的方式排序，或者如果它们没有排序，则对它们进行排序），然后计算最大长度的 LCS 总和（在所有 LCS成对），然后用相关数字替换相关数组中的值，更新它们的 LCS 并继续这种方式，直到没有超过一个数字的 LCS。当然这不是最佳的，但它比简单的算法更好（求和的数量较少）。但是，您可以进行回溯以找到最佳解决方案。

例如对于您的样本输入：

A1={1,3,4,5} , A2={2,3,4}

LCS (A_1,A_2) = {3,4} ==>7 ==>replace it:

A1={1,5,7}, A2={2,7} ==> LCS = {7}, maximum LCS length is `1`, so calculate sums.

您仍然可以通过计算两个随机数的总和来改进它，然后再次采用 LCS，...

于 2012-04-30T12:30:41.773 回答
0

不。没有有效的技术。

因为它是NP完全问题。并且没有针对此类问题的有效解决方案

为什么它是NP完全的？
我们可以使用该问题的算法来解决集合覆盖问题，只需将额外的集合放入集合中，包含所有元素。

示例：我们有一组元素
A1={1,2}, A2={2,3}, A3 = {3,4} 我们想解决集合覆盖问题。

我们添加到这个集合中，包含所有元素的数字集合 A4 = {1,2,3,4}

我们使用 John Smith 正在寻求的算法，并检查解决方案 A4 是否代表白衣。我们解决了 NP 完全问题。

于 2012-04-30T13:32:44.817 回答