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 mayor número de conjuntos más pequeños. En ese sentido, es dual a la estructura de datos 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 de refinamiento de particiones, como la búsqueda lexicográfica de amplitud primero , la estructura de datos mantiene también un orden en los conjuntos de la partición.
El refinamiento de particiones forma 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 la programación paralela y la búsqueda lexicográfica de gráficos en amplitud . [1] [2] [3]
Un algoritmo de refinamiento de partición mantiene una familia de conjuntos disjuntos Si . Al inicio 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 Si de la familia que contiene miembros de X se divide en dos conjuntos, la intersección Si ∩ X y la diferencia Si \ 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 dado X. Para cada elemento x , encuentra el conjunto Si que contiene x y verifica si ya se ha iniciado un segundo conjunto para Si ∩ X. De lo contrario, crea el segundo conjunto y agrega Si a una lista L de conjuntos que se dividen mediante la operación . Luego , independientemente de si se formó un nuevo conjunto, el algoritmo elimina x de Si y lo suma a Si ∩ 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 Si y luego disminuyendo el índice final de Si y el índice inicial 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 Si del segundo conjunto que se ha dividido de él, e informa que ambos conjuntos están recién formados por el refinamiento. operación.
El tiempo 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 en la estructura de datos. Por 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.
Una de las primeras aplicaciones del refinamiento de particiones fue el 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 el menor número de estados posible. 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 subconjuntos diferentes deben asignarse 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 Si 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 Si , y estados para los cuales una x - la transición llevaría a otra parte. Cuando un conjunto Si que ya ha sido elegido se divide mediante un refinamiento, sólo es necesario volver a elegir uno de los dos conjuntos resultantes (el más pequeño de los dos); de esta manera, cada estado participa en los conjuntos X para 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 podría usarse para construir un tipo topológico ordenado 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 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 solo el número de aristas en el gráfico, el algoritmo toma un tiempo lineal en el número de aristas, su tamaño de entrada. [7]
El refinamiento de la partición también constituye un paso clave en la búsqueda lexicográfica en amplitud , 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 tiempo lineal. [8] [9]