Какой алгоритм использовать для разбиения последовательности чисел на n подмножеств, чтобы минимизировать стандартное отклонение суммы чисел в каждом подмножестве

Question

Я ищу алгоритм для разбиения последовательности положительных чисел на n подпоследовательностей, чтобы стандартное отклонение суммы чисел в каждом подмножестве было минимальным.

Порядок чисел в каждой подпоследовательности должен совпадать с порядком в исходной последовательности

Например:

Предположим, у меня есть последовательность {1,1,1,1,1,1,10,1}, которую я хотел бы разделить на 2 подпоследовательности.
Я считаю, что оптимальным решением было бы {1,1,1,1,1,1}, {10,1}.

Сумма 1-й подпоследовательности равна 6, сумма 2-й подпоследовательности равна 11
. Стандартное отклонение двух чисел составляет ~ 3,5, что, я полагаю, является наименьшим возможным.

Предположим, у меня есть последовательность {4,1,1,1,1,6}, которую я хотел бы разделить на 3 подпоследовательности.
Я считаю, что оптимальным решением было бы {4}, {1,1,1,1}, {6}
Сумма подпоследовательностей составляет 4, 4 и 6.
Стандартное отклонение трех чисел составляет ~ 1,15, что, я считаю, является наименьшим возможным.

Лучший алгоритм, который мне удалось придумать, - это найти кумулятивную сумму каждого из чисел в последовательности и сегментировать последовательность на каждом интервале [totalSum / numSubsequence].

Например, учитывая последовательность {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 ^ numSubsequence).

Похоже, это тот тип вещей, к которому нужно применить уже существующий алгоритм, однако мой поиск в Google не помог мне. Мне известна проблема Partition , которая является 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 элементов вашей последовательности в 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;
}

Answer 2

Я согласен, что динамическое программирование может быть лучшим подходом - один метод, который я бы исключил, - это нелинейная оптимизация. У вас есть нелинейная целевая функция, минимизируете ли вы квадратный корень или просто сумму квадратов разностей. У вас также есть целочисленные переменные как часть вашего набора ограничений - назначение членов для наборов требует некоторых целочисленных переменных независимо от вашей формулировки. Нелинейная оптимизация с целочисленными переменными обычно очень трудна, если не невозможна, для оптимального решения. Если вам нужны только приблизительные решения, генетический алгоритм может быть хорошим подходом, когда генетическая строка представляет собой представление назначения для набора.

Что бы сделать все это менее чем за секунду ... Удачи!

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

Одна идея, которая приходит мне в голову, - это использовать алгоритм поиска 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 *.

Я не уверен, что это действительно поможет вам в вашей проблеме, так как я не решил эту проблему снова, но я думаю, что это может быть довольно хорошо. Это также, возможно, не самое сложное решение для этой конкретной проблемы, но оно, безусловно, лучше, чем любой подход «попробуй все комбинации». Это также является правильным и полным (из-за допустимой эвристики).

Если у вас есть еще вопросы по этому вопросу, и я сделаю все возможное, чтобы помочь вам.