Algorithme pour diviser un tableau en p sous-systèmes de somme équilibrée

tout d'abord, formalisons votre problème d'optimisation en spécifiant l'entrée, la sortie et la mesure pour chaque solution possible (j'espère que c'est dans votre intérêt):

etant Donné un tableau d'entiers positifs et d'un entier positif P, distincte du tableau en P subarrays Non chevauchants tels que la différence entre la somme de chaque subarrays et la somme parfaite des subarrays (somme()/ P) est minime.

Entrée: Array d'entiers positifs; P est un entier positif.

Sortie: Array SA P nombres entiers non négatifs représentant la longueur de chaque subarray de où la somme de ces subarray longueur égale à la longueur de .

Mesure: abs (sum ( sa)-somme()/ P) est minime pour chaque sa ∈ { sa/ sa = ( _i,..., _{i+ SA j}) i = (Σ SA _j), j de 0 à P -1}.

entrée et sortie définir l'ensemble des solutions valables. mesure définit une mesure pour comparer plusieurs solutions valides. Et comme nous recherchons une solution avec la moindre différence par rapport à la solution parfaite (problème de minimisation), mesure devrait aussi être minime.

Avec cette information, il est assez facile à mettre en œuvre measure fonction (ici en Python):

def measure(a, sa):
    sigma = sum(a)/len(sa)
    diff = 0
    i = 0
    for j in xrange(0, len(sa)):
        diff += abs(sum(a[i:i+sa[j]])-sigma)
        i += sa[j]
    return diff

print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8

Maintenant trouver une solution optimale est un peu plus difficile.

nous pouvons utiliser le algorithme de Backtracking pour trouver des solutions valables et utiliser le mesure fonction pour les noter. Nous essayons essentiellement toutes les combinaisons possibles de P nombres entiers non négatifs qui totalisent la longueur () pour représenter toutes les solutions valables possibles. Bien que cela garantisse de ne pas manquer une solution valable, il est fondamentalement une approche brute-force avec l'avantage que nous pouvons omettre certaines branches qui ne peuvent pas être mieux que notre encore meilleure solution. E. g. dans l'exemple ci-dessus, nous n'aurions pas besoin de tester des solutions avec [9,...] (mesure > 38) si nous avons déjà une solution avec mesure ≤ 38.

suivant le modèle de pseudo-code de Wikipédia, notre bt fonction se présente comme suit:

def bt(c):
    global P, optimum, optimum_diff
    if reject(P,c):
        return
    if accept(P,c):
        print "%r with %d" % (c, measure(P,c))
        if measure(P,c) < optimum_diff:
            optimum = c
            optimum_diff = measure(P,c)
        return
    s = first(P,c)
    while s is not None:
        bt(list(s))
        s = next(P,s)

Les variables globales P,optimum et optimum_diff représentent l'instance du problème contenant les valeurs de , P et sigma, ainsi que la solution optimale et sa mesure:

class MinimalSumOfSubArraySumsProblem:
    def __init__(self, a, p):
        self.a = a
        self.p = p
        self.sigma = sum(a)/p

ensuite nous spécifions le reject et accept fonctions qui sont assez simples:

def reject(P,c):
    return optimum_diff < measure(P,c)
def accept(P,c):
    return None not in c

cela rejette tout simplement tout candidat dont la mesure est déjà plus que notre solution pourtant optimale. Et nous acceptons toutes les valides solution.

measure la fonction est également légèrement modifié en raison du fait que c peut maintenant contenir None valeurs:

def measure(P, c):
    diff = 0
    i = 0
    for j in xrange(0, P.p):
        if c[j] is None:
            break;
        diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
        i += c[j]
    return diff

Les deux autres de la fonction first et next sont un peu plus compliquées:

def first(P,c):
    t = 0
    is_complete = True
    for i in xrange(0, len(c)):
        if c[i] is None:
            if i+1 < len(c):
                c[i] = 0
            else:
                c[i] = len(P.a) - t
            is_complete = False
            break;
        else:
            t += c[i]
    if is_complete:
        return None
    return c

def next(P,s):
    t = 0
    for i in xrange(0, len(s)):
        t += s[i]
        if i+1 >= len(s) or s[i+1] is None:
            if t+1 > len(P.a):
                return None
            else:
                s[i] += 1
            return s

en gros, first remplace les None valeur de la liste 0 si ce n'est pas la dernière valeur dans la liste ou avec le reste pour représenter une solution valide (petite optimisation ici) si c'est la dernière valeur dans la liste, ou retour None si il n'y a pas de None valeur dans la liste. next incrémente simplement l'entier le plus droit par un ou retourne None si un incrément dépasse la limite totale.

maintenant tout ce dont vous avez besoin est de créer une instance de problème, initialiser les variables globales et appeler bt à la racine:

P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)

