arrays - resueltos - Algoritmo para dividir una matriz en subgrupos P de suma equilibrada

matrices

Question

Tengo una gran variedad de longitud N, digamos algo como:

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

Necesito dividir esta matriz en subgrupos P (en este ejemplo, P=4 sería razonable), de modo que la suma de los elementos en cada subarray sea lo más cercana posible a sigma, siendo:

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

En este ejemplo, sigma=15 .

Para mayor claridad, un posible resultado sería:

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

He escrito un algoritmo muy ingenuo basado en cómo haría las divisiones a mano, pero no sé cómo imponer la condición de que una división cuyas sumas son (14,14,14,14,19) es peor que una es decir (15,14,16,14,16).

Gracias de antemano.

Answer 1

Código de trabajo a continuación (utilicé el lenguaje php). Este código decide la cantidad de la pieza en sí;

$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]);
}

El código generará sumas parciales como las siguientes

13
14
16
14
15
15
17

Answer 2

Esto es muy similar al caso del problema de empaquetamiento de contenedores unidimensionales, consulte http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml . En el libro asociado, The Algorithm Design Manual , Skienna sugiere un enfoque decreciente de primer ajuste . Es decir, calcule el tamaño de su contenedor (media = suma / N) y luego asigne el objeto restante más grande en el primer contenedor que tenga espacio para él. O llegas a un punto en el que tienes que comenzar a llenar demasiado un contenedor, o si tienes suerte, obtienes un ajuste perfecto. Como dice Skiena, "la reducción del primer ajuste tiene un atractivo intuitivo, ya que primero empaquetamos los objetos voluminosos y esperamos que los pequeños objetos puedan llenar las grietas".

Como dijo un póster anterior, el problema parece ser NP-completo, por lo que no lo resolverá a la perfección en un tiempo razonable, y necesita buscar heurísticas.

Answer 3

Hace poco necesité esto e hice lo siguiente;

1. crear una matriz de subarreglos inicial de la cantidad de subgrupos dada dada. las matrices de sub también deben tener una propiedad de suma. es decir [[sum:0],[sum:0]...[sum:0]]
2. ordenar la matriz principal descendente.
3. busque la sub-matriz con la suma más pequeña e inserte un elemento de la matriz principal e incremente la propiedad de suma de las matrices secundarias por el valor del elemento insertado.
4. repita el elemento 3 hasta llegar al final de la matriz principal.
5. devuelve la matriz initial .

Este es el código 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 4

Me pregunto si lo siguiente funcionaría:

Vaya desde la izquierda, tan pronto como sum > sigma , divida en dos, uno que incluya el valor que lo empuja, y otro que no. rightSum = totalSum-leftSum recursivamente los datos a la derecha con rightSum = totalSum-leftSum y rightP = P-1 .

Entonces, al comienzo, suma = 60

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

Luego para 2 4 6 7 , suma = 19> sigma, entonces divídase 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

Luego procesamos 7 6 3 3 3 4 3 4 4 4 3 3 1 y 6 3 3 3 4 3 4 4 4 3 3 1 con P = 4-1 y sum = 60-12 y sum = 60-19 respectivamente.

Esto da como resultado, creo, O (P * n).

Puede ser un problema cuando 1 o 2 valores son los más grandes, pero para cualquier valor> = sigma, probablemente podamos colocarlo en su propia partición (preprocesar la matriz para encontrar estos puede ser la mejor idea) suma apropiadamente)).

Si funciona, es de esperar que minimice la suma de error al cuadrado (o cerca de eso), que parece ser la medida deseada.

Answer 5

Primero, formalicemos su problema de optimización especificando la entrada, la salida y la medida para cada solución posible (espero que esto sea de su interés):

Dada una matriz A de enteros positivos y un entero positivo P , separe la matriz A en P subconjuntos no superpuestos de manera que la diferencia entre la suma de cada subarreglo y la suma perfecta de los subconjuntos (suma ( A ) / P ) sea mínima .

Entrada : Array A de enteros positivos; P es un entero positivo.
Salida : Array SA de P enteros no negativos que representan la longitud de cada subarreglo de A donde la suma de estas longitudes de subarray es igual a la longitud de A.
Medida : abs (sum ( sa ) -sum ( A ) / P ) es mínimo para cada sa ∈ { sa | sa = ( A _i , ..., A _{i + ‍ SA j} ) para i = (Σ SA _j ), j de 0 a P -1}.

