En informática , enlaces danzantes ( DLX ) es una técnica para agregar y eliminar un nodo de una lista circular doblemente enlazada . Es particularmente útil para implementar eficientemente algoritmos de retroceso , como el Algoritmo X de Knuth para el problema de cobertura exacta . [1] El algoritmo X es un algoritmo de retroceso recursivo , no determinista , de profundidad primero , que encuentra todas las soluciones al problema de cobertura exacto . Algunos de los problemas de cobertura exacta más conocidos incluyen el mosaico , el problema de las n reinas y el Sudoku .
El nombre enlaces de baile , sugerido por Donald Knuth , surge de la forma en que funciona el algoritmo, ya que las iteraciones del algoritmo hacen que los enlaces "bailen" con los enlaces de pareja para parecerse a un "baile exquisitamente coreografiado". Knuth le da crédito a Hiroshi Hitotsumatsu y Kōhei Noshita por haber inventado la idea en 1979, [2] pero es su artículo el que la popularizó.
Como el resto de este artículo analiza los detalles de una técnica de implementación para el Algoritmo X, se recomienda encarecidamente al lector que lea primero el artículo sobre el Algoritmo X.
La idea de DLX se basa en la observación de que en una lista circular de nodos doblemente enlazados ,
x.izquierda.derecha ← x.derecha;x.derecha.izquierda ← x.izquierda;
eliminará el nodo x de la lista, mientras que
x.izquierda.derecha ← x;x.derecha.izquierda ← x;
restaurará la posición de x en la lista, asumiendo que x.right y x.left no se han modificado. Esto funciona independientemente del número de elementos de la lista, incluso si ese número es 1.
Knuth observó que una implementación ingenua de su Algoritmo X requeriría una cantidad excesiva de tiempo buscando unos. Al seleccionar una columna, se debía buscar unos en toda la matriz. Al seleccionar una fila, se debía buscar unos en toda una columna. Después de seleccionar una fila, se debía buscar unos en esa fila y en varias columnas. Para mejorar este tiempo de búsqueda de complejidad O(n) a O(1), Knuth implementó una matriz dispersa donde solo se almacenan unos.
En todo momento, cada nodo de la matriz apuntará a los nodos adyacentes a la izquierda y a la derecha (unos en la misma fila), arriba y abajo (unos en la misma columna) y al encabezado de su columna (que se describe a continuación). Cada fila y columna de la matriz constará de una lista circular de nodos doblemente enlazada.
Cada columna tendrá un nodo especial conocido como "encabezado de columna", que se incluirá en la lista de columnas y formará una fila especial ("fila de control") que constará de todas las columnas que aún existen en la matriz.
Finalmente, cada encabezado de columna puede opcionalmente rastrear el número de nodos en su columna, de modo que ubicar una columna con el menor número de nodos sea de complejidad O( n ) en lugar de O( n × m ) donde n es el número de columnas y m es el número de filas. Seleccionar una columna con un número bajo de nodos es una heurística que mejora el rendimiento en algunos casos, pero no es esencial para el algoritmo.
En el algoritmo X, las filas y columnas se eliminan y restauran periódicamente en la matriz. Las eliminaciones se determinan seleccionando una columna y una fila en esa columna. Si una columna seleccionada no tiene filas, la matriz actual no tiene solución y se debe retroceder. Cuando se produce una eliminación, se eliminan todas las columnas para las cuales la fila seleccionada contiene un 1, junto con todas las filas (incluida la fila seleccionada) que contienen un 1 en cualquiera de las columnas eliminadas. Las columnas se eliminan porque se han completado y las filas se eliminan porque entran en conflicto con la fila seleccionada. Para eliminar una sola columna, primero elimine el encabezado de la columna seleccionada. A continuación, para cada fila donde la columna seleccionada contenga un 1, recorra la fila y elimínela de otras columnas (esto hace que esas filas sean inaccesibles y así se evitan los conflictos). Repita esta eliminación de columnas para cada columna donde la fila seleccionada contenga un 1. Este orden garantiza que cualquier nodo eliminado se elimine exactamente una vez y en un orden predecible, para que se pueda retroceder adecuadamente. Si la matriz resultante no tiene columnas, entonces todas se han llenado y las filas seleccionadas forman la solución.
Para retroceder, el proceso anterior debe revertirse utilizando el segundo algoritmo indicado anteriormente. Un requisito para utilizar ese algoritmo es que el retroceso debe realizarse como una inversión exacta de las eliminaciones. El artículo de Knuth ofrece una imagen clara de estas relaciones y de cómo funciona la eliminación y reinserción de nodos, y proporciona una ligera relajación de esta limitación.
También es posible resolver problemas de una sola cobertura en los que una restricción particular es opcional, pero no puede satisfacerse más de una vez. Dancing Links los acomoda con columnas primarias que deben completarse y columnas secundarias que son opcionales. Esto altera la prueba de solución del algoritmo de una matriz que no tiene columnas a una matriz que no tiene columnas primarias y si se utiliza la heurística de mínimo uno en una columna, entonces es necesario verificarla solo dentro de las columnas primarias. Knuth analiza las restricciones opcionales aplicadas al problema de las n reinas . Las diagonales del tablero de ajedrez representan restricciones opcionales, ya que algunas diagonales pueden no estar ocupadas. Si una diagonal está ocupada, sólo podrá ocuparse una vez.