algorithm - potencia - relacion de equivalencia ejercicios resueltos

Partición un conjunto en k subconjunto disjunto

Question

Dele un conjunto S , divida el conjunto en k subconjuntos disjuntos de manera que la diferencia de sus sumas sea mínima.

digamos, S = {1,2,3,4,5} k = 2 , entonces { {3,4}, {1,2,5} } ya que sus sumas {7,8} tienen una diferencia mínima. Para S = {1,2,3}, k = 2 será {{1,2},{3}} ya que la diferencia en suma es 0 .

El problema es similar al Problema de partición de The Algorithm Design Manual . Excepto Steven Skiena discute un método para resolverlo sin reordenamiento.

Iba a probar Simulated Annealing. Entonces, me pregunto si hubiera un método mejor.

Gracias por adelantado.

Answer 1

El algoritmo pseudo-polytime para una mochila se puede usar para k=2 . Lo mejor que podemos hacer es sum (S) / 2. Ejecute el algoritmo de mochila

for s in S:
    for i in 0 to sum(S):
        if arr[i] then arr[i+s] = true;

luego observe la suma (S) / 2, seguida de la suma (S) / 2 +/- 1, etc.

Para ''k> = 3'', creo que esto es NP-completo, como el problema de 3 divisiones.

La forma más sencilla de hacerlo para k> = 3 es simplemente para forzarla brutalmente, aquí hay una forma, no estoy seguro de si es la más rápida o la más limpia.

import copy
arr = [1,2,3,4]

def t(k,accum,index):
    print accum,k
    if index == len(arr):
        if(k==0):
            return copy.deepcopy(accum);
        else:
            return [];

    element = arr[index];
    result = []

    for set_i in range(len(accum)):
        if k>0:
            clone_new = copy.deepcopy(accum);
            clone_new[set_i].append([element]);
            result.extend( t(k-1,clone_new,index+1) );

        for elem_i in range(len(accum[set_i])):
            clone_new = copy.deepcopy(accum);
            clone_new[set_i][elem_i].append(element)
            result.extend( t(k,clone_new,index+1) );

    return result

print t(3,[[]],0);

El recocido simulado podría ser bueno, pero dado que los "vecinos" de una solución en particular no son realmente claros, un algoritmo genético podría ser más adecuado para esto. Comenzarías seleccionando al azar un grupo de subconjuntos y ''mutar'' moviendo números entre subconjuntos.

Answer 2

Si los conjuntos son grandes, definitivamente iría a la búsqueda estocástica. No sé exactamente qué significa spinning_plate cuando escribe que "el vecindario no está claramente definido". Por supuesto que es --- mueves un elemento de un conjunto a otro, o intercambias elementos de dos conjuntos diferentes, y este es un vecindario simple. Utilizaría ambas operaciones en la búsqueda estocástica (que en la práctica podría ser búsqueda tabú o recocido simulado).