algorithm - 使用什么算法将数字序列分割成n个子集，以最小化每个子集中数字之和的标准差

Question

我正在寻找一种算法，将正数序列分割成 n 个子序列，从而使每个子集中数字之和的标准差最小化。

每个子序列中数字的顺序需要与原始序列中的顺序相同

例如:

假设我有一个序列 {1,1,1,1,1,1,10,1}，我想将其分割成 2 个子序列。
我相信最佳解决方案是 {1,1,1,1,1,1}, {10,1} 。

第一个子序列的和是6，第二个子序列的和是11
这两个数字的标准差约为 3.5，我认为这是最低的。

假设我有一个序列 {4,1,1,1,1,6}，我想将其分割成 3 个子序列。
我相信最佳解决方案是 {4}、{1,1,1,1}、{6}
子序列之和为4、4、6。
3 个数字的标准偏差为 ~1.15，我认为这是可能的最低值。

我能想出的最好的算法是找到序列中每个数字的累积和，并在 [totalSum/numSubsequences] 的每个间隔处分割序列。

例如，给定序列{4,1,1,1,1,6}，每个序列的数字累加和为{4,5,6,7,8,14}。序列中所有数字的总数是 14，因此，如果我想要 3 个子序列，我应该在总数达到 14/3 = 4.66 和 2 * 14/3 = 9.333333 时分割序列。

但是，在序列中并没有累计总数等于 4.66 的实际位置 - 第一个累计总数是 4，下一个累计总数是 5。那么我应该向上取整还是向下取整？在这种情况下，向下舍入到 4 会给出最佳解决方案，但情况并非总是如此。我能想到的最好办法是尝试向上和向下舍入的每种组合，但这会导致 O(2^numSubsequences) 复杂度。

这似乎是一种可以应用预先存在的算法的东西，但是我的谷歌搜索失败了。我知道 Partition Problem ，它是 NP 完全的，但它处理无序集，而不是有序序列。

如有任何帮助，我们将不胜感激。

Answer 1

假设原始序列的长度为L子序列的数量是N .

您可以 simplify the expression for standard deviation得到sqrt(E[X^2] - E[X]^2) , 其中E表示期望/平均值和 X表示你的随机变量——在你的例子中，是子序列的总和。 (类似的公式适用于“样本标准偏差”。)请注意 E[X]不取决于您如何分割序列，因为它总是总和除以 N。 .因此，我们只想最小化 E[X^2]或等效地，X^2 的总和(根据平均值的定义，它们相差 N 倍)。

至此，我们可以看出这个问题可以用动态规划来解决。让f(i,j) , 对于 i来自 0至 M和 j来自 1至 N , 是第一个 i 的 split 子序列总和的最小平方和将序列的元素放入 j子序列。然后我们看到 f(i,j)可以根据所有 f(i',j') 来计算与 i' <= i和 j < j' .更具体地说，如果您的序列是 a[k]索引自 0至 M-1 :

f(i,1) = sum( a[k] for 0 <= k < i )^2
f(i,j) = minimum of  f(l,j-1)+sum( a[k] for l < k < i )^2  for l from 0 to i

最小化f(N,L) ，您可以使用标准动态规划技术来恢复拆分。特别是，您可以存储 l最小化 f(i,j) .

此解决方案的运行时间为 O(L^2 N)因为你计算 O(L N) f 的不同值和 minimum结束O(L) l 的不同值.

这是 Perl 中的一个简单实现:

#!/usr/bin/perl

use strict;
use warnings;

local $\ = $/;
print join ", ", map {"@$_"} best( 2, qw(1 1 1 1 1 1 10 1) );
# prints "1 1 1 1 1 1, 10 1"

print join ", ", map {"@$_"} best( 3, qw(4 1 1 1 1 6) );
# prints "4, 1 1 1 1, 6"

sub best {
    my( $N, @a ) = @_;

    my( @f, @g, $i, $j, $k, $sum );

    # DP base case
    $sum = 0;
    $f[0][1] = $g[0][1] = 0;
    for $i ( 1 .. @a ) {
        $sum += $a[$i-1];
        $f[$i][1] = $sum * $sum;
        $g[$i][1] = 0;
    }

    # DP recurrence
    for $j ( 2 .. $N ) {
        $f[0][$j] = $g[0][$j] = 0;
        for $i ( 1 .. @a ) {
            $sum = 0;
            $f[$i][$j] = $f[$i][$j-1];
            $g[$i][$j] = $i;
            for $k ( reverse 0 .. $i-1 ) {
                $sum += $a[$k];
                if( $f[$i][$j] > $f[$k][$j-1] + $sum * $sum ) {
                    $f[$i][$j] = $f[$k][$j-1] + $sum * $sum;
                    $g[$i][$j] = $k;
                }
            }
        }
    }

    # Extract best expansion
    my( @result );
    $i = @a; $j = $N;

    while( $j ) {
        $k = $g[$i][$j];
        unshift @result, [@a[$k .. $i-1]];
        $i = $k;
        $j--;
    }

    return @result;
}