Enlaces de baile - Dancing Links

El algoritmo Dancing Links para resolver un rompecabezas de policubos

En informática , los enlaces danzantes es una técnica para revertir la operación de eliminar un nodo de una lista circular doblemente enlazada . Es particularmente útil para implementar eficientemente algoritmos de retroceso , como el Algoritmo X de Donald Knuth para el problema de cobertura exacta . X es un algoritmo recursivo , no determinista , primero en profundidad , dando marcha atrás algoritmo que encuentra todas las soluciones a la cobertura exacta problema. Algunos de los problemas de cobertura exacta más conocidos incluyen el mosaico , el problema de las n reinas y el Sudoku .

El nombre de enlaces de baile , que fue sugerido por Donald Knuth , proviene de la forma en que funciona el algoritmo, ya que las iteraciones del algoritmo hacen que los enlaces "bailen" con 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, pero es su artículo el que la ha popularizado.

Implementación

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 del algoritmo X.

Ideas principales

La idea de DLX se basa en la observación de que en una lista circular de nodos doblemente enlazados , 

x.left.right ← x.right;
x.right.left ← x.left;

eliminará el nodo x de la lista, mientras que 

x.left.right ← x;
x.right.left ← x;

restaurará la posición de x en la lista, asumiendo que x.right y x.left se han dejado sin modificar. 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 gastaría una cantidad excesiva de tiempo buscando unos. Al seleccionar una columna, se tuvo que buscar 1 en toda la matriz. Al seleccionar una fila, se tuvo que buscar 1 en una columna completa. Después de seleccionar una fila, esa fila y varias columnas debían buscarse por 1. Para mejorar este tiempo de búsqueda desde la 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 el 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 enlazados.

Encabezamiento

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 consta de todas las columnas que aún existen en la matriz.

Finalmente, cada encabezado de columna puede rastrear opcionalmente 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 recuento de nodos bajo es una heurística que mejora el rendimiento en algunos casos, pero no es esencial para el algoritmo.

Explorador

En el algoritmo X, las filas y columnas se eliminan y restauran regularmente 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 se puede resolver y debe retroceder. Cuando se produce una eliminación, se eliminan todas las columnas para las que 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 llenado 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 contiene un 1, recorra la fila y elimínela de otras columnas (esto hace que esas filas sean inaccesibles y es como se previenen los conflictos). Repita la eliminación de esta columna para cada columna en la que la fila seleccionada contenga un 1. Este orden garantiza que cualquier nodo eliminado se elimine exactamente una vez y en un orden predecible, de modo que pueda retroceder adecuadamente. Si la matriz resultante no tiene columnas, entonces todas se han llenado y las filas seleccionadas forman la solución.

Retroceso

Para retroceder, el proceso anterior debe invertirse utilizando el segundo algoritmo indicado anteriormente. Un requisito para usar ese algoritmo es que el retroceso debe realizarse como una reversión exacta de las eliminaciones. El artículo de Knuth ofrece una imagen clara de estas relaciones y cómo funciona la eliminación y reinserción del nodo, y proporciona una ligera relajación de esta limitación.

Restricciones opcionales

También es posible resolver problemas de una sola cubierta en los que una restricción particular es opcional, pero no se puede satisfacer más de una vez. Dancing Links los acomoda con columnas primarias que deben llenarse 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 usa la heurística del mínimo uno en una columna, entonces debe verificarse 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, solo se puede ocupar una vez.

Ver también

Referencias

enlaces externos