Quel algorithme à utiliser pour segmenter une séquence de nombres dans n sous-ensembles, afin de minimiser l'écart type de la somme des nombres dans chaque sous-ensemble

Supposons que la longueur de la séquence d'origine est l code> et le nombre de sous-séquences est n code>.

vous pouvez Simplifiez l'expression de l'écart type pour obtenir sqrt (e [x ^ 2] - e [x] ^ 2) code >, où E code> désigne l'attente / moyenne et x code> indique votre variable aléatoire - dans votre cas, la somme des sous-séquences. (Une formule similaire s'applique à "l'exemple d'écart type".) Notez que E [x] code> ne dépend pas de la manière dont vous divisez votre séquence, car ce sera toujours la somme totale divisée par N code>. Ainsi, nous voulons simplement minimiser e [x ^ 2] code> ou équivalent, la somme de x ^ 2 code> (ils diffèrent par un facteur de n code > Par la définition de la moyenne). P>

À ce stade, nous pouvons constater que ce problème peut être résolu avec une programmation dynamique. Laissez f (i, j) code>, pour i code> à partir de 0 code> à m code> et j code > à partir de 1 code> à n code>, soyez la somme minimale des carrés de sujets de sous-séquences de la division du premier i code> éléments de votre séquence dans j code> des sous-séquences. Ensuite, nous voyons que f (i, j) code> peut être calculé en termes de tous les f (i ', j') code> avec i ' et j . Plus spécifiquement, si votre séquence est a [k] code> indexé de 0 code> à m-1 code>: p> xxx Pré>

ayant minimisé f (n, l) code>, vous pouvez utiliser des techniques de programmation dynamique standard pour récupérer les scissions. En particulier, vous pouvez stocker le l code> qui minimise f (i, j) code>. P>

Le temps d'exécution de cette solution est O (l ^ 2 N) code> parce que vous calculez o (ln) code> différentes valeurs de f code> et le minimum code> est sur o ( L) code> Valeurs différentes de l code>. P>

Voici une implémentation simple dans Perl: p>

#!/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;
}

Je conviens que la programmation dynamique peut être la meilleure approche - une technique que je voudrais exclure est une optimisation non linéaire. Vous avez une fonction d'objectif non linéaire si vous minimisez la racine carrée ou simplement la somme des différences au carré. Vous avez également une variables entière dans la partie de votre ensemble de contraintes - l'attribution de membres aux ensembles nécessite des variables entier quelle que soit votre formulation. Une optimisation non linéaire avec des variables entières est généralement très difficile, voire impossible à résoudre de manière optimale. Si vous n'avez besoin que d'une solution approximative, un algorithme génétique pourrait être une bonne approche où la chaîne génétique est une représentation de l'affectation d'un membre à un ensemble.

En ce qui concerne tout cela en moins d'une seconde ... bonne chance!