Code de travail ci-dessous (j'ai utilisé le langage php). Ce code décide de la quantité de la pièce elle-même;

$main = array(2,4,6,1,6,3,2,3,4,3,4,1,4,7,3,1,2,1,3,4,1,7,2,4,1,2,3,1,1,1,1,4,5,7,8,9,8,0);
$pa=0;
for($i=0;$i < count($main); $i++){
$p[]= $main[$i];
if(abs(15 - array_sum($p)) < abs(15 - (array_sum($p)+$main[$i+1])))
{
$pa=$pa+1;
$pi[] = $i+1;
$pc =  count($pi);

$ba = $pi[$pc-2] ;

$part[$pa] = array_slice( $main,  $ba, count($p));
unset($p);
}
}
print_r($part);
for($s=1;$s<count($part);$s++){
echo '<br>';
echo array_sum($part[$s]);
}

le code affichera les parties comme ci-dessous

13
14
16
14
15
15
17

si Je ne me trompe pas ici, une autre approche est la programmation dynamique.

Vous pouvez définir P [ pos, n] comme le plus petit "penalty" possible accumulé jusqu'à la position pos si n des subarrays ont été créés. De toute évidence, il y a une certaine Position pos' telle que

P[pos', n-1] + pénalité(pos', pos) = P[pos, n]

vous pouvez simplement minimiser plus de pos ' = 1..pos.

Les naïfs la mise en oeuvre s'effectuera en O(N^2 * M), où N - La Taille du tableau original et M - le nombre de divisions.

je me demande si ce qui suit pourrait fonctionner:

à partir de la gauche, dès que sum > sigma, branche en deux, une incluant la valeur qui la pousse, et une autre qui ne la pousse pas. Traiter les données de façon récursive vers la droite avec rightSum = totalSum-leftSum et rightP = P-1.

Donc, au début, somme = 60

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

Puis 2 4 6 7, somme = 19 > sigma, donc divisé en:

2 4 6     7 6 3 3 3 4 3 4 4 4 3 3 1

2 4 6 7     6 3 3 3 4 3 4 4 4 3 3 1

puis nous traitons 7 6 3 3 3 4 3 4 4 4 3 3 1 et 6 3 3 3 4 3 4 4 4 3 3 1P = 4-1 et sum = 60-12 et sum = 60-19 respectivement.

il en résulte, je pense, O (p*n).

cela pourrait être un problème quand 1 ou 2 valeurs est de loin la plus grande, mais, pour n'importe quelle valeur >= sigma, nous pouvons probablement juste mettre cela dans sa propre partition (prétraitement du tableau pour trouver ceux-ci pourraient être la meilleure idée (et réduire la somme de manière appropriée)).

Si cela fonctionne, il devrait minimiser la somme des carrés de l'erreur (ou proche), ce qui semble être la mesure souhaitée.

je propose un algorithme basé sur le rétractage. La fonction principale choisie au hasard sélectionne un élément du tableau original et l'ajoute à un tableau partitionné. Pour chaque ajout vérifiera pour obtenir une meilleure solution que l'original. Cela sera réalisé en utilisant une fonction qui calcule l'écart, en distinguant chaque ajout d'un nouvel élément à la page. Quoi qu'il en soit, j'ai pensé qu'il serait bon d'ajouter des variables originales dans les boucles que vous ne pouvez pas atteindre la solution désirée va forcer la fin du programme. Par solution désirée j'entends ajouter tous les éléments avec le respect de la condition imposée par la condition de si.

sum=CalculateSum(vector)
Read P
sigma=sum/P
initialize P vectors, with names vector_partition[i], i=1..P
list_vector initialize a list what pointed this P vectors
initialize a diferences_vector with dimension of P
//that can easy visualize like a vector of vectors
//construct a non-recursive backtracking algorithm
function Deviation(vector) //function for calculate deviation of elements from a vector
{
  dev=0
  for i=0 to Size(vector)-1 do
  dev+=|vector[i+1]-vector[i]|
  return dev 
}
iteration=0
//fix some maximum number of iteration for while loop
Read max_iteration
//as the number of iterations will be higher the more it will get  
//a more accurate solution
while(!IsEmpty(vector))
{   
   for i=1 to Size(list_vector) do
   {
       if(IsEmpty(vector)) break from while loop
       initial_deviation=Deviation(list_vector[i])
       el=SelectElement(vector) //you can implement that function using a randomized   
                               //choice of element
       difference_vector[i]=|sigma-CalculateSum(list_vector[i])|
       PutOnBackVector(vector_list[i], el)
       if(initial_deviation>Deviation(difference_vector))
          ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector)
    }
    iteration++
    //prevent to enter in some infinite loop
   if (iteration>max_iteration) break from while loop    

} Vous pouvez changer cela en ajoutant dans le premier si un certain accroissement de sorcière de code avec un montant l'écart calculé. aditional_amount=0 itération=0 alors { ... si (déviation initiale>déviation (secteur de différence)+montant additionnel) Extractfrombackvector etputonsecteurdecollecte(list_vector, vector) si (itération>max_itération) { itération=0 ational_amout+ = 1 / some_constant } itération++ // supprimer le deuxième si de la première version }

vous pouvez utiliser l'algorithme Max Flow.

Ton problème est très similaire, voire identique, le minimum makespan problème d'ordonnancement, selon la façon dont vous définissez votre objectif. Dans le cas où vous souhaitez réduire au maximum |sum_i - sigma|, c'est exactement le problème.

comme référencé dans L'article Wikipedia, ce problème est NP-complet pour p > 2. Graham liste algorithme d'ordonnancement est optimal pour p <= 3, et fournit un rapport approximatif de 2 - 1/p. Vous pouvez consulter le Article Wikipedia pour d'autres algorithmes et leur approximation.

tous les algorithmes donnés sur cette page résolvent pour un objectif différent, incorrect / suboptimal, ou peuvent être utilisés pour résoudre n'importe quel problème dans NP :)

C'est très similaire au cas de la unidimensionnel bin packing problèmehttp://www.cs.sunysb.edu / ~ algorithh / files / bin-packing.shtml