En el diseño de algoritmos , el refinamiento de particiones es una técnica para representar una partición de un conjunto como una estructura de datos que permite refinar la partición dividiendo sus conjuntos en un número mayor de conjuntos más pequeños. En ese sentido, es dual con la estructura de datos union-find , que también mantiene una partición en conjuntos disjuntos pero en la que las operaciones fusionan pares de conjuntos.
El refinamiento de las particiones forma un componente clave de varios algoritmos eficientes en gráficos y autómatas finitos , incluida la minimización de DFA , el algoritmo de Coffman-Graham para la programación paralela y la búsqueda lexicográfica de gráficos en amplitud primero . [1] [2] [3]
Estructura de datos
Un algoritmo de refinamiento de partición mantiene una familia de conjuntos disjuntos S i . Al comienzo del algoritmo, esta familia contiene un solo conjunto de todos los elementos en la estructura de datos. En cada paso del algoritmo, un conjunto X se presenta al algoritmo, y cada conjunto S i en la familia que contiene miembros de X se divide en dos conjuntos, la intersección S i ∩ X y la diferencia S i \ X .
Dicho algoritmo puede implementarse de manera eficiente manteniendo estructuras de datos que representen la siguiente información: [4] [5]
- La secuencia ordenada de los conjuntos S i en la familia, en una forma como una lista doblemente enlazada que permite insertar nuevos conjuntos en el medio de la secuencia.
- Asociado con cada conjunto S i , una colección de sus elementos de S i , en una forma como una lista doblemente enlazada o una estructura de datos de matriz que permite la eliminación rápida de elementos individuales de la colección. Alternativamente, este componente de la estructura de datos se puede representar almacenando todos los elementos de todos los conjuntos en una sola matriz, ordenados por la identidad del conjunto al que pertenecen, y representando la colección de elementos en cualquier conjunto S i por sus posiciones inicial y final en esta matriz.
- Asociado a cada elemento, el conjunto al que pertenece.
Para realizar una operación de refinamiento, el algoritmo recorre los elementos del conjunto X dado . Para cada uno de estos elementos x , encuentra el conjunto S i que contiene x , y comprueba si ya se ha iniciado un segundo conjunto para S i ∩ X. De lo contrario, crea el segundo conjunto y agrega S i a una lista L de los conjuntos que se dividen mediante la operación. A continuación, independientemente de si se formó un nuevo conjunto, los elimina algoritmo x de S i y lo añade a S i ∩ X . En la representación en la que todos los elementos se almacenan en una única matriz, se puede mover x de un conjunto a otro intercambiando x con el elemento final de S i y luego disminuyendo el índice final de S i y el índice de inicio del nuevo colocar. Finalmente, después de que todos los elementos de X se hayan procesado de esta manera, el algoritmo recorre L , separando cada conjunto actual S i del segundo conjunto que se ha dividido de él, e informa que ambos conjuntos se han formado nuevamente por el refinamiento. operación.
El tiempo para realizar una sola operación de refinamiento de esta manera es O (| X |) , independiente del número de elementos en la familia de conjuntos y también independiente del número total de conjuntos en la estructura de datos. Por lo tanto, el tiempo para una secuencia de refinamientos es proporcional al tamaño total de los conjuntos dados al algoritmo en cada paso de refinamiento.
Aplicaciones
Una de las primeras aplicaciones del refinamiento de particiones fue un algoritmo de Hopcroft (1971) para la minimización de DFA . En este problema, se le da como entrada un autómata finito determinista , y debe encontrar un autómata equivalente con el menor número posible de estados. El algoritmo de Hopcroft mantiene una partición de los estados del autómata de entrada en subconjuntos, con la propiedad de que dos estados cualesquiera en diferentes subconjuntos deben mapearse a diferentes estados del autómata de salida. Inicialmente, hay dos subconjuntos, uno que contiene todos los estados de aceptación del autómata y otro que contiene los estados restantes. En cada paso uno de los subconjuntos S i y uno de los símbolos de entrada Ix del autómata se eligen, y los subconjuntos de estados se refinan en estados para los que una transición marcada x conducirían a S i , y los estados para los que un x - la transición llevaría a otro lugar. Cuando un conjunto S i que ya ha sido elegido es dividido por un refinamiento, sólo uno de los dos conjuntos resultantes (el más pequeño de los dos) necesita ser elegido nuevamente; de esta manera, cada estado participa en los conjuntos X para O ( s log n ) pasos de refinamiento y el algoritmo general toma tiempo O ( ns log n ) , donde n es el número de estados iniciales y s es el tamaño del alfabeto. [6]
Sethi (1976) aplicó el refinamiento de particiones en una implementación eficiente del algoritmo de Coffman-Graham para la programación paralela. Sethi demostró que podría usarse para construir una clase topológica ordenada lexicográficamente de un gráfico acíclico dirigido dado en tiempo lineal; este ordenamiento topológico lexicográfico es uno de los pasos clave del algoritmo de Coffman-Graham. En esta aplicación, los elementos de los conjuntos disjuntos son vértices del gráfico de entrada y los conjuntos X usados para refinar la partición son conjuntos de vecinos de vértices. Dado que el número total de vecinos de todos los vértices es solo el número de aristas en el gráfico, el algoritmo toma tiempo lineal en la cantidad de aristas, su tamaño de entrada. [7]
El refinamiento de las particiones también constituye un paso clave en la búsqueda lexicográfica de amplitud primero , un algoritmo de búsqueda de gráficos con aplicaciones en el reconocimiento de gráficos cordales y varias otras clases importantes de gráficos. Nuevamente, los elementos del conjunto disjunto son vértices y el conjunto X representa conjuntos de vecinos , por lo que el algoritmo toma un tiempo lineal. [8] [9]
Ver también
Referencias
- ^ Paige, Robert; Tarjan, Robert E. (1987), "Tres algoritmos de refinamiento de particiones", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137 / 0216062 , MR 0917035.
- ^ Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Técnicas de refinamiento de particiones: un interesante conjunto de herramientas algorítmicas", International Journal of Foundations of Computer Science , 10 (2): 147-170, doi : 10.1142 / S0129054199000125 , MR 1759929.
- ^ Habib, Michel; Paul, Christophe; Viennot, Laurent (1998), "Una síntesis sobre el refinamiento de particiones: una rutina útil para cadenas, gráficos, matrices booleanas y autómatas", en Morvan, Michel; Meinel, Christoph; Krob, Daniel (eds.), STACS 98: XV Simposio anual sobre aspectos teóricos de la informática París, Francia, 25 al 27 de febrero de 1998, Actas , Notas de conferencias en informática , 1373 , Springer-Verlag, págs. 25–38 , doi : 10.1007 / BFb0028546 , ISBN 978-3-540-64230-5, MR 1650757.
- ^ Valmari, Antti; Lehtinen, Petri (2008), Albers, Susanne ; Weil, Pascal (eds.), Minimización eficiente de DFA con funciones de transición parcial , Leibniz International Proceedings in Informatics (LIPIcs), 1 , Dagstuhl, Alemania: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, págs. 645–656, doi : 10.4230 /LIPIcs.STACS.2008.1328 , ISBN 978-3-939897-06-4, MR 2873773 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Knuutila, Timo (2001), "Re-describir un algoritmo por Hopcroft", Ciencias de la Computación Teórica , 250 (1–2): 333–363, doi : 10.1016 / S0304-3975 (99) 00150-4 , ISSN 0304-3975
- ^ Hopcroft, John (1971), "Un algoritmo n log n para minimizar estados en un autómata finito", Teoría de máquinas y cálculos (Proc. Internat. Sympos., Technion, Haifa, 1971) , Nueva York: Academic Press, págs. 189-196, SR. 0403320.
- ^ Sethi, Ravi (1976), "Gráficos de programación en dos procesadores", SIAM Journal on Computing , 5 (1): 73–82, doi : 10.1137 / 0205005 , MR 0398156.
- ^ Rose, DJ; Tarjan, RE ; Lueker, GS (1976), "Aspectos algorítmicos de la eliminación de vértices en gráficos", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021.
- ^ Corneil, Derek G. (2004), "Primera búsqueda de amplitud lexicográfica - una encuesta", en Hromkovič, Juraj; Nagl, Manfred; Westfechtel, Bernhard (eds.), Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Alemania, 21-23 de junio de 2004, Revised Papers , Lecture Notes in Computer Science , 3353 , Springer-Verlag, págs. 1–19, doi : 10.1007 / 978-3-540-30559-0_1.