La entrada y la salida definen el conjunto de soluciones válidas. La medida define una medida para comparar múltiples soluciones válidas. Y ya que estamos buscando una solución con la menor diferencia con la solución perfecta (problema de minimización), la medida también debe ser mínima.

Con esta información, es bastante fácil implementar la función de measure (aquí 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

Ahora encontrar una solución óptima es un poco más difícil.

Podemos usar el algoritmo de Backtracking para encontrar soluciones válidas y usar la función de medición para calificarlas. Básicamente, probamos todas las combinaciones posibles de números enteros no negativos P que suman la longitud ( A ) para representar todas las soluciones válidas posibles. Si bien esto garantiza que no se pierda una solución válida, es básicamente un enfoque de fuerza bruta con el beneficio de que podemos omitir algunas sucursales que no pueden ser mejores que nuestra mejor solución. Por ejemplo, en el ejemplo anterior, no tendríamos que probar soluciones con [9, ...] ( medida > 38) si ya tenemos una solución con medida ≤ 38.

Siguiendo el patrón de pseudocódigo de Wikipedia, nuestra función bt tiene el siguiente aspecto:

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)

Las variables globales P , optimum y optimum_diff representan la instancia del problema que contiene los valores de A , P y sigma , así como la solución óptima y su medida:

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

A continuación especificamos las funciones de reject y accept que son bastante sencillas:

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

Esto simplemente rechaza a cualquier candidato cuya medida ya sea más que nuestra solución óptima. Y estamos aceptando cualquier solución válida.

La función de measure también se modificó ligeramente debido a que c ahora puede contener valores None :

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

Las dos funciones restantes first y next son un poco más complicadas:

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

Básicamente, first reemplaza el siguiente valor None en la lista con 0 si no es el último valor en la lista o con el resto para representar una solución válida (pequeña optimización aquí) si es el último valor en la lista, o regresa None si no hay ningún valor None en la lista. next simplemente incrementa el entero más a la derecha en uno o devuelve None si un incremento infringiría el límite total.

Ahora todo lo que necesita es crear una instancia de problema, inicializar las variables globales y llamar a bt con la raíz:

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)

Answer 6

Propongo un algoritmo basado en el backtracking. La función principal elegida selecciona aleatoriamente un elemento de la matriz original y lo agrega a una matriz particionada. Por cada adición se comprobará para obtener una solución mejor que la original. Esto se logrará mediante el uso de una función que calcula la desviación, distinguiendo cada uno agregando un nuevo elemento a la página. De todos modos, pensé que sería bueno agregar una variable original en los bucles que no se puede alcanzar, la solución forzará la finalización del programa. Por solución deseada, significa agregar todos los elementos con respecto a la condición impuesta por la condición 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    

} Puede cambiar esto agregando primero si algún código se incrementa con una cantidad de la desviación calculada. aditional_amount = 0 iteration = 0 while {... if (initial_deviation> Deviation (Difference_vector) + additional_amount) ExtractFromBackVectorAndPutOnSecondVector (list_vector, vector / es / un / un / un / un / un / otro / pequeño / ajedrez / servicio / centro de información). de la primera versión

Answer 7

Puede utilizar el algoritmo de flujo máximo.

Answer 8

Si no me equivoco aquí, un enfoque más es la programación dinámica.

Puede definir P [ pos , n ] como la "penalización" más pequeña posible acumulada hasta la posición pos si se crearan n subarrays. Obviamente hay alguna posición pos ''tal que

P [pos '', n-1] + penalización (pos'', pos) = P [pos, n]

Solo puedes minimizar sobre pos ''= 1..pos.

La implementación ingenua se ejecutará en O (N ^ 2 * M), donde N - tamaño de la matriz original y M - número de divisiones.

Answer 9

Su problema es muy similar, o igual, al problema mínimo de programación de makepan , dependiendo de cómo defina su objetivo. En el caso de que quiera minimizar el máximo |sum_i - sigma| , es exactamente ese problema.

Como se menciona en el artículo de Wikipedia, este problema es NP-completo para p > 2 . El algoritmo de programación de listas de Graham es óptimo para p <= 3 , y proporciona una relación de aproximación de 2 - 1/p . Puede consultar el artículo de Wikipedia para otros algoritmos y su aproximación.

Todos los algoritmos dados en esta página están resolviendo para un objetivo diferente, incorrecto / subóptimo, o pueden usarse para resolver cualquier problema en NP :)