Enlaces de baile
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 . [1] Algoritmo X es un 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 Sudoku .
El nombre de enlaces de baile , que fue sugerido por Donald Knuth , se deriva 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, [2] pero es su artículo el que la ha popularizado.
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.
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 unos. 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.
