algorithm - resueltos - subconjuntos de los numeros naturales

Algoritmo para encontrar un subconjunto dentro de dos conjuntos de enteros cuyas sumas coinciden

Question

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

El problema es similar al problema de la suma de subconjuntos, excepto que estoy buscando subconjuntos en ambos lados.

Aquí hay un ejemplo:

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

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

Entonces, 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 tiempo.

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

Answer 1

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 polinomio de tiempo (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 llenas de forma iterativa: estableces (k, m) en "verdadero" si (k-1, m) se establece en "verdadero" (obviamente, si puedes obtener m de elementos k-1, puedes obtenerlo 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 elemento k-ésimo).

Llenar la mesa le proporciona 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 2

la suma del subconjunto es Np-complete y usted puede reducir polinomicamente su problema, por lo que su problema es NP-completo también.

Answer 3

¡Muchas gracias por todas las respuestas rápidas!

La solución de programación dinámica no es realmente diferente a la aproximación exhaustiva que tenemos ahora y supongo que si necesitamos la solución óptima, debemos considerar todas las combinaciones posibles, pero el tiempo que lleva generar esta lista exhaustiva de sumas es demasiado largo. Hizo una prueba rápida y el tiempo que toma generar todas las sumas posibles para x cantidad de elementos muy rápidamente durante más de 1 minuto:

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

lo cual para el problema comercial que estamos tratando de resolver no es realmente aceptable. Voy a volver al tablero de dibujo y ver si de hecho necesitamos saber todas las soluciones o podemos simplemente hacer con una (la más pequeña / subconjunto 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!

Answer 4

Lo que otros han dicho es verdad:

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 solo es débilmente NP-completo, ya que es polinomial en el tamaño de los números involucrados, pero se supone que es exponencial en sus logaritmos . Esto significa que el problema es más fácil que el apodo "NP-complete" podría sugerir.

3. Deberías usar programación dinámica.

Entonces, ¿qué estoy contribuyendo a esta discusión? Bueno, 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)

así que, notablemente, ¡hay más de una solución que funciona en su problema original!

Editar : ¡El itzy del usuario señaló correctamente que esta solución era incorrecta, y peor, de múltiples 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!