El algoritmo X es un algoritmo para resolver el problema de cobertura exacto . Es un algoritmo de retroceso sencillo , recursivo , no determinista , de profundidad primero , utilizado por Donald Knuth para demostrar una implementación eficiente llamada DLX, que utiliza la técnica de enlaces danzantes . [1]
El problema de cobertura exacto está representado en el algoritmo X por una matriz A que consta de 0 y 1. El objetivo es seleccionar un subconjunto de filas de modo que el dígito 1 aparezca en cada columna exactamente una vez.
El algoritmo X funciona de la siguiente manera:
- Si la matriz A no tiene columnas, la solución parcial actual es una solución válida; terminar con éxito.
- De lo contrario, elija una columna c (de forma determinista ).
- Elija una fila r tal que A r , c = 1 ( no determinista ).
- Incluya la fila r en la solución parcial.
- Para cada columna j tal que A r , j = 1,
- para cada fila i tal que A i , j = 1,
- Eliminar fila i de la matriz A .
- eliminar la columna j de la matriz A .
- para cada fila i tal que A i , j = 1,
- Repita este algoritmo de forma recursiva en la matriz reducida A .
La elección no determinista de r significa que el algoritmo se repite sobre subalgoritmos independientes; cada subalgoritmo hereda la matriz A actual , pero la reduce con respecto a una fila r diferente . Si la columna c es completamente cero, no hay subalgoritmos y el proceso termina sin éxito.
Los subalgoritmos forman un árbol de búsqueda de forma natural, con el problema original en la raíz y con el nivel k que contiene cada subalgoritmo que corresponde a k filas elegidas. Retroceder es el proceso de atravesar el árbol en preorden, primero la profundidad.
Cualquier regla sistemática para elegir la columna c en este procedimiento encontrará todas las soluciones, pero algunas reglas funcionan mucho mejor que otras. Para reducir el número de iteraciones, Knuth sugiere que el algoritmo de selección de columnas seleccione una columna con el menor número de unos en ella.
Ejemplo
Por ejemplo, considere el problema de cobertura exacto especificado por el universo U = {1, 2, 3, 4, 5, 6, 7} y la colección de conjuntos= { A , B , C , D , E , F }, donde:
- A = {1, 4, 7};
- B = {1, 4};
- C = {4, 5, 7};
- D = {3, 5, 6};
- E = {2, 3, 6, 7}; y
- F = {2, 7}.
Este problema está representado por la matriz:
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
El algoritmo X con la heurística sugerida por Knuth para seleccionar columnas resuelve este problema de la siguiente manera:
Nivel 0
Paso 1: la matriz no está vacía, por lo que el algoritmo continúa.
Paso 2: el número más bajo de unos en cualquier columna es dos. La columna 1 es la primera columna con dos unos y, por lo tanto, se selecciona (de forma determinista):
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
Paso 3: las filas A y B tienen un 1 en la columna 1 y, por lo tanto, se seleccionan (de forma no determinista).
El algoritmo se mueve a la primera rama en el nivel 1 ...
- Nivel 1: seleccione la fila A
- Paso 4: la fila A se incluye en la solución parcial.
- Paso 5: la fila A tiene un 1 en las columnas 1, 4 y 7:
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
- La columna 1 tiene un 1 en las filas A y B ; la columna 4 tiene un 1 en las filas A , B y C ; y la columna 7 tiene un 1 en las filas A , C , E , y F . Por lo tanto, las filas A , B , C , E y F deben eliminarse y las columnas 1, 4 y 7 deben eliminarse:
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
- La fila D permanece y las columnas 2, 3, 5 y 6 permanecen:
2 3 5 6 D 0 1 1 1
- Paso 1: la matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: el número más bajo de 1 en cualquier columna es cero y la columna 2 es la primera columna con cero 1:
2 3 5 6 D 0 1 1 1
- Por tanto, esta rama del algoritmo termina sin éxito.
- El algoritmo pasa a la siguiente rama en el nivel 1 ...
- Nivel 1: seleccione la fila B
- Paso 4: la fila B se incluye en la solución parcial.
- La fila B tiene un 1 en las columnas 1 y 4:
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
- La columna 1 tiene un 1 en las filas A y B ; y la columna 4 tiene un 1 en las filas A , B , y C . Por lo tanto, las filas A , B y C deben eliminarse y las columnas 1 y 4 deben eliminarse:
1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 mi 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
- Las filas D , E y F permanecen y las columnas 2, 3, 5, 6 y 7 permanecen:
2 3 5 6 7 D 0 1 1 1 0 mi 1 1 0 1 1 F 1 0 0 0 1
- Paso 1: la matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: el número más bajo de unos en cualquier columna es uno. La columna 5 es la primera columna con un 1 y, por lo tanto, se selecciona (determinísticamente):
2 3 5 6 7 D 0 1 1 1 0 mi 1 1 0 1 1 F 1 0 0 0 1
- Paso 3: la fila D tiene un 1 en la columna 5 y, por lo tanto, se selecciona (de forma no determinista).
- El algoritmo se mueve a la primera rama en el nivel 2 ...
- Nivel 2: seleccione la fila D
- Paso 4: la fila D se incluye en la solución parcial.
- Paso 5: la fila D tiene un 1 en las columnas 3, 5 y 6:
2 3 5 6 7 D 0 1 1 1 0 mi 1 1 0 1 1 F 1 0 0 0 1
- La columna 3 tiene un 1 en las filas D y E ; la columna 5 tiene un 1 en la fila D ; y la columna 6 tiene un 1 en las filas D y E . Por lo tanto, las filas D y E deben eliminarse y las columnas 3, 5 y 6 deben eliminarse:
2 3 5 6 7 D 0 1 1 1 0 mi 1 1 0 1 1 F 1 0 0 0 1
- La fila F permanece y las columnas 2 y 7 permanecen:
2 7 F 1 1
- Paso 1: la matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: el número más bajo de unos en cualquier columna es uno. La columna 2 es la primera columna con un 1 y, por lo tanto, se selecciona (de forma determinista).
- La fila F tiene un 1 en la columna 2 y, por lo tanto, se selecciona (de forma no determinista).
- El algoritmo pasa a la primera rama en el nivel 3 ...
- Nivel 3: seleccione la fila F
- Paso 4: la fila F se incluye en la solución parcial.
- La fila F tiene un 1 en las columnas 2 y 7:
2 7 F 1 1
- La columna 2 tiene un 1 en la fila F ; y la columna 7 tiene un 1 en la fila F . Por lo tanto, la fila F debe eliminarse y las columnas 2 y 7 deben eliminarse:
2 7 F 1 1
- Paso 1: la matriz está vacía, por lo que esta rama del algoritmo termina con éxito.
- A medida que se seleccionan las filas B , D y F , la solución final es:
1 2 3 4 5 6 7 B 1 0 0 1 0 0 0 D 0 0 1 0 1 1 0 F 0 1 0 0 0 0 1
- En otras palabras, la subcolección { B , D , F } es una cobertura exacta, ya que cada elemento está contenido exactamente en uno de los conjuntos B = {1, 4}, D = {3, 5, 6} o F = {2, 7}.
- No hay más filas seleccionadas en el nivel 3, por lo que el algoritmo pasa a la siguiente rama en el nivel 2 ...
- No hay más filas seleccionadas en el nivel 2, por lo que el algoritmo pasa a la siguiente rama en el nivel 1 ...
- No hay más filas seleccionadas en el nivel 1, por lo que el algoritmo pasa a la siguiente rama en el nivel 0 ...
No hay ramas en el nivel 0, por lo que el algoritmo termina.
En resumen, el algoritmo determina que solo hay una cobertura exacta: = { B , D , F }.
Implementaciones
El principal propósito de Donald Knuth al describir el algoritmo X fue demostrar la utilidad de los enlaces danzantes . Knuth demostró que el algoritmo X se puede implementar de manera eficiente en una computadora usando enlaces danzantes en un proceso que Knuth llama "DLX" . DLX utiliza la representación matricial del problema de cobertura exacta , implementada como listas doblemente enlazadas de los 1 de la matriz: cada 1 elemento tiene un enlace al siguiente 1 arriba, abajo, a la izquierda y a la derecha de sí mismo. (Técnicamente, debido a que las listas son circulares, esto forma un toro ). Debido a que los problemas de cobertura exacta tienden a ser escasos, esta representación suele ser mucho más eficiente tanto en el tamaño como en el tiempo de procesamiento requerido. Luego, DLX usa enlaces danzantes para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) las suposiciones erróneas de manera eficiente. [1]
Ver también
Referencias
- ↑ a b Knuth, Donald (2000). "Enlaces de baile". arXiv : cs / 0011047 .
- Knuth, Donald E. (2000), "Dancing links", en Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honor of Sir Tony Hoare , Palgrave, págs. 187-214, arXiv : cs / 0011047 , Bibcode : 2000cs .... ... 11047K , ISBN 978-0-333-92230-9.
enlaces externos
- Documento de Knuth - archivo PDF (también arXiv : cs / 0011047 )
- Documento de Knuth que describe la optimización de Dancing Links - Archivo postscript con Gzip.