python - studio - Cómo acelerar el código para resolver el rompecabezas de eliminación de bits

rompecabezas c#

Question

[Esto está relacionado con el conjunto mínimo de cobertura ]

Me gustaría resolver el siguiente rompecabezas por computadora para un tamaño pequeño de n. Considere todos los 2 ^ n vectores binarios de longitud n. Para cada uno, borra exactamente n / 3 de los bits, dejando una longitud de vector binario 2n / 3 (se supone que n es un múltiplo entero de 3). El objetivo es elegir los bits que elimine para minimizar el número de diferentes vectores binarios de longitud 2n / 3 que permanecen al final.

Por ejemplo, para n = 3 la respuesta óptima es 2 vectores diferentes 11 y 00. Para n = 6 es 4, para n = 9 es 6 y para n = 12 es 10.

Anteriormente había intentado resolver este problema como un problema de cobertura de conjunto mínimo del siguiente tipo. Todas las listas contienen solo 1s y 0s.

Digo que una lista A cubre una lista B si puedes hacer B desde A insertando exactamente x símbolos.

Considere todas las 2 ^ n listas de 1s y 0s de longitud n y establezca x = n/3 . Me gustaría calcular un conjunto mínimo de listas de longitud 2n/3 que las cubra todas. David Eisenstat proporcionó un código que convirtió este problema de cobertura de conjunto mínimo en un problema de programación de enteros mixtos que podría incluirse en CPLEX (o http://scip.zib.de/ que es de código abierto).

from collections import defaultdict
from itertools import product, combinations

def all_fill(source, num):
    output_len = (len(source) + num)
    for where in combinations(range(output_len), len(source)):
        poss = ([[0, 1]] * output_len)
        for (w, s) in zip(where, source):
            poss[w] = [s]
        for tup in product(*poss):
            (yield tup)

def variable_name(seq):
    return (''x'' + ''''.join((str(s) for s in seq)))
n = 12
shortn = ((2 * n) // 3)
x = (n // 3)
all_seqs = list(product([0, 1], repeat=shortn))
hit_sets = defaultdict(set)
for seq in all_seqs:
    for fill in all_fill(seq, x):
        hit_sets[fill].add(seq)
print(''Minimize'')
print('' + ''.join((variable_name(seq) for seq in all_seqs)))
print(''Subject To'')
for (fill, seqs) in hit_sets.items():
    print('' + ''.join((variable_name(seq) for seq in seqs)), ''>='', 1)
print(''Binary'')
for seq in all_seqs:
    print(variable_name(seq))
print(''End'')

El problema es que si establece n = 15, la instancia que genera es demasiado grande para cualquier solucionador que pueda encontrar. ¿Hay una manera más eficiente de resolver este problema para que pueda resolver n = 15 o incluso n = 18?

Answer 1

Esto no resuelve su problema (bueno, no lo suficientemente rápido), pero no está obteniendo muchas ideas y alguien más puede encontrar algo útil sobre lo que construir aquí.

Es un programa corto y puro de Python 3, que utiliza la búsqueda de seguimiento con algunas heurísticas de pedidos codiciosos. Resuelve las instancias N = 3, 6 y 9 muy rápidamente. También encuentra una cubierta de tamaño 10 para N = 12 rápidamente, pero aparentemente tomará mucho más tiempo para agotar el espacio de búsqueda (no tengo tiempo para esto y todavía está en ejecución). Para N = 15, el tiempo de inicialización ya es lento.

Las cadenas de bits están representadas por enteros de N bits simples aquí, por lo que consumen poco almacenamiento. Eso es para facilitar la grabación en un lenguaje más rápido. Hace un uso intensivo de conjuntos de enteros, pero no de otras estructuras de datos "avanzadas".

¡Espero que esto ayude a alguien! Pero está claro que la explosión combinatoria de posibilidades a medida que aumenta N asegura que nada será "lo suficientemente rápido" sin profundizar en las matemáticas del problema.

def dump(cover):
    for s in sorted(cover):
        print("    {:0{width}b}".format(s, width=I))

def new_best(cover):
    global best_cover, best_size
    assert len(cover) < best_size
    best_size = len(cover)
    best_cover = cover.copy()
    print("N =", N, "new best cover, size", best_size)
    dump(best_cover)

def initialize(N, X, I):
    from itertools import combinations
    # Map a "wide" (length N) bitstring to the set of all
    # "narrow" (length I) bitstrings that generate it.
    w2n = [set() for _ in range(2**N)]
    # Map a narrow bitstring to all the wide bitstrings
    # it generates.
    n2w = [set() for _ in range(2**I)]
    for wide, wset in enumerate(w2n):
        for t in combinations(range(N), X):
            narrow = wide
            for i in reversed(t):  # largest i to smallest
                hi, lo = divmod(narrow, 1 << i)
                narrow = ((hi >> 1) << i) | lo
            wset.add(narrow)
            n2w[narrow].add(wide)
    return w2n, n2w

def solve(needed, cover):
    if len(cover) >= best_size:
        return
    if not needed:
        new_best(cover)
        return
    # Find something needed with minimal generating set.
    _, winner = min((len(w2n[g]), g) for g in needed)
    # And order its generators by how much reduction they make
    # to `needed`.
    for g in sorted(w2n[winner],
                    key=lambda g: len(needed & n2w[g]),
                    reverse=True):
        cover.add(g)
        solve(needed - n2w[g], cover)
        cover.remove(g)

N = 9  # CHANGE THIS TO WHAT YOU WANT

assert N % 3 == 0
X = N // 3 # number of bits to exclude
I = N - X  # number of bits to include

print("initializing")
w2n, n2w = initialize(N, X, I)
best_cover = None
best_size = 2**I + 1  # "infinity"
print("solving")
solve(set(range(2**N)), set())

Ejemplo de salida para N = 9:

initializing
solving
N = 9 new best cover, size 6
    000000
    000111
    001100
    110011
    111000
    111111

Seguir

Para N = 12, esto terminó finalmente, lo que confirma que el conjunto mínimo de cobertura contiene 10 elementos (que se encontraron muy pronto al comienzo). No lo cronometré, pero me tomó al menos 5 horas.

¿Porque eso? Porque está cerca de muerte cerebral ;-) Una búsqueda completamente ingenua probaría todos los subconjuntos de las 256 cadenas cortas de 8 bits. Hay 2 ** 256 subconjuntos de este tipo, aproximadamente 1.2e77; no terminaría en la vida útil esperada del universo ;-)

Los trucos de pedido aquí primero detectan que las cadenas cortas "todo 0" y "todas 1" deben estar en cualquier conjunto de cobertura, así que selecciónalas. Eso nos deja mirando "solo" las 254 cuerdas cortas restantes. Luego, la codiciosa estrategia de "elegir un elemento que cubra la mayoría" encuentra rápidamente un conjunto de cobertura con 11 elementos en total y, poco después, una cobertura con 10 elementos. Eso resulta ser óptimo, pero lleva mucho tiempo agotar todas las demás posibilidades.

En este punto, cualquier intento de un conjunto de cobertura que alcance 10 elementos se cancela (¡entonces no puede ser menor que 10 elementos!). Si eso también se hiciera completamente ingenuo, tendría que intentar agregar (a las cadenas "todas las 0" y "todas las 1") todos los subconjuntos de 8 elementos de los 254 restantes, y 254-elegir-8 es aproximadamente 3.8e14. Mucho más pequeño que 1.2e77, pero aún demasiado grande para ser práctico. Es un ejercicio interesante para entender cómo el código logra hacerlo mucho mejor que eso. Sugerencia: tiene mucho que ver con los datos en este problema.

Los solucionadores de fuerza industrial son incomparablemente más sofisticados y complejos. Me sorprendió gratamente lo bien que funcionó este pequeño y sencillo programa en los casos de problemas más pequeños. Tuvo suerte.

Pero para N = 15 este enfoque simple no tiene remedio. Encuentra rápidamente una portada con 18 elementos, pero no hace ningún progreso más visible durante al menos horas. Internamente, sigue trabajando con los conjuntos needed que contienen cientos (incluso miles) de elementos, lo que hace que el cuerpo de solve() bastante caro. Todavía tiene 2 ** 10 - 2 = 1022 cadenas cortas para considerar, y 1022-elegir-16 es aproximadamente 6e34. No creo que ayude visiblemente, incluso si este código fuera acelerado por un factor de un millón.

Aunque fue divertido intentarlo :-)

Y una pequeña reescritura.

Esta versión se ejecuta al menos 6 veces más rápido en una carrera completa N = 12, simplemente eliminando las búsquedas inútiles de un nivel anterior. También acelera la inicialización y reduce el uso de la memoria al cambiar los conjuntos 2 ** N w2n en listas (no se utilizan operaciones de conjuntos en esos). Aún no hay esperanza para N = 15, aunque :-(

def dump(cover):
    for s in sorted(cover):
        print("    {:0{width}b}".format(s, width=I))

def new_best(cover):
    global best_cover, best_size
    assert len(cover) < best_size
    best_size = len(cover)
    best_cover = cover.copy()
    print("N =", N, "new best cover, size", best_size)
    dump(best_cover)

def initialize(N, X, I):
    from itertools import combinations
    # Map a "wide" (length N) bitstring to the set of all
    # "narrow" (length I) bitstrings that generate it.
    w2n = [set() for _ in range(2**N)]
    # Map a narrow bitstring to all the wide bitstrings
    # it generates.
    n2w = [set() for _ in range(2**I)]
    # mask[i] is a string of i 1-bits
    mask = [2**i - 1 for i in range(N)]
    for t in combinations(range(N), X):
        t = t[::-1]  # largest i to smallest
        for wide, wset in enumerate(w2n):
            narrow = wide
            for i in t:  # delete bit 2**i
                narrow = ((narrow >> (i+1)) << i) | (narrow & mask[i])
            wset.add(narrow)
            n2w[narrow].add(wide)
    # release some space
    for i, s in enumerate(w2n):
        w2n[i] = list(s)
    return w2n, n2w

def solve(needed, cover):
    if not needed:
        if len(cover) < best_size:
            new_best(cover)
        return
    if len(cover) >= best_size - 1:
        # can''t possibly be extended to a cover < best_size
        return
    # Find something needed with minimal generating set.
    _, winner = min((len(w2n[g]), g) for g in needed)
    # And order its generators by how much reduction they make
    # to `needed`.
    for g in sorted(w2n[winner],
                    key=lambda g: len(needed & n2w[g]),
                    reverse=True):
        cover.add(g)
        solve(needed - n2w[g], cover)
        cover.remove(g)

N = 9  # CHANGE THIS TO WHAT YOU WANT

assert N % 3 == 0
X = N // 3 # number of bits to exclude
I = N - X  # number of bits to include

print("initializing")
w2n, n2w = initialize(N, X, I)

best_cover = None
best_size = 2**I + 1  # "infinity"
print("solving")
solve(set(range(2**N)), set())

print("best for N =", N, "has size", best_size)
dump(best_cover)

Answer 2

Primero considere si tiene 6 bits. Puedes tirar 2 bits. Por lo tanto, cualquier balance de patrón de 6-0, 5-1 o 4-2 se puede convertir a 0000 o 1111. En el caso de un balance de 3-3 cero-uno, cualquier patrón se puede convertir en uno de cuatro casos: 1000, 0001 , 0111 o 1110. Por lo tanto, un posible conjunto mínimo para 6 bits es:

0000
0001
0111
1110
1000
1111

Ahora considere 9 bits con 3 tirados. Tienes el siguiente conjunto de 14 patrones maestros:

000000
100000
000001
010000
000010
110000
000011
001111
111100
101111
111101
011111
111110
111111

En otras palabras, cada conjunto de patrones tiene unos / ceros en el centro, con cada permutación de n / 3-1 bits en cada extremo. Por ejemplo, si tiene 24 bits, entonces tendrá 17 bits en el centro y 7 bits en los extremos. Como 2 ^ 7 = 128 tendrás 4 x 128 - 2 = 510 posibles patrones.

Para encontrar las eliminaciones correctas hay varios algoritmos. Un método es encontrar la distancia de edición entre el conjunto de bits actual y cada patrón maestro. El patrón con la distancia de edición mínima es el que se va a convertir. Este método utiliza la programación dinámica. Otro método sería hacer una búsqueda de árbol a través de los patrones utilizando un conjunto de reglas para encontrar el patrón coincidente.