Algoritmo de enumeración

En informática , un algoritmo de enumeración es un algoritmo que enumera las respuestas a un problema computacional . Formalmente, un algoritmo de este tipo se aplica a problemas que toman una entrada y producen una lista de soluciones, de manera similar a los problemas de funciones . Para cada entrada, el algoritmo de enumeración debe producir la lista de todas las soluciones, sin duplicados, y luego detenerse. El rendimiento de un algoritmo de enumeración se mide en términos del tiempo requerido para producir las soluciones, ya sea en términos del tiempo total requerido para producir todas las soluciones, o en términos del retraso máximo entre dos soluciones consecutivas y en términos de un tiempo de preprocesamiento , contado como el tiempo antes de generar la primera solución. Esta complejidad se puede expresar en términos del tamaño de la entrada, el tamaño de cada salida individual o el tamaño total del conjunto de todas las salidas, de manera similar a lo que se hace con los algoritmos sensibles a la salida .

Definiciones formales

Un problema de enumeración se define como una relación sobre cadenas de un alfabeto arbitrario : ${\estilo de visualización P}$ ${\estilo de visualización R}$ ${\estilo de visualización \Sigma}$

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}$

Un algoritmo resuelve si para cada entrada el algoritmo produce la secuencia (posiblemente infinita) tal que no tiene duplicados y si y solo si . El algoritmo debería detenerse si la secuencia es finita. ${\estilo de visualización P}$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización y}$ $z\en y$ $(x,z)\en R$ ${\estilo de visualización y}$

Clases de complejidad comunes

Los problemas de enumeración se han estudiado en el contexto de la teoría de la complejidad computacional y se han introducido varias clases de complejidad para dichos problemas.

Una clase muy general de este tipo es EnumP , ^[1] la clase de problemas para los que se puede comprobar la exactitud de una posible salida en tiempo polinomial en la entrada y la salida. Formalmente, para un problema de este tipo, debe existir un algoritmo A que tome como entrada la entrada del problema x , la salida candidata y , y resuelva el problema de decisión de si y es una salida correcta para la entrada x , en tiempo polinomial en x e y . Por ejemplo, esta clase contiene todos los problemas que equivalen a enumerar los testigos de un problema en la clase NP .

Otras clases que se han definido incluyen las siguientes. En el caso de problemas que también están en EnumP , estos problemas se ordenan de menos a más específicos:

Polinomio de salida , la clase de problemas cuya salida completa se puede calcular en tiempo polinomial.
Tiempo polinomial incremental , la clase de problemas donde, para todo i , la i -ésima salida se puede producir en tiempo polinomial en el tamaño de entrada y en el número i .
Retardo polinomial , la clase de problemas donde el retraso entre dos salidas consecutivas es polinomial en la entrada (e independiente de la salida).
Retardo fuertemente polinomial : clase de problemas en los que el retardo antes de cada salida es polinomial en tamaño de esta salida específica (e independiente de la entrada o de las otras salidas). Generalmente se supone que el preprocesamiento es polinomial.
Retardo constante : clase de problemas en los que el retardo antes de cada salida es constante, es decir, independiente de la entrada y la salida. Generalmente se supone que la fase de preprocesamiento es polinómica en la entrada.

Técnicas comunes

Retroceso : la forma más sencilla de enumerar todas las soluciones es explorando sistemáticamente el espacio de resultados posibles ( dividándolo en cada paso sucesivo).^[2] Sin embargo, realizar esto puede no dar buenas garantías sobre el retraso, es decir, un algoritmo de retroceso puede pasar mucho tiempo explorando partes del espacio de resultados posibles que no dan lugar a una solución completa.
Búsqueda con linterna : esta técnica mejora el retroceso explorando el espacio de todas las soluciones posibles pero resolviendo en cada paso el problema de si la solución parcial actual puede extenderse a una solución parcial.^[1]Si la respuesta es no, entonces el algoritmo puede retroceder inmediatamente y evitar perder tiempo, lo que hace que sea más fácil mostrar garantías sobre el retraso entre dos soluciones completas cualesquiera. En particular, esta técnica se aplica bien aproblemasautorreducibles
Cierre bajo operaciones de conjuntos : Si deseamos enumerar la unión disjunta de dos conjuntos, entonces podemos resolver el problema enumerando el primer conjunto y luego el segundo conjunto. Si la unión no es disjunta pero los conjuntos pueden enumerarse en orden ordenado , entonces la enumeración puede realizarse en paralelo en ambos conjuntos mientras se eliminan los duplicados sobre la marcha. Si la unión no es disjunta y ambos conjuntos no están ordenados, entonces los duplicados pueden eliminarse a expensas de un mayor uso de memoria, por ejemplo, utilizando una tabla hash . Del mismo modo, el producto cartesiano de dos conjuntos puede enumerarse de manera eficiente enumerando un conjunto y uniendo cada resultado con todos los resultados obtenidos al enumerar el segundo paso.

Ejemplos de problemas de enumeración

El problema de enumeración de vértices , donde se nos da un politopo descrito como un sistema de desigualdades lineales y debemos enumerar los vértices del politopo.
Enumeración de las transversales mínimas de un hipergrafo . Este problema está relacionado con la dualización monótona y está conectado a muchas aplicaciones en la teoría de bases de datos y la teoría de grafos . ^[3]
Enumeración de las respuestas a una consulta de base de datos , por ejemplo, una consulta conjuntiva o una consulta expresada en un segundo orden monádico . En la teoría de bases de datos se han descrito consultas conjuntivas que podrían enumerarse con preprocesamiento lineal y retardo constante . ^[4]
El problema de enumerar camarillas máximas en un gráfico de entrada, por ejemplo, con el algoritmo de Bron-Kerbosch
Listado de todos los elementos de estructuras como matroides y greedoides
Varios problemas sobre gráficos, por ejemplo, enumerar conjuntos independientes , caminos , cortes , etc.
Enumerar las asignaciones satisfactorias de representaciones de funciones booleanas , por ejemplo, una fórmula booleana escrita en forma normal conjuntiva o forma normal disyuntiva , un diagrama de decisión binario como un OBDD , o un circuito booleano en clases restringidas estudiadas en la compilación de conocimientos , por ejemplo, NNF . ^[5]

Conexión con la teoría de la computabilidad

La noción de algoritmos de enumeración también se utiliza en el campo de la teoría de la computabilidad para definir algunas clases de alta complejidad como RE , la clase de todos los problemas enumerables recursivamente . Esta es la clase de conjuntos para los que existe un algoritmo de enumeración que producirá todos los elementos del conjunto: el algoritmo puede ejecutarse indefinidamente si el conjunto es infinito, pero cada solución debe ser producida por el algoritmo después de un tiempo finito.

Referencias

^ ab Strozecki, Yann; Mary, Arnaud (2019). "Enumeración eficiente de soluciones producidas por operaciones de cierre". Matemáticas discretas y ciencias de la computación teórica . 21 (3). doi :10.23638/DMTCS-21-3-22.
^ Read, Ronald C. ; Tarjan, Robert E. (1975). "Límites en algoritmos de retroceso para ciclos de listado, rutas y árboles de expansión". Redes . 5 (3): 237–252. doi :10.1002/net.1975.5.3.237.
^ Hagen, Matthias (2008). Problemas de complejidad computacional y algorítmica de MONET. Göttingen: Cuvillier. ISBN 9783736928268.
^ Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). Duparc, Jacques; Henzinger, Thomas A. (eds.). "Sobre consultas conjuntivas acíclicas y enumeración de retardo constante". Lógica informática . Apuntes de clase en informática. 4646. Springer Berlin Heidelberg: 208–222. doi :10.1007/978-3-540-74915-8_18. ISBN . 9783540749158.
^ Marquis, P.; Darwiche, A. (2002). "Un mapa de compilación de conocimientos". Revista de investigación en inteligencia artificial . 17 : 229–264. arXiv : 1106.1819 . doi :10.1613/jair.989. S2CID 9919794.