stringtranslate.com

Algoritmo X de Knuth

El algoritmo X es un algoritmo para resolver el problema de cobertura exacta . Es un algoritmo de retroceso sencillo, recursivo , no determinista , de profundidad primero , utilizado por Donald Knuth para demostrar una implementación eficiente llamada DLX, que utiliza la técnica de enlaces danzantes . [1] [2]

El problema de cobertura exacto está representado en el algoritmo X mediante una matriz A que consta de 0 y 1. El objetivo es seleccionar un subconjunto de filas de modo 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; terminar exitosamente.
  1. De lo contrario, elija una columna c ( de manera determinista ).
  2. Elija una fila r tal que Ar , c = 1 ( de forma no determinista ).
  3. Incluya la fila r en la solución parcial.
  4. Para cada columna j tal que Ar , 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.
  5. Repita este algoritmo de forma recursiva 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 un nivel k que contiene cada subalgoritmo que corresponde a k filas elegidas. Retroceder es el proceso de atravesar el árbol en orden anticipado, primero 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 elección de columnas seleccione una columna con el menor número de unos.

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 }, dónde:

  • A = {1, 4, 7};
  • B = {1, 4};
  • C = {4, 5, 7};
  • D = {3, 5, 6};
  • mi = {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: el número más bajo de unos en cualquier columna es dos. La columna 1 es la primera columna con dos unos y, por lo tanto, se selecciona (de manera 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 pasa a la primera rama en el nivel 1...

Nivel 1: seleccione 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 eliminarán las filas A , B , C , E y F y se eliminarán las columnas 1, 4 y 7:
Queda la fila D y quedan las columnas 2, 3, 5 y 6:
Paso 1: la matriz no está vacía, por lo que el algoritmo continúa.
Paso 2: el número más bajo de unos en cualquier columna es cero y la columna 2 es la primera columna con cero unos:
Por tanto, esta rama del algoritmo termina sin éxito.
El algoritmo pasa a la siguiente rama en el nivel 1...
Nivel 1: seleccione 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 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 unos 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, está seleccionada (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 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 eliminarán las filas D y E y se eliminarán las columnas 3, 5 y 6:
Queda la fila F y quedan las columnas 2 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 unos 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, está seleccionada (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 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 eliminará la fila F y se eliminarán las columnas 2 y 7:
Paso 1: la matriz está vacía, por lo que esta rama del algoritmo finaliza con éxito.
Cuando se seleccionan las filas B , D y F , la solución final 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 sólo hay una cobertura exacta: S * = { B , D , F }.

Implementaciones

El objetivo principal de Knuth al describir el Algoritmo X fue 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 utiliza la representación matricial del problema de cobertura exacto , 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 toroide ). Debido a que los problemas de cobertura exacta tienden a ser escasos, esta representación suele ser mucho más eficiente tanto en tamaño como en tiempo de procesamiento requerido. Luego, DLX utiliza enlaces dinámicos para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) de manera eficiente las conjeturas erróneas. [1]

Ver también

Referencias

  1. ^ ab Knuth, Donald (2000). "Enlaces de baile". 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