En el campo matemático de la combinatoria , dada una colección de subconjuntos de un conjunto , una cobertura exacta es una subcolección tal que cada elemento está contenido exactamente en un subconjunto . Se dice que cada elemento en está cubierto por exactamente un subconjunto en . [1] Una portada exacta es una especie de portada . Es un tiempo polinomial (NP) completo no determinista y tiene una variedad de aplicaciones, que van desde la optimización de horarios de vuelos de aerolíneas, computación en la nube y diseño de circuitos electrónicos . [2]
En otras palabras, es una partición que consta de subconjuntos contenidos en .
El problema de cobertura exacta para encontrar una cobertura exacta es una especie de problema de satisfacción de restricciones . Los elementos de representan elecciones y los elementos de representan restricciones.
Un problema de cobertura exacta implica la relación contiene entre subconjuntos y elementos. Pero un problema de cobertura exacta puede representarse por cualquier relación heterogénea entre un conjunto de opciones y un conjunto de restricciones. Por ejemplo, un problema de cobertura exacta es equivalente a un problema de conjunto de golpes exacto , una matriz de incidencia o un gráfico bipartito .
En informática , el problema de cobertura exacta es un problema de decisión para determinar si existe una cobertura exacta. El problema de cobertura exacto es NP-completo [3] y es uno de los 21 problemas NP-completo de Karp . [4] Es NP-completo incluso cuando cada subconjunto en S contiene exactamente tres elementos; Este problema restringido se conoce como cobertura exacta por 3 juegos , a menudo abreviado X3C. [3]
El algoritmo X de Knuth es un algoritmo que encuentra todas las soluciones a un problema de cobertura exacta. DLX es el nombre que se le da al Algoritmo X cuando se implementa de manera eficiente utilizando la técnica Dancing Links de Donald Knuth en una computadora. [5]
El problema de cobertura exacta se puede generalizar ligeramente para involucrar no sólo restricciones de exactamente una vez sino también restricciones de como máximo una vez .
Encontrar mosaicos de Pentomino y resolver Sudoku son ejemplos notables de problemas de cobertura exacta. El problema de las n reinas es un problema de cobertura exacta generalizado.
Dada una colección de subconjuntos de un conjunto , una cobertura exacta de es una subcolección de que satisface dos condiciones:
En resumen, una cobertura exacta es exacta en el sentido de que cada elemento de está contenido exactamente en un subconjunto de .
De manera equivalente, una portada exacta es una subcolección de esas particiones .
Para que exista una cobertura exacta de es necesario que:
Si el conjunto vacío está contenido en , entonces no importa si está o no en una cubierta exacta. Por tanto, es típico suponer que:
Sea una colección de subconjuntos de un conjunto tal que:
La subcolección es una cobertura exacta de , ya que los subconjuntos y son disjuntos y su unión es .
La subcolección también es una portada exacta de . Incluir el conjunto vacío no hace ninguna diferencia, ya que es disjunto con todos los subconjuntos y no cambia la unión.
La subcolección no es una portada exacta de . Aunque la unión de los subconjuntos y es , la intersección de los subconjuntos y , no está vacía. Por lo tanto, los subconjuntos y no cumplen con el requisito disjunto de una cobertura exacta.
La subcolección tampoco es una portada exacta de . Aunque y están separados, su unión no lo es , por lo que no cumplen con el requisito de cobertura .
Por otro lado, no existe una cobertura exacta (de hecho, ni siquiera una cobertura) de porque es un subconjunto adecuado de : Ninguno de los subconjuntos de contiene el elemento 5.
Sea S = { A , B , C , D , E , F } una colección de subconjuntos de un conjunto X = {1, 2, 3, 4, 5, 6, 7} tal que:
La subcolección S * = { B , D , F } es una cobertura exacta, ya que cada elemento está cubierto (contenido en) exactamente un subconjunto seleccionado, como deja claro el resaltado.
Además, { B , D , F } es la única cobertura exacta, como lo demuestra el siguiente argumento: debido a que A y B son los únicos subconjuntos que contienen el elemento 1, una cobertura exacta debe contener A o B , pero no ambos. Si una portada exacta contiene A , entonces no contiene B , C , E o F , ya que cada uno de estos subconjuntos tiene el elemento 1, 4 o 7 en común con A . Entonces D es el único subconjunto restante, pero la subcolección { A , D } no cubre el elemento 2. En conclusión, no existe una cobertura exacta que contenga A. Por otro lado, si una portada exacta contiene B , entonces no contiene A o C , ya que cada uno de estos subconjuntos tiene el elemento 1 o 4 en común con B . Debido a que D es el único subconjunto restante que contiene el elemento 5, D debe ser parte exacta de la cobertura. Si una portada exacta contiene D , entonces no contiene E , ya que E tiene los elementos 3 y 6 en común con D . Entonces F es el único subconjunto restante, y la subcolección { B , D , F } es de hecho una cobertura exacta. Consulte el ejemplo en el artículo sobre el algoritmo X de Knuth para obtener una versión basada en matrices de este argumento.
Un problema de cobertura exacta se define por la relación heterogénea que contiene entre una colección S de subconjuntos y un conjunto X de elementos. Pero no hay nada fundamental en los subconjuntos y elementos.
Una representación de un problema de cobertura exacta surge siempre que existe una relación heterogénea R ⊆ S × X entre un conjunto S de opciones y un conjunto X de restricciones y el objetivo es seleccionar un subconjunto S * de S tal que cada elemento en X sea R T -relacionado exactamente con un elemento en S * . Aquí R T es el inverso de R .
En general, R T restringida a X × S * es una función de X a S * , que asigna cada elemento en X al elemento único en S * que está relacionado con R con ese elemento en X . Esta función es on , a menos que S * contenga un elemento (similar al conjunto vacío) que no esté relacionado con R con ningún elemento en X .
Las representaciones de un problema de cobertura exacta incluyen un problema de conjunto de golpes exacto, una matriz de incidencia y un gráfico bipartito.
En matemáticas , dado un conjunto S y una colección X de subconjuntos de S , un conjunto exacto S * es un subconjunto de S tal que cada subconjunto en X contiene exactamente un elemento en S * . Se dice que cada subconjunto en X es afectado por exactamente un elemento en S * .
El problema de conjunto de aciertos exacto es una representación de un problema de cobertura exacta que involucra la relación está contenido en lugar de contiene .
Por ejemplo, sea S = { a , b , c , d , e , f } un conjunto y X = { I , II , III , IV , V , VI , VII } una colección de subconjuntos de S tal que:
Entonces S * = { b , d , f } es un conjunto de impacto exacto, ya que cada subconjunto en X es golpeado por (contiene) exactamente un elemento en S * , como deja claro el resaltado.
Este ejemplo exacto de conjunto de golpes es esencialmente el mismo que el ejemplo detallado anterior. Mostrar la relación contenida en (∈) de elementos a subconjuntos deja claro que simplemente hemos reemplazado los subconjuntos con letras por elementos y los elementos numerados por subconjuntos:
La relación contenida se puede representar mediante una matriz de incidencia .
La matriz incluye una fila para cada subconjunto en S y una columna para cada elemento en X. La entrada en una fila y columna en particular es 1 si el subconjunto correspondiente contiene el elemento correspondiente y es 0 en caso contrario.
En la representación matricial, una cobertura exacta es una selección de filas de modo que cada columna contenga un 1 exactamente en una fila seleccionada. Cada fila representa una elección y cada columna representa una restricción.
Por ejemplo, la relación contenida en el ejemplo detallado anterior se puede representar mediante una matriz de incidencia de 6×7:
Nuevamente, la subcolección S * = { B , D , F } es una portada exacta, ya que cada columna contiene un 1 exactamente en una fila seleccionada, como deja claro el resaltado.
Consulte el ejemplo en el artículo sobre el algoritmo X de Knuth para obtener una solución basada en matrices para el ejemplo detallado anterior.
A su vez, se puede considerar que la matriz de incidencia también describe un hipergráfico . El hipergráfico incluye un nodo para cada elemento en X y un borde para cada subconjunto en S ; cada nodo está incluido exactamente en uno de los bordes que forman la cubierta.
La relación contenida se puede representar mediante un gráfico bipartito .
Los vértices del gráfico se dividen en dos conjuntos disjuntos, uno que representa los subconjuntos en S y otro que representa los elementos en X. Si un subconjunto contiene un elemento, una arista conecta los vértices correspondientes en el gráfico.
En la representación gráfica, una cobertura exacta es una selección de vértices correspondientes a subconjuntos de modo que cada vértice correspondiente a un elemento esté conectado exactamente a un vértice seleccionado.
Por ejemplo, la relación contenida en el ejemplo detallado anterior se puede representar mediante un gráfico bipartito con 6+7 = 13 vértices:
Nuevamente, la subcolección S * = { B , D , F } es una cobertura exacta, ya que el vértice correspondiente a cada elemento en X está conectado exactamente a un vértice seleccionado, como deja claro el resaltado.
Algoritmo X es el nombre que dio Donald Knuth para "el enfoque de prueba y error más obvio" para encontrar todas las soluciones al problema de cobertura exacto. [5] Técnicamente, el algoritmo X es un algoritmo de retroceso recursivo , no determinista , que prioriza la profundidad .
Cuando el Algoritmo X se implementa de manera eficiente utilizando la técnica Dancing Links de Donald Knuth en una computadora, Knuth lo llama DLX. Utiliza la representación matricial del problema, implementada como una serie de listas doblemente enlazadas de los 1 de la matriz: cada elemento 1 tiene un enlace al siguiente 1 arriba, abajo, a la izquierda y a la derecha de sí mismo. Debido a que los problemas de cobertura exacta tienden a ser escasos, esta representación suele ser mucho más eficiente tanto en tamaño como en tiempo de procesamiento requerido. Luego, DLX utiliza la técnica Dancing Links para seleccionar rápidamente permutaciones de filas como posibles soluciones y retroceder (deshacer) de manera eficiente las conjeturas erróneas. [5]
En un problema de cobertura exacta estándar, cada restricción debe satisfacerse exactamente una vez. Es una generalización simple relajar ligeramente este requisito y permitir la posibilidad de que algunas restricciones primarias deban satisfacerse exactamente con una opción, pero otras restricciones secundarias puedan satisfacerse mediante como máximo una opción.
Como explica Knuth, un problema de cobertura exacta generalizado se puede convertir en un problema de cobertura exacta equivalente simplemente agregando una fila para cada columna secundaria, que contenga un solo 1 en esa columna. [6] Si en una solución candidata particular se satisface una columna secundaria particular, entonces la fila agregada no es necesaria. Pero si la columna secundaria no se satisface, como se permite en el problema generalizado pero no en el problema estándar, entonces se puede seleccionar la fila agregada para garantizar que la columna se cumpla.
Pero Knuth continúa explicando que es mejor trabajar directamente con el problema generalizado, porque el algoritmo generalizado es más simple y rápido: un simple cambio en su Algoritmo X permite manejar columnas secundarias directamente.
El problema de N reinas es un ejemplo de un problema de cobertura exacta generalizado, ya que las restricciones correspondientes a las diagonales del tablero de ajedrez tienen un recuento máximo de reinas en lugar de exacto.
Debido a su integridad NP, cualquier problema en NP se puede reducir a problemas de cobertura exactos, que luego se pueden resolver con técnicas como Dancing Links. Sin embargo, para algunos problemas bien conocidos, la reducción es particularmente directa. Por ejemplo, el problema de colocar pentominós en un tablero y resolver Sudoku pueden verse como problemas de cobertura exactos.
El problema de colocar en mosaico un tablero de 60 cuadrados con los 12 pentominós libres diferentes es un ejemplo de un problema de cobertura exacta, como explica Donald Knuth en su artículo "Dancing links". [5]
Por ejemplo, considere el problema de revestir con pentominós un tablero de ajedrez de 8×8 sin los 4 cuadrados centrales:
El problema involucra dos tipos de restricciones:
Por tanto, hay 12+60 = 72 restricciones en total.
Como ambos tipos de restricciones son restricciones de exactamente una vez , el problema es un problema de cobertura exacta.
El problema implica muchas opciones, una para cada forma de colocar un pentominó en el tablero. Es conveniente considerar que cada elección satisface un conjunto de 6 restricciones: 1 restricción para el pentominó que se coloca y 5 restricciones para los cinco cuadrados donde se coloca.
En el caso de un tablero de ajedrez de 8×8 al que se le quitaron los 4 cuadros centrales, hay 1568 opciones de este tipo, por ejemplo:
Una de las muchas soluciones a este problema de cobertura exacto es el siguiente conjunto de 12 opciones:
Este conjunto de opciones corresponde a la siguiente solución al problema de mosaico del pentominó:
Un problema de mosaico de pentominó se ve más naturalmente como un problema de cobertura exacta que como un problema de conjunto de aciertos exacto, porque es más natural ver cada elección como un conjunto de restricciones que cada restricción como un conjunto de opciones.
Cada elección se relaciona con sólo 6 restricciones, que son fáciles de enumerar. Por otra parte, cada restricción se relaciona con muchas opciones, que son más difíciles de enumerar.
Ya sea visto como un problema de cobertura exacta o un problema de conjunto de aciertos exacto, la representación matricial es la misma, con 1568 filas correspondientes a opciones y 72 columnas correspondientes a restricciones. Cada fila contiene un único 1 en la columna que identifica el pentominó y cinco unos en las columnas que identifican los cuadrados cubiertos por el pentominó.
Usando la matriz, una computadora puede encontrar todas las soluciones con relativa rapidez, por ejemplo usando Dancing Links .
Artículos principales: Sudoku , Matemáticas del Sudoku , Algoritmos de resolución de Sudoku
El problema del Sudoku es asignar números (o dígitos, valores, símbolos) a celdas (o cuadrados) de una cuadrícula para satisfacer ciertas restricciones.
En la variante estándar del Sudoku 9×9, hay cuatro tipos de restricciones:
Si bien la primera restricción puede parecer trivial, es necesaria para garantizar que solo haya un número por celda. Naturalmente, colocar un número en una celda prohíbe colocar cualquier otro número en la celda ahora ocupada.
Resolver Sudoku es un problema de cobertura exacta. Más precisamente, resolver Sudoku es un problema de conjunto de aciertos exactos , lo que equivale a un problema de cobertura exacta, cuando se ve como un problema para seleccionar posibilidades de modo que cada conjunto de restricciones contenga (es decir, sea acertado por) exactamente una posibilidad seleccionada.
Cada posible asignación de un número particular a una celda particular es una posibilidad (o candidata). Cuando se juega al Sudoku con lápiz y papel, las posibilidades suelen denominarse marcas de lápiz.
En la variante estándar del Sudoku 9×9, en la que a cada una de las celdas de 9×9 se le asigna uno de los 9 números, hay 9×9×9=729 posibilidades. Usando notación obvia para filas, columnas y números, las posibilidades se pueden etiquetar
El hecho de que cada tipo de restricción implique exactamente una de algo es lo que hace del Sudoku un problema de conjunto de golpes exactos. Las restricciones se pueden representar mediante conjuntos de restricciones . El problema es seleccionar posibilidades de modo que cada conjunto de restricciones contenga (es decir, sea afectado por) exactamente una posibilidad seleccionada.
En la variante estándar del Sudoku 9×9, hay cuatro tipos de conjuntos de restricciones correspondientes a los cuatro tipos de restricciones:
Como hay 9 filas, 9 columnas, 9 cuadros y 9 números, hay 9×9=81 conjuntos de restricciones de fila-columna, 9×9=81 conjuntos de restricciones de número de fila, 9×9=81 conjuntos de restricciones de número de columna, y 9×9=81 conjuntos de restricciones de números de cuadro: 81+81+81+81=324 conjuntos de restricciones en total.
En resumen, la variante estándar del Sudoku 9×9 es un problema de conjunto de golpes exacto con 729 posibilidades y 324 conjuntos de restricciones. Por tanto, el problema se puede representar mediante una matriz de 729 × 324.
Aunque es difícil presentar la matriz completa de 729×324, la naturaleza general de la matriz se puede ver en varias instantáneas:
La matriz completa de 729 × 324 está disponible en Robert Hanson. [8]
Tenga en cuenta que el conjunto de posibilidades R x C y # z se puede organizar como un cubo de 9 × 9 × 9 en un espacio tridimensional con coordenadas x , y y z . Entonces, cada fila R x , columna C y o número # z es una "porción" de posibilidades de 9 × 9 × 1; cada caja B w es un "tubo" de posibilidades de 9x3×3; cada conjunto de restricciones de fila-columna R x C y , conjunto de restricciones de número de fila R x # z o conjunto de restricciones de número de columna C y # z es una "franja" de posibilidades de 9x1 × 1; cada conjunto de restricciones de número de cuadro B w # z es un "cuadrado" de posibilidades de 3x3×1; y cada posibilidad R x C y # z es un "cubículo" de 1x1×1 que consta de una única posibilidad. Además, cada conjunto de restricciones o posibilidad es la intersección de los conjuntos de componentes. Por ejemplo, R1C2#3 = R1 ∩ C2 ∩ #3, donde ∩ denota intersección establecida.
Aunque otras variaciones del Sudoku tienen diferentes números de filas, columnas, números y/o diferentes tipos de restricciones, todas involucran posibilidades y conjuntos de restricciones y, por lo tanto, pueden verse como problemas de conjuntos de aciertos exactos.
El problema de las N reinas es el problema de colocar n reinas de ajedrez en un tablero de ajedrez de n × n de modo que dos reinas no se amenacen entre sí. Una solución requiere que no haya dos reinas que compartan la misma fila, columna o diagonal. Es un ejemplo de un problema de cobertura exacta generalizado. [5]
El problema involucra cuatro tipos de restricciones:
Tenga en cuenta que las 2 N filas y filas forman las restricciones primarias, mientras que las 4 N − 2 diagonales y las diagonales inversas forman las restricciones secundarias. Además, debido a que cada una de las diagonales primera y última y las diagonales inversas involucran solo un cuadrado en el tablero de ajedrez, éstas se pueden omitir y, por lo tanto, se puede reducir el número de restricciones secundarias a 4 N − 6. La matriz para el problema de N reinas entonces tiene N 2 filas y 6 N − 6 columnas, cada fila para una posible ubicación de la reina en cada casilla del tablero de ajedrez y cada columna para cada restricción.
