algorithme récursif-retours en arrière pour résoudre le problème de partitionnement

Question

Hey, je suis à la recherche d'aide pour trouver un algorithme qui divise un tableau de nombres positifs en k parties-de sorte que chaque partie a (approximativement) la même somme ... disons que nous avons

1,2,3,4,5,6,7,8,9 en k = 3 THN l'algorithme doit partitionner comme ce 1,2,3,4,5 | 6,7 | 8,9 l'ordre des éléments ne peut pas être changé ... Trouver un algorithme glouton est facile, mais je suis à la recherche d'une version de retours en arrière qui renvoie toujours la solution optimale ...

Annyone a des notes?

Answer 1

Voici une solution qui n'utilise pas de structures de données dynamiques telles que des listes. Ils sont tout à fait inutiles et dans la pratique rendre l'algorithme beaucoup plus lent que nécessaire.

Soit K le nombre de partitions ici et N le nombre d'éléments dans votre tableau.

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

Note: ceci est un O (n ^K ) algorithme. Il est sous-exponentielle parce que c'est pas équivalent au problème général de partitionnement NP-complet a ici que vous cherchez contigus des segments d'un réseau linéaire au lieu de sous-ensembles arbitraires d'un ensemble total donné.

Answer 2

Qu'est-ce que vous entendez par solution? Je crois que vous voulez dire celui qui minimise la somme de chaque distance de partition à la partition optimale. La partition optimale serait la partition qui lui somme de éléments est égale à la somme totale divisée le nombre de partitions.

Si vous ne me dérange pas d'efficacité, alors peut-être cette approche approximative est assez bon pour vous. Je ne l'ai pas testé l'algorithme pour vérifier si elle est correct, alors soyez prudent.

void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance)
{
    if (i == numbers.Length)
    {
        int sum = numbers.Sum();
        int avg = sum / partitions.Length;
        int currentDistance = 0;
        foreach (var partition in partitions)
            currentDistance += Math.Abs(partition.Sum() - avg);
        if (currentDistance < minDistance)
        {
            minDistance = currentDistance;
            for (int j = 0; j < partitions.Length; j++)
                bestSolution[j] = new List<int>(partitions[j]);
        }
    }
    else
    {
        partitions[currentPartition].Add(numbers[i]);
        FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance);
        partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1);
        if (currentPartition < partitions.Length - 1)
            FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance);
    }
}

Answer 3

Voici un algorithme récursif en Javascript. Cette fonction retourne les totaux que chaque travailleur sera affecté. Disons que le tableau d'entrée bookLoads est un tableau de nombres positifs que vous voulez diviser le plus équitablement possible en k-parties (disons que parmi les travailleurs k)

Voici un violon de travail: https://jsfiddle.net/missyalyssi/jhtk8vnc/3/

function fairWork(bookLoads, numWorkers = 0) {
    // recursive version

    // utilities
    var bestDifference = Infinity;
    var bestPartition = {};
    var initLoads = {};
    var workers = Array.from({length: numWorkers}, (val, idx) => {
      initLoads[idx] = 0;
      return idx;
    });
    var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0); 
    var average = bookTotal / bookLoads.length;

    // recursive function
    function partition(books = bookLoads, workers, loads={}) {

      // if only one worker give them all the books
      if (workers.length == 1 && books.length > 0) {
        var onlyWorker = workers[0];
        loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => {
                               return acum + curr;
                             },0);
        books = [];
      }

      // base case
      if (books.length == 0) {
        var keys = Object.keys(loads);
        var total = 0;
        for (let key = 0; key < keys.length; key++) {
          // square so that difference shows 
          total += Math.pow(Math.abs(average - loads[keys[key]]), 2);
        }
        if (total < bestDifference) {
          bestDifference = total;
          bestPartition= loads;
        }
        return bestPartition;
      }

      var currBookLoad = books[0];

      // add book to curr worker 1
      var newWorker1Loads = Object.assign({}, loads);
      var worker1 = workers[0]; 
      newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers, newWorker1Loads)

      // give to next worker
      var newNextWorkerLoads = Object.assign({}, loads);
      var worker2 = workers[1]; 
      newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers.slice(1), newNextWorkerLoads)

      return bestPartition;
    }
    // function call
    return partition(bookLoads, workers, initLoads)
}
fairWork([3,1,2,3], 3)
//Result will be: Object {0: 3, 1: 3, 2: 3}
fairWork([1,2,3,4,5,6,7,8,9], 3)
//Result will be: Object {0: 15, 1: 13, 2: 17}