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 de unión-búsqueda , que también mantiene una partición en conjuntos disjuntos pero en la que las operaciones fusionan pares de conjuntos. En algunas aplicaciones del refinamiento de particiones, como la búsqueda lexicográfica en amplitud , la estructura de datos mantiene también un ordenamiento de los conjuntos en la partición.
El refinamiento de particiones constituye un componente clave de varios algoritmos eficientes en gráficos y autómatas finitos , incluida la minimización de DFA , el algoritmo Coffman-Graham para programación paralela y la búsqueda lexicográfica en amplitud de gráficos. [1] [2] [3]
Un algoritmo de refinamiento de particiones mantiene una familia de conjuntos disjuntos S i . Al comienzo del algoritmo, esta familia contiene un único conjunto de todos los elementos de la estructura de datos. En cada paso del algoritmo, se presenta un conjunto X al algoritmo, y cada conjunto S i de la familia que contiene miembros de X se divide en dos conjuntos, la intersección S i ∩ X y la diferencia S i \ X .
Un algoritmo de este tipo se puede implementar de manera eficiente manteniendo estructuras de datos que representen la siguiente información: [4] [5]
Para realizar una operación de refinamiento, el algoritmo recorre los elementos del conjunto X dado . Para cada elemento x , encuentra el conjunto S i que contiene a x y comprueba si ya se ha iniciado un segundo conjunto para S i ∩ X. Si no, crea el segundo conjunto y añade 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, el algoritmo elimina 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 inicial del nuevo conjunto. 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 a partir de él, e informa que ambos conjuntos se han formado recientemente mediante la operación de refinamiento.
El tiempo necesario para realizar una única operación de refinamiento de esta manera es O (| X |) , independiente del número de elementos de la familia de conjuntos y también independiente del número total de conjuntos de la estructura de datos. Por lo tanto, el tiempo necesario para una secuencia de refinamientos es proporcional al tamaño total de los conjuntos entregados al algoritmo en cada paso de refinamiento.
Una aplicación temprana del refinamiento de particiones fue en un algoritmo de Hopcroft (1971) para la minimización de DFA . En este problema, se da como entrada un autómata finito determinista y se debe encontrar un autómata equivalente con la menor cantidad 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 se elige uno de los subconjuntos S i y uno de los símbolos de entrada x del autómata, y los subconjuntos de estados se refinan en estados para los cuales una transición etiquetada x conduciría a S i , y estados para los cuales una transición x conduciría a algún otro lugar. Cuando un conjunto S i que ya ha sido elegido se divide mediante un refinamiento, sólo es necesario elegir nuevamente uno de los dos conjuntos resultantes (el más pequeño de los dos); de esta manera, cada estado participa en los conjuntos X durante O ( s log n ) pasos de refinamiento y el algoritmo general toma un 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 la partición en una implementación eficiente del algoritmo Coffman-Graham para la programación paralela. Sethi demostró que se podía utilizar para construir una clasificación topológica ordenada lexicográficamente de un grafo acíclico dirigido dado en tiempo lineal; este ordenamiento topológico lexicográfico es uno de los pasos clave del algoritmo Coffman-Graham. En esta aplicación, los elementos de los conjuntos disjuntos son vértices del grafo de entrada y los conjuntos X utilizados 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 simplemente el número de aristas del grafo, el algoritmo toma tiempo lineal en el número de aristas, su tamaño de entrada. [7]
El refinamiento de particiones también constituye un paso clave en la búsqueda lexicográfica en amplitud , un algoritmo de búsqueda de grafos con aplicaciones en el reconocimiento de grafos cordales y varias otras clases importantes de grafos. Nuevamente, los elementos del conjunto disjunto son vértices y el conjunto X representa conjuntos de vecinos , por lo que el algoritmo toma tiempo lineal. [8] [9]