algorithm - subconjuntos - problemas np ejemplos

Generar todas las sumas de subconjuntos dentro de un rango más rápido que O((k+N)*2 ^(N/2))?

Question

¿Hay alguna manera de generar todas las sumas de subconjuntos s ₁ , s ₂ , ..., s _k que caen en un rango [A, B] más rápido que O ((k + N) * 2 ^{N / 2} ), donde k es el número de sumas que hay en [A, B]? Tenga en cuenta que k solo se conoce después de haber enumerado todas las sumas de subconjuntos dentro de [A, B].

Actualmente estoy usando un algoritmo modificado de Horowitz-Sahni . Por ejemplo, primero lo llamo por la suma más pequeña mayor que o igual a A, dándome s ₁ . Luego lo vuelvo a llamar para la siguiente suma más pequeña mayor que s ₁ , dándome s ₂ . Repita esto hasta que encontremos una suma s _{k + 1} mayor que B. Hay una gran cantidad de cálculos repetidos entre cada iteración, incluso sin reconstruir las dos listas iniciales de 2 ^{N / 2} , entonces ¿hay alguna manera de hacerlo mejor?

En mi problema, N tiene aproximadamente 15, y la magnitud de los números es del orden de millones, por lo que no he considerado la ruta de programación dinámica.

Answer 1

Es posible hacer esto en O (N * 2 ^ (N / 2)), usando ideas similares a Horowitz Sahni, pero tratamos de hacer algunas optimizaciones para reducir las constantes en el BigOh.

Hacemos lo siguiente

• Step 1 : divide en conjuntos de N / 2 y genera todos los posibles 2 ^ (N / 2) conjuntos para cada división. Llámalos S1 y S2. Esto lo podemos hacer en O (2 ^ (N / 2)) (nota: el factor N falta aquí, debido a una optimización que podemos hacer).

• Step 2 : Luego, ordena el mayor de S1 y S2 (digamos S1) en O (N * 2 ^ (N / 2)) vez (optimizamos aquí al no ordenar ambos).

• Step 3 : Encuentre las sumas del subconjunto en el rango [A, B] en S1 usando la búsqueda binaria (como está ordenada).

• Step 4 : A continuación, para cada suma en S2, encuentre utilizando búsqueda binaria los conjuntos en S1, cuya unión con este da suma en el rango [A, B]. Esto es O (N * 2 ^ (N / 2)). Al mismo tiempo, encuentre si ese conjunto correspondiente en S2 está en el rango [A, B]. La optimización aquí es combinar bucles. Nota: Esto le da una representación de los conjuntos (en términos de dos índices en S2), no los conjuntos en sí mismos. Si quiere todos los conjuntos, se convierte en O (K + N * 2 ^ (N / 2)), donde K es el número de conjuntos.

Posibles optimizaciones adicionales, por ejemplo cuando la suma de S2 es negativa, no consideramos sumas <A, etc.

Dado que los Pasos 2,3,4 deben ser bastante claros, detallaré más sobre cómo hacer el Paso 1 en O (2 ^ (N / 2)) vez.

Para esto, usamos el concepto de Códigos Grises . Los códigos grises son una secuencia de patrones de bits binarios en los que cada patrón difiere del patrón anterior en exactamente un bit. Ejemplo: 00 -> 01 -> 11 -> 10 es un código gris con 2 bits.

Hay códigos grises que atraviesan todos los números de N / 2 bits posibles y estos se pueden generar de forma iterativa (ver la página wiki a la que he vinculado), en O (1) tiempo para cada paso (total O (2 ^ (N / 2) ) pasos), dado el patrón de bits anterior, es decir, dado el patrón de bits actual, podemos generar el siguiente patrón de bits en el tiempo O (1).

Esto nos permite formar todas las sumas de subconjuntos, utilizando la suma anterior y cambiando eso simplemente sumando o restando un número (correspondiente a la posición de bit diferente) para obtener la siguiente suma.

Answer 2

Verifique la suma del subconjunto en Wikipedia. Por lo que yo sé, es el algoritmo más rápido conocido, que opera en O (2 ^ (N / 2)) tiempo.

