Si alguna vez ha intentado crear un programa para resolver Sudoku , es posible que se haya topado con el problema de Exact Cover . En este artículo, discutiremos cuál es el problema de la cobertura exacta y un algoritmo “Algoritmo X” propuesto por Donald Knuth para resolver este problema.
Dada una colección S de subconjuntos del conjunto X , una cobertura exacta es el subconjunto S* de S tal que cada elemento de X contenido es exactamente un subconjunto de S*. Debe satisfacer las siguientes dos condiciones:
- La intersección de dos subconjuntos cualesquiera en S* debe estar vacía. Es decir, cada elemento de X debe estar contenido como máximo en un subconjunto de S*
- La unión de todos los subconjuntos en S* es X. Eso significa que la unión debe contener todos los elementos en el conjunto X. Entonces podemos decir que S* cubre X.
Ejemplo (representación estándar) –
Sea S = { A, B, C, D, E, F } y X = {1, 2, 3, 4, 5, 6, 7} tal que –
- A = {1, 4, 7}
- B = {1, 4}
- C = {4, 5, 7}
- re = {3, 5, 6}
- mi = {2, 3, 6 7}
- F = {2, 7}
Entonces S* = {B, D, F} es una cobertura exacta, porque cada elemento en X está contenido exactamente una vez en los subconjuntos {B, D, F}. Si unimos subconjuntos, obtendremos todos los elementos de X –
[Tex]B \bigcup D \bigcup F = \{ 1,2,3,4,5,6,7\}[\Tex]
El problema de la cobertura exacta es un problema de decisión para determinar si existe o no una cobertura exacta. Se considera un problema NP-Completo .
El problema se puede representar en forma de array donde la fila representa los subconjuntos de S y las columnas representan el elemento de X. El problema anterior se puede representar como:
array de problemas
En el contexto de la representación matricial, nuestra cobertura exacta es la selección de filas de modo que cada columna contenga solo 1 entre las filas seleccionadas. Entonces podemos ver a continuación que cada columna tiene solo 1 entre las filas seleccionadas B, D, F.
cobertura exacta
Algoritmo X
Donald Knuth propuso un Algoritmo X que puede encontrar todas las soluciones al problema exacto de la cobertura. El algoritmo X se puede implementar de manera eficiente mediante la técnica de «enlaces de baile» propuesta por Donald Knuth llamada DLX .
El algoritmo X es recursivo, primero en profundidad, algoritmo de retroceso. Es de naturaleza no determinista, lo que significa que para la misma entrada, puede exhibir diferentes comportamientos en una ejecución diferente.
A continuación se muestra el pseudocódigo para el Algoritmo X:
1. If the matrix A has no columns, the current partial solution
is a valid solution; terminate successfully.
2. Otherwise, choose a column c (deterministically).
3. Choose a row r such that A[r] = 1 (nondeterministically).
4. Include row r in the partial solution.
5. For each column j such that A[r][j] = 1,
for each row i such that A[i][j] = 1,
delete row i from matrix A.
delete column j from matrix A.
6. Repeat this algorithm recursively on the reduced matrix A.
Elección no determinista de r significa, el algoritmo se copia a sí mismo en el subalgoritmo. Cada subalgoritmo hereda la array A original pero la reduce con respecto a la r elegida (veremos esto en breve en el ejemplo)
El subalgoritmo forma un árbol de búsqueda con el problema original en la raíz y cada nivel k tiene subalgoritmo corresponde a las filas elegidas en el nivel anterior (al igual que el espacio de búsqueda n-queen ).
Si la columna c elegida es completamente cero, entonces no hay subalgoritmos y el proceso terminó sin éxito. Knuth sugiere que deberíamos elegir la columna con el número mínimo de 1 en ella. Si no queda ninguna columna, entonces sabemos que hemos encontrado nuestra solución.
Ejemplo
Considere el ejemplo anterior, aplicaremos el Algoritmo X para encontrar la cobertura exacta:
Nivel – 0
Paso 1: nuestra array no está vacía, tiene columnas, luego proceda
Paso 2: la primera columna que tiene un número mínimo de 1 es C-1, por lo que la seleccionaremos
Paso 3: Filas A y B tienen 1 en C-1 para que sean seleccionados. 
Entonces ahora el algoritmo se mueve a la primera rama en el nivel 1
Nivel – 1 (Seleccione la fila A)
Paso 4: Seleccione la fila A y agréguela a las soluciones parciales
Paso 5: La fila A tiene 1 en la columna 1, 4, 7 
C-1 tiene 1 en la fila A y B, C-4 tienen 1 en A, B y C, C-7 tienen 1 en la fila A, C, E y F. 
Por lo tanto, la columna 1, 4, 7 y las filas A, B, C, E y F deben eliminarse. 
Paso 1: la array no está vacía, así que proceda
Paso 2: la primera columna que tiene un número mínimo de 1 es C-2
Dado que la columna C-2 no tiene 1, nuestra búsqueda terminará aquí sin éxito.
Ahora nuestro algoritmo retrocederá en el nivel 0 y procederá con la fila B en la segunda rama en el nivel 1
Nivel: 1 (seleccione la fila B)
Paso: 4: seleccione la fila B y agréguela a las soluciones parciales
Paso: 5: la fila B tiene 1 en la columna C-1 y C-4 
C-1 tiene 1 en la fila A y B. C -4 tiene 1 en las filas A, B y C. 
Por lo tanto, C-1, C-2 y las filas A, B, C se eliminarán de la array. 
Ahora repetimos el algoritmo:
Paso 1: la array no está vacía, continúe
con el Paso 2: C-5 tiene un número mínimo de 1, por lo que se elige. 
Paso 3: la fila D tiene 1 en C-5, por lo que se elige
Ahora el algoritmo se mueve a la primera rama en el nivel 2 con la array que tiene la fila D, E y F
Nivel 2 (seleccione la fila D)
Paso 4: se elige la fila D y se agrega a la solución parcial.
Paso 5: C-3, C-5, C-6 tienen 1 en la fila D 
En C-3, la fila D y E tienen 1, en C-5, la fila D tiene 1 y en C-6, la fila D, E tienen 1 Entonces , 
estas filas y columnas deben eliminarse y nos quedamos con una array que tiene solo la fila F y la columna 2, 7. 
Ahora repetiremos el algoritmo:
Paso 1: la array no está vacía, así que continúe
con el Paso 2: C-2 es la primera columna tiene un número mínimo si hay 1 en ella. Entonces se elige
el Paso 3: la fila F tiene 1 en C-2, por lo que se elige.
Ahora el algoritmo se moverá a la primera rama en el nivel 3.
Nivel – 3 (Seleccione la fila F)
Paso 4: La fila F se agrega a la solución parcial
Paso 5: C-2 y C-7 tienen 1 en la fila F. 
C-2 tienen 1 en la fila F, C-7 tienen 1 en la fila F 
Por lo tanto, C2, C7 y la fila F deben eliminarse. Después de eliminar, nos quedará una array vacía para que nuestra búsqueda pueda terminar aquí con éxito y tengamos nuestra cobertura exacta {B, D, F}
el subalgoritmo retrocede en el nivel 2 y dado que no queda ninguna fila en el nivel 3
, retrocede aún más en el nivel 1. Dado que en el nivel 1 no queda ninguna fila para terminar nuestro algoritmo.
En el próximo artículo, discutiremos cómo implementar DLX de manera eficiente para resolver Exact Cover.
Referencias
Este artículo es una contribución de Atul Kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA