stringtranslate.com

Algoritmo X de Knuth

El algoritmo X es un algoritmo para resolver el problema de cobertura exacta . Es un algoritmo recursivo , no determinista , de profundidad y de retroceso sencillo 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 cobertura exacta se representa en el algoritmo X mediante una matriz de incidencia A que consta de 0 y 1. El objetivo es seleccionar un subconjunto de las filas de modo que el dígito 1 aparezca en cada columna exactamente una vez.

El algoritmo X funciona de la siguiente manera:

  1. Si la matriz A no tiene columnas, la solución parcial actual es una solución válida; finalizar exitosamente.
  2. De lo contrario, elija una columna c ( de forma determinista ).
  3. Elija una fila r tal que A r , c = 1 ( no determinísticamente ).
  4. Incluya la fila r en la solución parcial.
  5. 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.
  6. Repita este algoritmo recursivamente en la matriz reducida A.


La elección no determinista de r significa que el algoritmo recurre sobre subalgoritmos independientes; cada subalgoritmo hereda la matriz actual A , pero la reduce con respecto a una fila diferente r . 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 las k filas elegidas. El backtracking es el proceso de recorrer el árbol en preorden, comenzando por 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 la cantidad de iteraciones, Knuth sugiere que el algoritmo de elección de columnas seleccione una columna con la menor cantidad de 1.

Ejemplo

Por ejemplo, considere 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 cantidad más baja de 1 en cualquier columna es dos. La columna 1 es la primera columna con dos 1 y, por lo tanto, se selecciona (de manera determinista):

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 pasa a la primera rama en el nivel 1…

Nivel 1: Seleccionar 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:
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 se deben eliminar 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: El número más bajo de 1 en cualquier columna es cero y la columna 2 es la primera columna con cero 1:
Por lo tanto, esta rama del algoritmo finaliza sin éxito.
El algoritmo pasa a la siguiente rama en el nivel 1…
Nivel 1: Seleccionar 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:
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 se deben eliminar 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: el número más bajo de 1 en cualquier columna es uno. La columna 5 es la primera columna con un 1 y, por lo tanto, se selecciona (de manera 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: Seleccionar 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:
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: el número más bajo de 1 en cualquier columna es uno. La columna 2 es la primera columna con un 1 y, por lo tanto, se selecciona (de manera 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: Seleccionar 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:
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 que esta rama del algoritmo finaliza exitosamente.
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 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: S * = { B , D , F }.

Implementaciones

El objetivo principal de Knuth al describir el algoritmo X era 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 usa la representación matricial del problema de cobertura exacta , implementado como listas doblemente enlazadas de los 1 de la matriz: cada elemento 1 tiene un enlace con el 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 dispersos, esta representación suele ser mucho más eficiente tanto en tamaño como en tiempo de procesamiento requerido. DLX luego usa enlaces danzantes para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) de manera eficiente las suposiciones erróneas. [1]

Véase también

Referencias

  1. ^ ab Knuth, Donald (2000). "Enlaces danzantes". arXiv : cs/0011047 .
  2. ^ Banerjee, Bikramjit; Kraemer, Landon; Lyle, Jeremy (4 de julio de 2010). "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.

Enlaces externos