Hispanopedia WikiEl algoritmo X es un algoritmo para resolver el problema de la cobertura exacta . Es un algoritmo recursivo , no determinista , de búsqueda en profundidad y de retroceso , utilizado por Donald Knuth para demostrar una implementación eficiente llamada DLX, que utiliza la técnica de enlaces danzantes . [ 1 ] [ 2 ]
Algoritmo
El problema de la cobertura exacta se representa en el Algoritmo X mediante una matriz de incidencia A compuesta por 0s y 1s. El objetivo es seleccionar un subconjunto de filas de tal manera 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; finaliza con éxito.
- De lo contrario, elija una columna c ( de forma determinista ).
- Elija una fila r tal que A r , c = 1 ( de forma no determinista ).
- Incluir 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 la 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 recursivamente en la matriz reducida A.
La elección no determinista de r implica que el algoritmo recurse sobre subalgoritmos independientes; cada subalgoritmo hereda la matriz actual A , pero la reduce con respecto a una fila r diferente . Si la columna c es completamente cero, no hay subalgoritmos y el proceso finaliza 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 conteniendo cada subalgoritmo que corresponde a k filas seleccionadas. El retroceso consiste en recorrer el árbol en preorden, en 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 elija la columna con la menor cantidad de unos.
Ejemplo
Por ejemplo, consideremos el problema de cobertura exacta especificado por el universo U = {1, 2, 3, 4, 5, 6, 7} y la colección de conjuntos S = { 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:
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: La menor cantidad de 1s en cualquier columna es dos. La columna 1 es la primera columna con dos 1s y, por lo tanto, se selecciona (de forma determinista):
Paso 3: Las filas A y B tienen cada una 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 está incluida en la solución parcial.
- Paso 5—La fila A tiene un 1 en las columnas 1, 4 y 7:
- 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, se deben eliminar las filas A , B , C , E y F , y las columnas 1, 4 y 7.
- La fila D permanece y las columnas 2, 3, 5 y 6 permanecen:
- Paso 1: La matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: La menor cantidad de 1s en cualquier columna es cero, y la columna 2 es la primera columna con cero 1s:
- Por lo tanto, esta rama del algoritmo finaliza sin éxito.
- El algoritmo pasa a la siguiente rama en el nivel 1…
- Nivel 1: Seleccione la fila B
- Paso 4: La fila B está incluida en la solución parcial.
- La fila B tiene un 1 en las columnas 1 y 4:
- 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, se deben eliminar las filas A , B y C , y las columnas 1 y 4.
- Quedan las filas D , E y F , y las columnas 2, 3, 5, 6 y 7:
- Paso 1: La matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: La menor cantidad de 1s en cualquier columna es uno. La columna 5 es la primera columna con un 1 y, por lo tanto, se selecciona (de forma determinista):
- Paso 3: La fila D tiene un 1 en la columna 5 y, por lo tanto, se selecciona (de forma no determinista).
- El algoritmo pasa a la primera rama en el nivel 2…
- Nivel 2: Seleccione la fila D
- Paso 4: La fila D está incluida en la solución parcial.
- Paso 5—La fila D tiene un 1 en las columnas 3, 5 y 6:
- 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, se deben eliminar las filas D y E , y las columnas 3, 5 y 6.
- La fila F permanece y las columnas 2 y 7 permanecen:
- Paso 1: La matriz no está vacía, por lo que el algoritmo continúa.
- Paso 2: La menor cantidad de 1s 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 está incluida en la solución parcial.
- La fila F tiene un 1 en las columnas 2 y 7:
- La columna 2 tiene un 1 en la fila F ; y la columna 7 tiene un 1 en la fila F. Por lo tanto, se debe eliminar la fila F y las columnas 2 y 7.
- No quedan filas ni columnas:
- Paso 1: La matriz está vacía, por lo tanto, esta rama del algoritmo finaliza con éxito.
- Como se han seleccionado las filas B , D y F (paso 4), la solución final en esta rama es:
- En otras palabras, la subcolección { B , D , F } es una cobertura exacta, ya que cada elemento está contenido en exactamente 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 tanto, el algoritmo pasa a la siguiente rama en el nivel 2…
- No hay más filas seleccionadas en el nivel 2, por lo tanto, el algoritmo pasa a la siguiente rama en el nivel 1…
- No hay más filas seleccionadas en el nivel 1, por lo tanto, el algoritmo pasa a la siguiente rama en el nivel 0…
No hay ramificaciones en el nivel 0, por lo tanto, el algoritmo finaliza.
En resumen, el algoritmo determina que solo hay una cobertura exacta: S * = { B , D , F }.
Implementaciones
El propósito principal de Knuth al describir el Algoritmo X era demostrar la utilidad de los enlaces dinámicos . Knuth demostró que el Algoritmo X puede implementarse eficientemente en una computadora utilizando enlaces dinámicos en un proceso que él denomina "DLX" . DLX utiliza la representación matricial del problema de cobertura exacta , implementada como 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. (Técnicamente, debido a que las listas son circulares, esto forma un toro ). Dado que los problemas de cobertura exacta tienden a ser dispersos, esta representación suele ser mucho más eficiente tanto en tamaño como en tiempo de procesamiento requerido. DLX utiliza enlaces dinámicos para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) eficientemente las suposiciones erróneas. [ 1 ]
Véase también
Referencias
- 1 2 Knuth, Donald (2000). "Dancing links". arXiv : cs/0011047 .
- ↑ Banerjee, Bikramjit; Kraemer, Landon; Lyle, Jeremy (2010-07-04). "Reconocimiento de planes multiagente: formalización y algoritmos" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 24 (1): 1059– 1064. doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468 .
- Knuth, Donald E. (2000), "Dancing links", en Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Perspectivas milenarias en informática: Actas del simposio Oxford-Microsoft de 1999 en honor a Sir Tony Hoare , Palgrave, pp. 187–214 , arXiv : cs/0011047 , Bibcode : 2000cs.......11047K , ISBN 978-0-333-92230-9.
Enlaces externos
- Artículo de Knuth - archivo PDF (también en arXiv : cs/0011047 )
- Artículo de Knuth que describe la optimización de Dancing Links : archivo PostScript comprimido con Gzip.
- Algoritmos de búsqueda
- Donald Knuth
