Algorithme pour diviser un tableau en P sous-réseaux de somme équilibrée

Question

J'ai un grand tableau de longueur N, disons quelque chose comme :

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

Je dois diviser ce tableau en P sous-ensembles (dans cet exemple, P=4 serait raisonnable), de telle sorte que la somme des éléments de chaque sous-réseau soit aussi proche que possible de sigma, c'est-à-dire :

sigma=(sum of all elements in original array)/P

Dans cet exemple, sigma=15 .

Par souci de clarté, un résultat possible serait le suivant :

2 4 6    7 6 3 3   3 4 3 4    4 4 3 3 1
(sums: 12,19,14,15)

J'ai écrit un algorithme très naïf basé sur la façon dont je ferais les divisions à la main, mais je ne sais pas comment imposer la condition qu'une division dont les sommes sont (14,14,14,14,14,19) est pire qu'une division qui est (15,14,16,14,16).

Je vous remercie d'avance.

Answer 1

Je propose un algorithme basé sur le backtracking. La fonction principale choisie sélectionne aléatoirement un élément du tableau original et l'ajoute à un tableau partitionné. Pour chaque ajout, on vérifiera si l'on obtient une meilleure solution que l'originale. Ceci sera réalisé en utilisant une fonction qui calcule la déviation, 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 une variable originale dans les boucles que vous ne pouvez pas atteindre la solution souhaitée forcera le programme à se terminer. Par solution souhaitée, j'entends ajouter tous les éléments en respectant la condition imposée par la condition de if.

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 modifier cela en ajoutant d'abord si un code de sorcière incrémente d'un montant l'écart calculé. montant_aditionnel=0 iteration=0 while { ... if(écart_initial>écart(vecteur_différence)+montant_complémentaire) ExtractFromBackVectorAnd [...] { [...] montant_complémentaire+=1/quelque_constante [...] itération++ //supprime le deuxième si de la première version }

Answer 2

Votre problème est très similaire ou identique à celui de la problème d'ordonnancement à portée minimale selon la manière dont vous définissez votre objectif. Dans le cas où vous souhaitez minimiser le maximum de |sum_i - sigma| C'est précisément ce problème qui se pose.

Comme indiqué dans l'article de Wikipedia, ce problème est NP-complet pour p > 2 . Graham's algorithme d'ordonnancement des listes est optimale pour p <= 3 et fournit un rapport d'approximation de 2 - 1/p . Vous pouvez consulter l'article de Wikipedia pour d'autres algorithmes et leur approximation.

Tous les algorithmes présentés sur cette page résolvent un objectif différent, sont incorrects/sous-optimaux, ou peuvent être utilisés pour résoudre n'importe quel problème dans NP :)

Answer 3

Ce cas est très similaire à celui de l'application unidimensionnelle de la norme problème d'emballage des bacs , voir http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml . Dans le livre associé, Manuel de conception d'algorithmes Skienna suggère une approche décroissante de premier ajustement . Il s'agit de déterminer la taille de l'emplacement (moyenne = somme / N), puis d'allouer le plus grand objet restant dans le premier emplacement qui peut l'accueillir. Soit vous arrivez à un point où vous devez commencer à surcharger une case, soit, si vous avez de la chance, vous obtenez un ajustement parfait. Comme le dit Skiena, "la décroissance au premier ajustement a un attrait intuitif, car nous emballons d'abord les objets volumineux et espérons que les petits objets pourront combler les fissures".

Comme l'a dit un autre internaute, le problème semble être NP-complet, vous ne pourrez donc pas le résoudre parfaitement en un temps raisonnable et vous devrez chercher des heuristiques.

Answer 4

J'en ai eu besoin récemment et j'ai procédé comme suit ;

1. créer un tableau initial de sous-réseaux d'une longueur donnée par le nombre de sous-réseaux. les sous-réseaux doivent également avoir une propriété de somme, c'est-à-dire [[sum:0],[sum:0]...[sum:0]]
2. trier le tableau principal en ordre décroissant.
3. recherche le sous-réseau ayant la plus petite somme, insère un élément du tableau principal et incrémente la propriété sum du sous-réseau de la valeur de l'élément inséré.
4. répéter le point 3 jusqu'à ce que la fin du tableau principal soit atteinte.
5. renvoyer le initial de la gamme.

Voici le code en JS.

function groupTasks(tasks,groupCount){
  var  sum = tasks.reduce((p,c) => p+c),
   initial = [...Array(groupCount)].map(sa => (sa = [], sa.sum = 0, sa));
  return tasks.sort((a,b) => b-a)
              .reduce((groups,task) => { var group = groups.reduce((p,c) => p.sum < c.sum ? p : c);
                                         group.push(task);
                                         group.sum += task;
                                         return groups;
                                       },initial);
}

var tasks = [...Array(50)].map(_ => ~~(Math.random()*10)+1), // create an array of 100 random elements among 1 to 10
   result = groupTasks(tasks,7);                             // distribute them into 10 sub arrays with closest sums

console.log("input array:", JSON.stringify(tasks));
console.log(result.map(r=> [JSON.stringify(r),"sum: " + r.sum]));

Answer 5

Vous pouvez utiliser l'algorithme Max Flow.