Una prueba asistida por computadora resuelve el problema de "colorear el paquete".

Sin embargo, Heule encuentra alentador el descubrimiento de resultados pasados, ya que muestra que otros investigadores encuentran el problema lo suficientemente importante como para trabajar en él, y le confirma que el único resultado que vale la pena obtener es resolver el problema por completo.

"Una vez que nos dimos cuenta de que había habido 20 años de trabajo sobre el problema, cambió completamente el panorama", dijo.

Evitando lo vulgar

A lo largo de los años, Heule ha hecho una carrera encontrando formas eficientes de buscar a través de la gran cantidad de combinaciones posibles. Su enfoque se llama SAT solling, abreviatura de "satisfacibilidad". Implica construir una fórmula larga, llamada fórmula booleana, que puede tener dos resultados posibles: 0 o 1. Si el resultado es 1, la fórmula es verdadera y el problema está completo.

Para el problema de coloración del empaquetamiento, cada variable en la fórmula puede representar si una celda determinada está ocupada por un número determinado. La computadora busca formas de asignar variables para satisfacer la fórmula. Si el ordenador puede hacerlo, lo sabes... Es posible empaquetar la rejilla en las condiciones que establezcas.

Desafortunadamente, codificar directamente el problema de coloración del empaque como una fórmula booleana puede extenderse a muchos millones de términos: una computadora, o incluso un conjunto de computadoras, puede funcionar para siempre probando todas las diferentes formas de asignarle variables.

"Tratar de aplicar esta fuerza bruta llevaría hasta el fin del universo si lo hicieras de manera ingenua”, dijo Goddard. "Así que necesitas algunas grandes simplificaciones para llegar a algo que sea posible".

Además, cada vez que agregas un número al problema de colorear el paquete, se vuelve unas 100 veces más difícil, debido a la forma en que se multiplican las combinaciones posibles, lo que significa que si un grupo de computadoras trabajando en paralelo puede apagar 12 por un día de cálculo, necesitarían 100 días de tiempo de cálculo para descartar 13.

Heule y Subercaseaux consideran que la escala de un enfoque computacional de fuerza bruta es vulgar en cierto sentido. "Teníamos algunas ideas prometedoras, por lo que adoptamos la mentalidad de 'Intentemos optimizar nuestro enfoque hasta que podamos resolver este problema en menos de 48 horas de computación en el clúster'", dijo Subercasso.

Para hacer esto, tuvieron que encontrar formas de limitar la cantidad de combinaciones que el clúster de computación tenía que probar.

“[They] No solo quiero resolverlo, sino resolverlo de una manera impresionante", dijo. Alejandro Soifer de la Universidad de Colorado, Colorado Springs.

Heule y Subercaseaux se dieron cuenta de que muchas combinaciones eran esencialmente iguales. Si está tratando de llenar un mosaico en forma de diamante con ocho números diferentes, no importa si el primer número que coloca es uno arriba y uno a la derecha del cuadrado central o uno abajo y uno a la izquierda del cuadrado. plaza central. Los dos diseños son simétricos entre sí y limitan su próximo movimiento exactamente de la misma manera, por lo que no hay razón para verificarlos a ambos.

Si todos los problemas de empaquetamiento pudieran resolverse con un modelo de tablero de ajedrez, donde una cuadrícula diagonal de 1 cubre todo el espacio (como los espacios oscuros de un tablero de ajedrez), los cálculos podrían simplificarse mucho. Pero este no es siempre el caso, como en este ejemplo de una ficha limitada rellena con 14 números. El patrón de tablero de ajedrez debe romperse en varios lugares hacia la esquina superior izquierda.Cortesía de Bernardo Subercaseaux y Marijn Heule

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Subir
error: Content is protected !!