Algoritmo de retroceso recursivo para resolver el problema de partición

Question

Oye, estoy buscando ayuda para encontrar un algoritmo que divide una matriz de números positivos en k-partes para que cada parte tenga la (aproximadamente) la misma suma. . digamos que tenemos

1,2,3,4,5,6,7,8,9 en k = 3 thn el algoritmo debería dividirlo así 1,2,3,4,5 | 6, 7 | 8,9 el orden de los elementos no se puede cambiar ... Encontrar un algoritmo codicioso es fácil, pero estoy buscando una versión de retroceso que siempre devuelva la solución óptima ...

Annyone tiene alguna pista?

Answer 1

Aquí hay una solución que no utiliza ninguna estructura de datos dinámicos como listas. Son totalmente innecesarios y, en la práctica, harían que el algoritmo fuera mucho más lento de lo necesario.

Deje K ser el número de particiones aquí y N sea el número de elementos en su matriz.

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() */ 

Nota: este es un O (n ^K) algoritmo. Es subexponencial porque es no equivalente al problema general de partición de NP completo. Aquí se buscan segmentos contiguos de una matriz lineal en lugar de subconjuntos arbitrarios de un conjunto total dado.

Answer 2

¿Qué quiere decir con una solución óptima? Creo que te refieres al que minimiza la suma de cada distancia de partición a la partición óptima. La partición óptima sería la partición en la que su suma de elementos es igual a la suma total dividida en el número de particiones.

Si no te importa la eficiencia, entonces tal vez este enfoque aproximado sea lo suficientemente bueno para ti. No he probado el algoritmo para verificar que sea correcto, así que ten cuidado.

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

Aquí hay un algoritmo recursivo en Javascript. Esta función devuelve los totales que se asignarán a cada trabajador. Digamos que los bookLoads matriz de entrada es un conjunto de números positivos que desea dividir manera más justa posible en k-partes (digamos entre los trabajadores k)

Aquí es un violín de trabajo: 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}