使用什么算法将数字序列分割成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) 复杂性。

这似乎是一种需要应用预先存在的算法的事情，但是我的谷歌搜索失败了。我知道 分区问题，它是 NP 完全的，但涉及无序集，并且不是有序的序列。

任何帮助将不胜感激。

Answer 1

假设原始序列的长度为L，子序列的数量为N。

您可以简化标准差的表达式得到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 元素拆分为 i 的子序列之和的最小平方和code>j 子序列。然后我们看到，f(i,j) 可以根据所有 f(i',j') 进行计算，其中 i' <= i 和 j < j'。更具体地说，如果您的序列是从 0 索引到 M-1 的 a[k]：

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 ），您可以使用标准动态编程技术来恢复分割。特别是，您可以存储最小化 f(i,j) 的 l。

此解决方案的运行时间为 O(L^2 N)，因为您计算 O(LN) 不同的 f 值 和 最小值超过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;
}

Answer 2

我想到的一个想法是使用 A* 搜索算法。

更多相关信息：

http://en.wikipedia.org/wiki/A*_search_algorithm

值得阅读的好书：

Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig

您可以用于 A* 的一些内容：

• 初始状态：将序列拆分为 n 个相等（尽可能多）的子序列
• 下一个状态：对于每个子集添加左侧或右侧的数字 (子集 i-1 的最后一个数（如果 i != 0）或子集 i+1 的第一个数（如果 i != n））到它（创建当前状态节点的所有降序节点）
• 启发式：最优值将是所有值的平均值。它是可接受的，因此可以与 A* 一起使用。

我不确定这真的能帮助你解决你的问题，因为我还没有再次解决这个问题，但我认为它可能会做得很好。它也可能不是针对这个特定问题的最复杂的解决方案，但它肯定比任何“尝试所有组合”方法都要好。它也是健全和完整的（因为可接受的启发式）。

如果您对此还有更多疑问，请询问，我会尽力帮助您。

Answer 3

我认为你的意思是分成连续的块，或者换句话说，找到 n-1 个位置将序列切成碎片。 （如果您确实打算允许交错的子序列来创建主序列，您可能只需对序列进行排序，解决块问题，然后跟踪各个数字的来源以提供交错的子序列）。

我认为您可以使用动态规划在与序列长度的 n 倍成比例的时间内解决这个问题。从左到右填充 bestCost[i][j] 和 lastCut[i][j] 数组，其中 i 沿着序列运行，j 从 0 运行到 n-1。 bestCost[i][j] 是将序列从 0 到 i 分割成 j 个块的最佳方法的成本。 lastCut[i][j] 是产生 bestCost[i][j] 的剪切的最近剪切的位置。 bestCost[i + 1][j] = min_k 标准偏差（i + 1 到 k）+ bestCost[k - 1][j - 1]。然后lastCut[i + 1][j] = k。最后，您以相同的方式计算出 n 次切割的最佳答案的成本，然后使用 lastCut[][] 回溯以找到其他切割。

Answer 4

我同意动态编程可能是最好的方法 - 我会排除的一种技术是非线性优化。无论您是最小化平方根还是仅最小化平方差之和，您都有一个非线性目标函数。您还有一个整数变量作为约束集的一部分 - 将成员分配给集合需要一些整数变量，无论您的公式如何。使用整数变量的非线性优化通常是非常困难的，即使不是不可能最优地解决。如果您只需要近似解，遗传算法可能是一个好方法，其中遗传字符串表示成员到集合的分配。

就在不到一秒的时间内完成这一切......祝你好运！