Joh*_*ith 9 c arrays algorithm
是否有任何有效的技术可以进行以下求和？
给定有限集A,其包含n个整数A = {X1,X2,...,Xn},其中Xi是整数.现在有ň子集的一个,记为A1,A2,...,的.我们想要计算每个子集的总和.有一些有效的技术吗？
(注意,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
...
广义案例怎么样？有没有有效的方法来加速计算？谢谢!
对于某些子集的选择，如果您不介意进行一些（可能昂贵的）预计算，则有多种方法可以加快计算速度，但并非适用于所有子集。例如，假设您的子集为 {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 困难或更糟。（它当然是可计算的；您可能执行的一组可能的计算是有限的。但是，从表面上看，它可能非常昂贵；您可能会跟踪大约 2^n 部分和，添加以下任何一个：在每个步骤中将它们与任何其他步骤相结合，并且最多有大约 n^2 个步骤，以 (2^2n)^(n^2) = 2^(2n^3) 操作的超级天真成本来尝试每种可能性。 ）