algorithm - propios - Sum-subconjunto con un tamaño de subconjunto fijo

ejercicios de subconjuntos para primaria (6)

El problema de determinar si 0 en W + X + Y + Z = {w + x + y + z | w en W, x en X, y en Y, z en Z} es básicamente el mismo excepto por no tener casos degenerados molestos (es decir, los problemas son interreducibles con recursos mínimos).

Este problema (y por lo tanto el original para k = 4) tiene un algoritmo O (n ^ 2 log n) -time, O (n) -space. El algoritmo O (n log n) -time para k = 2 (para determinar si 0 en A + B) accede a A en orden clasificado y B en orden inverso ordenado. Por lo tanto, todo lo que necesitamos es un iterador de espacio O (n) para A = W + X, que se puede reutilizar simétricamente para B = Y + Z. Deje W = {w1, ..., wn} en orden ordenado. Para todo x en X, inserte un elemento de valor-clave (w1 + x, (1, x)) en una cola de prioridad. Repetidamente elimine el elemento mínimo (wi + x, (i, x)) e inserte (wi + 1 + x, (i + 1, x)).

El problema del subconjunto suma dice:

Dado un conjunto de enteros, ¿hay un subconjunto no vacío cuya suma es cero?

Este problema es NP-completo en general. Tengo curiosidad si se conoce la complejidad de esta pequeña variante:

Dado un conjunto de enteros, ¿hay un subconjunto de tamaño k cuya suma es cero?

Por ejemplo, si k = 1 , puede hacer una búsqueda binaria para encontrar la respuesta en O(log n) . Si k = 2 , puede bajarlo a O(n log n) (por ejemplo, consulte Buscar un par de elementos de una matriz cuya suma sea igual a un número dado ). Si k = 3 , entonces puede hacer O(n^2) (por ejemplo, vea Encontrar tres elementos en una matriz cuya suma es la más cercana a un número dado ).

¿Existe un límite conocido que se pueda colocar sobre este problema como una función de k ?

Como motivación, estaba pensando en esta pregunta. ¿Cómo se divide una matriz en 2 partes para que las dos partes tengan el mismo promedio? y tratando de determinar si en realidad es NP-completo. La respuesta está en si existe o no una fórmula como se describió anteriormente.

Salvo una solución general, estaría muy interesado en conocer un límite óptimo para k=4 .

La complejidad temporal es trivialmente O(n^k) (número de k subconjuntos de n elementos).

Como k es una constante dada, un polinomio superior (posiblemente de orden bastante elevado) limita la complejidad en función de n .

Para construir sobre la respuesta de awesomo ... si podemos suponer que los números están ordenados, podemos hacerlo mejor que O (n ^ k) para la k dada; simplemente tome todos los O (n ^ (k-1)) subconjuntos de tamaño (k-1), luego haga una búsqueda binaria en lo que queda para un número que, cuando se agrega al primero (k-1), da el objetivo. Esto es O (n ^ (k-1) log n). Esto significa que la complejidad es ciertamente menor que eso.

De hecho, si sabemos que la complejidad es O (n ^ 2) para k = 3, podemos hacerlo aún mejor para k> 3: elegir todos los conjuntos (k-3), de los cuales hay O (n ^ ( k-3)), y luego resuelve el problema en O (n ^ 2) en los elementos restantes. Esto es O (n ^ (k-1)) para k> = 3.

Sin embargo, tal vez puedas hacerlo aún mejor? Pensaré en esto.

EDITAR: inicialmente iba a agregar mucho proponiendo una visión diferente sobre este problema, pero he decidido publicar una versión abreviada. Animo a otros carteles a ver si creen que esta idea tiene algún mérito. El análisis es difícil, pero podría ser lo suficientemente loco como para funcionar.

Podemos usar el hecho de que tenemos una k fija, y que las sumas de números impares y pares se comportan de cierta manera, para definir un algoritmo recursivo para resolver este problema.

Primero, modifique el problema para que tenga números pares e impares en la lista (esto puede lograrse dividiendo por dos si todos son pares, o restando 1 de los números yk de la suma objetivo si todos son impares, y repitiendo según sea necesario).

A continuación, use el hecho de que incluso las sumas objetivo solo pueden alcanzarse mediante el uso de un número par de números impares, y se pueden alcanzar sumas objetivo impares utilizando solo un número impar de números impares. Genere subconjuntos apropiados de los números impares y llame al algoritmo de forma recursiva utilizando los números pares, la suma menos la suma del subconjunto de números impares examinados, y k menos el tamaño del subconjunto de números impares. Cuando k = 1, realiza una búsqueda binaria. Si alguna vez k> n (no estoy seguro de que esto pueda suceder), devuelva falso.

Si tiene muy pocos números impares, esto podría permitirle elegir rápidamente los términos que deben ser parte de un subconjunto ganador, o descartar los que no. Puede transformar problemas con muchos números pares en problemas equivalentes con muchos números impares utilizando el truco de resta. El peor caso, por lo tanto, debe ser cuando las cifras de números pares e impares son muy similares ... y ahí es donde estoy ahora. Un límite superior inútilmente flojo en esto es muchos órdenes de magnitud peor que la fuerza bruta, pero siento que esto es, al menos, tan bueno como la fuerza bruta. ¡Los pensamientos son bienvenidos!

EDIT2: Un ejemplo de lo anterior, para la ilustración.