Editar: si busca múltiples sumas posibles, en lugar de solo 0, puede guardar las matrices finales y simplemente repetirlas nuevamente (que es aproximadamente una operación O (2 ^ (n / 2)) y guardar el reintegro El valor de todos los subconjuntos posibles no cambia con el objetivo.

Edita de nuevo: no estoy del todo seguro de lo que quieres. ¿Estamos ejecutando K búsquedas de un valor independiente cada uno, o buscando cualquier subconjunto que tenga un valor en un rango específico que sea K ancho? ¿O estás tratando de aproximar el segundo usando el primero?

Edite en respuesta: Sí, obtiene mucho trabajo duplicado incluso sin reconstruir la lista. Pero si no reconstruye la lista, eso no es O (k * N * 2 ^ (N / 2)). La construcción de la lista es O (N * 2 ^ (N / 2)).

Si conoce A y B en este momento, puede comenzar la iteración, y luego simplemente no detenerse cuando encuentre la respuesta correcta (el límite inferior), sino que continúe hasta que salga del rango. Eso debería ser más o menos lo mismo que resolver una suma de subconjuntos para una sola solución, involucrando solo + k más operaciones, y cuando hayas terminado, puedes abandonar la lista.

Más edición: Tienes un rango de sumas, de A a B. Primero, resuelves el problema de suma de subconjuntos para A. Luego, sigues iterando y almacenando los resultados, hasta que encuentres la solución para B, momento en el que te detienes. Ahora tiene cada suma entre A y B en una sola ejecución, y solo le costará una solución de problema de suma de subconjunto más operaciones K para valores K en el rango de A a B, que es lineal y agradable y rápido.

 s = *i + *j; if s > B then ++i; else if s < A then ++j; else { print s; ... what_goes_here? ... }

No no no. Ahora obtengo la fuente de tu confusión (malinterpreté algo), pero aún no es tan complejo como lo que originalmente tenías. Si desea encontrar TODAS las combinaciones dentro del rango, en lugar de una, tendrá que iterar sobre todas las combinaciones de ambas listas, lo cual no es tan malo.

Disculpe mi uso de auto. C ++ 0x compilador

std::vector<int> sums;
std::vector<int> firstlist;
std::vector<int> secondlist;
// Fill in first/secondlist.
std::sort(firstlist.begin(), firstlist.end());
std::sort(secondlist.begin(), secondlist.end());
auto firstit = firstlist.begin();
auto secondit = secondlist.begin();
// Since we want all in a range, rather than just the first, we need to check all combinations. Horowitz/Sahni is only designed to find one.
for(; firstit != firstlist.end(); firstit++) {
    for(; secondit = secondlist.end(); secondit++) {
        int sum = *firstit + *secondit;
        if (sum > A && sum < B)
            sums.push_back(sum);
    }
}

Todavía no es genial. Pero podría optimizarse si sabe de antemano que N es muy grande, por ejemplo, asignando o acumulando sumas a los iteradores, para que cualquier primer dado pueda encontrar socios adecuados en segundo lugar, reduciendo el tiempo de ejecución.

Answer 3

Si modifica el algoritmo Horowitz-Sahni de la manera correcta, entonces es apenas más lento que el original Horowitz-Sahni. Recuerde que Horowitz-Sahni trabaja dos listas de sumas de subconjuntos: Sumas de subconjuntos en la mitad izquierda de la lista original y sumas de subconjuntos en la mitad derecha. Llame a estas dos listas de sumas L y R. Para obtener subconjuntos que sumen un valor fijo A, puede ordenar R, y luego buscar un número en R que coincida con cada número en L usando una búsqueda binaria. Sin embargo, el algoritmo es asimétrico solo para guardar un factor constante en espacio y tiempo. Es una buena idea para este problema ordenar L y R.

En mi código a continuación también invierto L. Entonces puede mantener dos punteros en R, actualizados para cada entrada en L: puntero A a la última entrada en R que es demasiado baja, y un puntero a la primera entrada en R que es demasiado alto. Cuando avanza a la siguiente entrada en L, cada puntero puede avanzar o mantenerse, pero no tendrá que moverse hacia atrás. Por lo tanto, la segunda etapa del algoritmo Horowitz-Sahni solo toma tiempo lineal en los datos generados en la primera etapa, más el tiempo lineal en la longitud de la salida. Hasta un factor constante, no puedes hacer nada mejor que eso (una vez que te has comprometido con este algoritmo de meet-in-the-middle).

Aquí hay un código de Python con entrada de ejemplo:

# Input
terms = [29371, 108810, 124019, 267363, 298330, 368607,
    438140, 453243, 515250, 575143, 695146, 840979, 868052, 999760]
(A,B) = (500000,600000)

# Subset iterator stolen from Sage
def subsets(X):
    yield []; pairs = []
    for x in X:
        pairs.append((2**len(pairs),x))
        for w in xrange(2**(len(pairs)-1), 2**(len(pairs))):
            yield [x for m, x in pairs if m & w]

# Modified Horowitz-Sahni with toolow and toohigh indices
L = sorted([(sum(S),S) for S in subsets(terms[:len(terms)/2])])
R = sorted([(sum(S),S) for S in subsets(terms[len(terms)/2:])])
(toolow,toohigh) = (-1,0)
for (Lsum,S) in reversed(L):
    while R[toolow+1][0] < A-Lsum and toolow < len(R)-1: toolow += 1
    while R[toohigh][0] <= B-Lsum and toohigh < len(R): toohigh += 1
    for n in xrange(toolow+1,toohigh):
        print ''+''.join(map(str,S+R[n][1])),''='',sum(S+R[n][1])

"Moron" (creo que debería cambiar su nombre de usuario) plantea la cuestión razonable de optimizar el algoritmo un poco más al saltarse uno de los géneros. En realidad, dado que cada lista L y R es una lista de tamaños de subconjuntos, ¡puede hacer una generación combinada y una clasificación de cada uno en tiempo lineal! (Es decir, lineal en las longitudes de las listas.) L es la unión de dos listas de sumas, aquellas que incluyen el primer término, el término [0] y las que no. Entonces, en realidad, debes hacer una de estas mitades en forma ordenada, agregar una constante y luego hacer una fusión de las dos listas ordenadas. Si aplica esta idea recursivamente, guarda un factor logarítmico en el tiempo para hacer una L ordenada, es decir, un factor de N en la variable original del problema. Esto proporciona una buena razón para ordenar ambas listas a medida que las genera. Si solo ordena una lista, tiene algunas búsquedas binarias que podrían reintroducir ese factor de N; en el mejor de los casos, debes optimizarlos de alguna manera.

A primera vista, un factor de O (N) todavía podría estar allí por una razón diferente: si no solo quiere la suma del subconjunto, sino también el subconjunto que hace la suma, entonces parece que O (N) el tiempo y el espacio para almacenar cada subconjunto en L y en R. Sin embargo, hay un truco de intercambio de datos que también elimina ese factor de O (N). El primer paso del truco es almacenar cada subconjunto de la mitad izquierda o derecha como una lista vinculada de bits (1 si se incluye un término, 0 si no está incluido). Entonces, cuando la lista L se duplica en tamaño como en el párrafo anterior, las dos listas vinculadas para un subconjunto y su compañero pueden compartirse, excepto en la cabecera:

     0
     |
     v
1 -> 1 -> 0 -> ...

En realidad, este truco de la lista vinculada es un artefacto del modelo de costos y nunca realmente útil. Porque, para tener punteros en una arquitectura de RAM con costo O (1), debe definir palabras de datos con bits O (log (memoria)). Pero si tiene palabras de datos de este tamaño, también podría almacenar cada palabra como un vector de un solo bit en lugar de con esta estructura de puntero. Es decir, si necesita menos de una gigapalabra de memoria, puede almacenar cada subconjunto en una palabra de 32 bits. Si necesita más de una gigaword, entonces tiene una arquitectura de 64 bits o una emulación (o quizás 48 bits), y aún puede almacenar cada subconjunto en una palabra. Si aplica un parche al modelo de costo de RAM para tener en cuenta el tamaño de palabra, entonces este factor de N nunca estuvo realmente allí de todos modos.

Entonces, curiosamente, la complejidad del tiempo para el algoritmo original de Horowitz-Sahni no es O (N * 2 ^ (N / 2)), es O (2 ^ (N / 2)). Asimismo, la complejidad de tiempo para este problema es O (K + 2 ^ (N / 2)), donde K es la longitud de la salida.