Algoritmo para buscar un subconjunto dentro de dos conjuntos de enteros cuyas sumas coincidan con

Question

Estoy buscando un algoritmo que pueda tomar dos conjuntos de enteros (tanto positivos como negativos) y buscar subconjuntos dentro de cada uno que tenga la misma suma.

El problema es similar al subset sum problem excepto que estoy buscando subconjuntos en ambos lados.

He aquí un ejemplo:

Lista A {4, 5, 9, 10, 1}

Lista B {21, 7, -4, 180}

Así que el único partido aquí es: {10, 1, 4, 9} < => {21, 7, -4}

¿Alguien sabe si existen algoritmos para este tipo de problemas?

Hasta ahora, la única solución que tengo es un enfoque de fuerza bruta que prueba todas las combinaciones pero funciona en tiempo exponencial y he tenido que poner un límite estricto a la cantidad de elementos a considerar para evitar que tome demasiado largo.

La única otra solución que puedo pensar es ejecutar un factorial en ambas listas y buscar las mismas, pero eso no es muy eficiente y demora exponencialmente a medida que las listas se hacen más grandes.

Answer 1

lo que han dicho es cierto:

1. Este problema es NP-completo. Una reducción fácil es a la suma de subconjuntos habitual. Puede mostrar esto al observar que un subconjunto de A suma a un subconjunto de B (no ambos vacíos) solo si un subconjunto no vacío de una unión (-B) suma a cero.

2. Este problema es sólo débilmente NP-completo, en el que es polinomio en el tamaño de los números de involucrados, pero se conjetura que ser exponencial en sus logaritmos . Esto significa que el problema es más fácil que el apodo "NP-complete" podría sugerir.

3. Debe utilizar la programación dinámica.

¿Qué estoy contribuyendo a esta discusión? Así, el código (en Perl):

@a = qw(4 5 9 10 1); 
@b = qw(21 7 -4 180); 
%a = sums(@a); 
%b = sums(@b); 
for $m (keys %a) { 
    next unless exists $b{$m}; 
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0); 
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n"; 
} 

sub sums { 
    my(@a) = @_; 
    my($a, %a, %b); 
    %a = (0 => []); 
    while(@a) { 
     %b = %a; 
     $a = shift @a; 
     for my $m (keys %a) { 
      $b{$m+$a} = [@{$a{$m}},$a]; 
     } 
    %a = %b; 
    } 
    return %a; 
} 

Imprime

sum(4 5 9 10) = sum(21 7) 
sum(4 9 10 1) = sum(21 7 -4) 

es así, sobre todo, hay más de una solución que funciona en su problema original!

Editar: ¡El usuario itzy señaló correctamente que esta solución era incorrecta, y peor, de varias maneras! Lo siento mucho y espero abordar estas preocupaciones en el nuevo código anterior. No obstante, todavía hay un problema, a saber, que para cualquier suma de subconjuntos particular, solo imprime una de las posibles soluciones. A diferencia de los problemas anteriores, que eran errores directos, clasificaría esto como una limitación intencional. ¡Mucha suerte y cuidado con los errores!

Answer 2

subconjunto suma es Np-completo y puede reducir polinomialmente su problema, por lo que su problema es NP-completo también.

Answer 3

Al igual que el problema de suma de subconjuntos, este problema es débilmente NP-completo, por lo que tiene una solución que se ejecuta en tiempo polinomial (M), donde M es la suma de todos los números que aparecen en la instancia del problema. Puede lograr eso con la programación dinámica. Para cada conjunto puede generar todas las sumas posibles mediante el llenado de una tabla binaria bidimensional, donde "verdadero" en (k, m) significa que se puede lograr una suma de subconjunto seleccionando algunos elementos de los primeros k elementos del conjunto.

Lo rellena de forma iterativa: establece (k, m) en "verdadero" si (k-1, m) se establece en "verdadero" (obviamente, si puede obtener m de elementos k-1, puede obténgalo de k elementos al no elegir la k-ésima) o si (k-1, md) se establece en "verdadero", donde d es el valor del elemento k-ésimo en el conjunto (el caso donde se elige el k- el elemento th).

Al llenar la tabla obtendrá todas las sumas posibles en la última columna (la que representa todo el conjunto). Haga esto para ambos conjuntos y encuentre sumas comunes. Puede retroceder los subconjuntos reales que representan las soluciones invirtiendo el proceso que utilizó para llenar las tablas.

Answer 4

¡Muchas gracias por todas las respuestas rápidas!

La solución de programación dinámica no es muy diferente a la aproximación exhaustiva que tenemos ahora y supongo que si necesitamos la solución óptima tenemos que considerar todas las combinaciones posibles pero el tiempo que lleva generar esta lista exhaustiva de sumas demasiado tiempo .. hizo una prueba rápida y el tiempo que se tarda en generar todas las sumas posibles de x número de elementos van muy rápidamente durante 1 min:

11 elements took - 0.015625 seconds 
12 elements took - 0.015625 seconds 
13 elements took - 0.046875 seconds 
14 elements took - 0.109375 seconds 
15 elements took - 0.171875 seconds 
16 elements took - 0.359375 seconds 
17 elements took - 0.765625 seconds 
18 elements took - 1.609375 seconds 
19 elements took - 3.40625 seconds 
20 elements took - 7.15625 seconds 
21 elements took - 14.96875 seconds 
22 elements took - 31.40625 seconds 
23 elements took - 65.875 seconds 
24 elements took - 135.953125 seconds 
25 elements took - 282.015625 seconds 
26 elements took - 586.140625 seconds 
27 elements took - 1250.421875 seconds 
28 elements took - 2552.53125 seconds 
29 elements took - 5264.34375 seconds 

que por el problema de negocio que estamos tratando de resolver es no es realmente aceptable. Voy a volver al tablero de dibujo y ver si realmente necesitamos saber todas las soluciones o podemos simplemente hacer con uno (el subconjunto más pequeño/más grande, por ejemplo) en su lugar y con suerte eso puede ayudar simplemente al problema y hacer que mi algoritmo funcione a la expectativa.

Gracias de todos modos!