{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20. Subset {}: {2, 2, 6, 20}, k = 3, sum = 20 = {1, 1, 3, 10}, k = 3, sum = 10 Subset {}: {10}, k = 3, sum = 10 Failure Subset {1, 1}: {10}, k = 1, sum = 8 Failure Subset {1, 3}: {10}, k = 1, sum = 6 Failure Subset {1, 7}: {2, 2, 6, 20}, k = 1, sum = 12 Failure Subset {7, 7}: {2, 2, 6, 20}, k = 1, sum = 6 Success

Pregunta que es muy similar:

¿Es esta variante del problema de la suma de subconjuntos más fácil de resolver?

Todavía es NP completo.

Si no fuera así, la suma del subconjunto también estaría en P, ya que podría representarse como F(1) | F(2) | ... F(n) F(1) | F(2) | ... F(n) F(1) | F(2) | ... F(n) donde F es tu función. Esto tendría O(O(F(1)) + O(F(2)) + O(F(n))) que seguiría siendo un polinomio, lo cual es incorrecto ya que sabemos que es NP-completo.

Tenga en cuenta que si tiene ciertos límites en las entradas, puede lograr un tiempo polinomial.

También tenga en cuenta que el tiempo de ejecución de la fuerza bruta se puede calcular con coeficientes binomiales.

La solución para k = 4 en O (n ^ 2log (n))

Paso 1: calcule la suma por parejas y clasifique la lista. Hay n (n-1) / 2 sumas. Entonces la complejidad es O (n ^ 2log (n)). Mantenga las identidades de las personas que hacen la suma.

Paso 2: para cada elemento de la lista anterior busque el complemento y asegúrese de que no compartan "los individuos". Hay n ^ 2 búsquedas, cada una con complejidad O (log (n))

EDITAR: La complejidad del espacio del algoritmo original es O (n ^ 2). La complejidad del espacio se puede reducir a O (1) simulando una matriz 2D virtual (O (n), si considera el espacio para almacenar la versión ordenada de la matriz).

Primero acerca de la matriz 2D: ordena los números y crea una matriz X usando sumas por pares. Ahora la matriz se encuentra de tal manera que todas las filas y columnas están ordenadas. Para buscar un valor en esta matriz, busque los números en la diagonal. Si el número está entre X [i, i] y X [i + 1, i + 1], básicamente puedes reducir a la mitad el espacio de búsqueda por matrices X [i: N, 0: i] y X [0: i , yo: N]. El algoritmo de búsqueda resultante es O (log ^ 2n) (NO ESTOY MUY SEGURO. ¿ALGUIEN PUEDE VERIFICARLO?).

Ahora, en lugar de usar una matriz real, use una matriz virtual donde X [i, j] se calculan según sea necesario en lugar de precompilarlos.

Complejidad del tiempo resultante: O ((nlogn) ^ 2).

PD: en el siguiente enlace, dice que la complejidad de la búsqueda en matriz ordenada en 2D es O (n) complejidad. Si eso es cierto (es decir, O (log ^ 2n) es incorrecto), entonces la complejidad final es O (n ^ 3).

Para k = 4, complejidad del espacio O (n), complejidad del tiempo O (n ² * log (n))

Ordenar la matriz A partir de 2 elementos más pequeños y 2 más grandes, calcule todas las sumas lesser de 2 elementos (a[i] + a[j]) en orden no decreciente y todas las sumas greater de 2 elementos (a[k] + a[l]) en el orden no creciente. Aumente la suma lesser si la suma total es menor que cero, disminuya la suma greater si la suma total es mayor que cero, deténgase cuando la suma total sea cero (éxito) o a[i] + a[j] > a[k] + a[l] (falla).

El truco es iterar a través de todos los índices i y j de tal manera, que (a[i] + a[j]) nunca disminuirá. Y para k y l , (a[k] + a[l]) nunca debería aumentar. Una cola de prioridad ayuda a hacer esto:

Coloque la key=(a[i] + a[j]), value=(i = 0, j = 1) en la cola de prioridad.
Pop (sum, i, j) de la cola de prioridad.
Use sum en el algoritmo anterior.
Pon (a[i+1] + a[j]), i+1, j y (a[i] + a[j+1]), i, j+1 en la cola de prioridad solo si estos elementos no están ya usado. Para realizar un seguimiento de los elementos usados, mantenga una matriz de ''j'' máxima utilizada para cada ''i''. Es suficiente usar solo valores para ''j'', que son mayores que ''i''.
Continúa desde el paso 2.

Para k> 4

Si la complejidad del espacio se limita a O (n), no puedo encontrar nada mejor que utilizar la fuerza bruta para k-4 valores k-4 y el algoritmo anterior para los 4 valores restantes. Complejidad del tiempo O (n ^(k-2) * log (n)).

Para k la programación lineal entera muy grande puede dar alguna mejora.

Actualizar

Si n es muy grande (en el mismo orden que el valor entero máximo), es posible implementar la cola de prioridad O (1), mejorando las complejidades a O (n ² ) y O (n ^(k-2) ).

Si n >= k * INT_MAX , es posible un algoritmo diferente con una complejidad de espacio O (n). Precalcula un conjunto de bits para todas las sumas posibles de valores k/2 . Y úselo para verificar sumas de otros valores k/2 . La complejidad del tiempo es O (n ^{(ceil (k / 2))} ).