我有一个n浮点流列表,每个浮点流具有不同的大小.
可以使用以下规则将流组合在一起:
您可以从任何时间点开始放置流(在开始之前为零).您可以使用相同的流几次(它可以重叠,甚至可以在相同的位置几次),并且您可以根本不使用某个流.
例如:
输入流:
1 2 3 4
2 4 5 6 7
1 5 6
可以像:
1 2 3 4
1 5 6
1 5 6
在放置之后,输出流由每个输出浮点数等于每个项的平方和的平方根的规则组成.
例如:
如果某个位置的流是:
1
2
3
输出是:
sqrt(1*1 + 2*2 + 3*3) = sqrt(14) = 3.74...
所以对于示例组合:
1 2 3 4
1 5 6
1 5 6
输出是:
1 5.09 6.32 3 4.12 5 6
我所拥有的是输出流和输入流.我需要计算导致该输出的组合.确切的成分不一定存在 - 我需要尽可能接近输出的成分(最小的累积差异).
例如:
输入:
流模仿:
1 5.09 6.32 3 4.12 5 6
和一份清单:
1 2 3 4
2 4 5 6 7
1 5 6
预期产量:
Stream 0 starting at 1,
Stream 2 starting at 0,
Stream 2 starting at 4.
这似乎是一个NP问题,有什么快速的方法可以解决这个问题吗？它可能有点蛮力(但不完全,它不是理论上的问题),只要它足够接近它就不会给出最好的答案.
该算法通常与流一起用于模拟非常长的长度(可能是几兆字节),而它将有大约20个流组成,而每个流将大约为千字节长.
我认为你可以加快贪婪搜索的速度，而不是显而易见的。首先，对所有涉及的流中的每个元素进行平方。然后，您正在寻找看起来很像平方目标流的平方流之和。假设“看起来像”是平方流之间的欧几里得距离，被视为向量。
那么我们有 (ab)^2 = a^2 + b^2 - 2a.b。因此，如果我们能够快速找到两个向量的点积，并且知道它们的绝对大小，那么我们就可以快速找到距离。但是使用 FFT 和http://en.wikipedia.org/wiki/Convolution_theorem，我们可以通过使用 FFT 进行卷积计算出 a.b_i，其中 a 是目标流，b_i 是 i 的某个偏移处的流 b b 的反转版本 - 对于对 a 进行 FFT、对反转 b 进行 FFT 以及对结果进行 FFT 的成本，对于每个偏移量 i，我们得到 a.b_i。
如果我们进行贪心搜索，第一步将是找到使 (a-b_i)^2 最小的 b_i 并从 a 中减去它。然后我们寻找一个使 (a-b_i-c_j)^2 尽可能小的流 c_j。但这是 a^2 + b_i^2 + c_j^2 - 2a.b_i - 2a.c_j + 2b_i.c_j 并且我们已经在上面的步骤中计算了除 b_i.c_j 之外的所有内容。如果 b 和 c 是较短的流，则计算 b_i.c_j 会很便宜，并且我们可以像以前一样使用 FFT。
因此，我们有一种不太可怕的方法来进行贪婪搜索 - 在每个阶段从调整后的目标流中减去到目前为止的流，使残差最小（被视为欧几里德空间中的向量），然后从那里继续。在某个阶段，我们会发现我们可用的流都无法使残差变得更小。我们可以到此为止，因为上面的计算表明，同时使用两个流也无济于事 - 这是因为 b_i.c_j >= 0，因为 b_i 的每个元素 >= 0，因为它是一个正方形。
如果你进行了贪婪搜索并且不满意，但还有更多的 cpu 需要消耗，请尝试有限差异搜索。