Cola de cubo

Una cola de depósito es una estructura de datos que implementa el tipo de datos abstractos de cola de prioridad : mantiene una colección dinámica de elementos con prioridades numéricas y permite un acceso rápido al elemento con prioridad mínima (o máxima). En la cola de depósitos, las prioridades deben ser números enteros y es particularmente adecuada para aplicaciones en las que las prioridades tienen un rango pequeño. ^[1] Una cola de depósitos tiene la forma de una matriz de depósitos: una estructura de datos de matriz , indexada por prioridades, cuyas celdas contienen colecciones de elementos con la misma prioridad entre sí. Con esta estructura de datos, la inserción de elementos y los cambios de su prioridad toman un tiempo constante . Buscar y eliminar el elemento de prioridad mínima lleva un tiempo proporcional al número de depósitos o, manteniendo un puntero al depósito encontrado más recientemente, en un tiempo proporcional a la diferencia de prioridades entre operaciones sucesivas.

La cola de depósitos es el análogo de cola de prioridad de la clasificación por casilleros (también llamada clasificación de depósitos), un algoritmo de clasificación que coloca elementos en depósitos indexados por sus prioridades y luego concatena los depósitos. El uso de una cola de depósitos como cola de prioridad en una clasificación por selección proporciona una forma de algoritmo de clasificación por casillero. ^[2] Las colas de depósito también se denominan colas de prioridad de depósito ^[3] o colas de prioridad de altura limitada . ^[1] Cuando se utilizan para aproximaciones cuantificadas a prioridades de números reales , también se denominan colas de prioridad desordenadas ^[4] o colas de pseudoprioridad . ^[5] Están estrechamente relacionados con la cola de calendario , una estructura que utiliza una matriz similar de depósitos para una priorización exacta por números reales.

Las aplicaciones de la cola de cubos incluyen el cálculo de la degeneración de un gráfico , algoritmos rápidos para caminos más cortos y caminos más anchos para gráficos con pesos que son enteros pequeños o ya están ordenados, y algoritmos de aproximación codiciosos para el problema de cobertura de conjuntos . La versión cuantificada de la estructura también se ha aplicado a la programación ^[2] y a los cubos de marcha en gráficos por computadora . ^[4] El primer uso de la cola de cubos ^[6] fue en un algoritmo de ruta más corta por Dial (1969). ^[7]

Operación

Estructura de datos básica

Una cola de depósito puede manejar elementos con prioridades enteras en el rango de 0 o 1 hasta algún límite conocido $C$ , y operaciones que insertan elementos, cambian la prioridad de elementos o extraen (buscan y eliminan) el elemento que tiene el mínimo (o máxima) prioridad. Consiste en una matriz $A$ de estructuras de datos contenedoras ; en la mayoría de las fuentes, estos contenedores son listas doblemente enlazadas, pero también podrían ser matrices dinámicas ^[3] o conjuntos dinámicos . El contenedor en la $p$ -ésima celda de la matriz $A [p]$ almacena la colección de elementos cuya prioridad es $p$ .

Una cola de depósito puede manejar las siguientes operaciones:

Para insertar un elemento $x$ con prioridad $p$ , agregue $x$ al contenedor en $A [p]$ .
Para cambiar la prioridad de un elemento, elimínelo del contenedor para su prioridad anterior y vuelva a insertarlo en el contenedor para su nueva prioridad.
Para extraer un elemento con prioridad mínima o máxima, realice una búsqueda secuencial en la matriz para encontrar el primer o último contenedor no vacío, respectivamente, elija un elemento arbitrario de este contenedor y elimínelo del contenedor.

De esta manera, las inserciones y cambios de prioridad toman un tiempo constante, y extraer el elemento de prioridad mínima o máxima toma tiempo $O (C)$ . ^[1]^[6]^[8]

Optimizaciones

Como optimización, la estructura de datos puede iniciar cada búsqueda secuencial de un depósito no vacío en el depósito no vacío encontrado más recientemente en lugar de al inicio de la matriz. Esto se puede hacer de dos maneras diferentes: perezoso (retrasando estas búsquedas secuenciales hasta que sean necesarias) o ansioso (haciendo las búsquedas con anticipación). La elección de cuándo realizar la búsqueda afecta cuál de las operaciones de la estructura de datos se ralentiza por estas búsquedas. La versión original de la estructura de Dial utilizaba una búsqueda diferida. Esto se puede hacer manteniendo un índice $L$ que sea un límite inferior de la prioridad mínima de cualquier elemento actualmente en la cola. Al insertar un nuevo elemento, $L$ debe actualizarse al mínimo de su valor anterior y la prioridad del nuevo elemento. Al buscar el elemento de prioridad mínima, la búsqueda puede comenzar en $L$ en lugar de cero, y después de la búsqueda, $L$ debe dejarse igual a la prioridad encontrada en la búsqueda. ^[7]^[9] Alternativamente, la versión ansiosa de esta optimización mantiene $L$ actualizado para que siempre apunte al primer depósito que no esté vacío. Al insertar un nuevo elemento con una prioridad menor que $L$ , la estructura de datos establece $L$ en la nueva prioridad, y al eliminar el último elemento de un depósito con prioridad $L$ , realiza una búsqueda secuencial a través de índices más grandes hasta encontrar un depósito que no esté vacío. y estableciendo $L$ como la prioridad del depósito resultante. ^[1]

En cualquiera de estas dos variaciones, cada búsqueda secuencial toma un tiempo proporcional a la diferencia entre los valores antiguos y nuevos de $L.$ Esto podría ser significativamente más rápido que el tiempo límite $O (C)$ para las búsquedas en la versión no optimizada de la estructura de datos. En muchas aplicaciones de colas de prioridad, como el algoritmo de Dijkstra , las prioridades mínimas forman una secuencia monótona , lo que permite utilizar una cola de prioridad monótona . En estas aplicaciones, tanto para las variaciones perezosas como para las entusiastas de la estructura optimizada, las búsquedas secuenciales de depósitos no vacíos cubren rangos disjuntos de depósitos. Debido a que cada segmento se encuentra como máximo en uno de estos rangos, su número de pasos suma como máximo $C$ . Por lo tanto, en estas aplicaciones, el tiempo total para una secuencia de $n$ operaciones es $O (n + C)$ , en lugar del límite de tiempo $O (nC)$ más lento que resultaría sin esta optimización. ^[9] Se puede aplicar una optimización correspondiente en aplicaciones donde se utiliza una cola de depósito para encontrar elementos de máxima prioridad, pero en este caso debe mantener un índice que limite la prioridad máxima y la búsqueda secuencial de un elemento no vacío. El cubo debe proceder hacia abajo desde este límite superior. ^[10]

Se puede utilizar otra optimización (ya proporcionada por Dial 1969) para ahorrar espacio cuando las prioridades son monótonas y, durante el transcurso de un algoritmo, siempre caen dentro de un rango de valores $de r$ en lugar de extenderse a todo el rango de 0 a $C.$ En este caso, se puede indexar la matriz por el módulo de prioridades $r$ en lugar de por sus valores reales. La búsqueda del elemento de mínima prioridad siempre debe comenzar por el mínimo anterior, para evitar prioridades superiores al mínimo pero con módulos inferiores. En particular, esta idea se puede aplicar en el algoritmo de Dijkstra en gráficos cuyas longitudes de aristas son números enteros en el rango de 1 a $r$ . ^[8]

Debido a que la creación de una nueva cola de depósitos implica inicializar una serie de depósitos vacíos, este paso de inicialización lleva un tiempo proporcional al número de prioridades. En cambio , una variación de la cola de depósitos descrita por Donald B. Johnson en 1981 almacena solo los depósitos no vacíos en una lista vinculada, ordenados por sus prioridades, y utiliza un árbol de búsqueda auxiliar para encontrar rápidamente la posición en esta lista vinculada para cualquier nuevo cubos. Se necesita tiempo $O (log log C)$ para inicializar esta estructura variante, tiempo constante para encontrar un elemento con prioridad mínima o máxima, y tiempo $O (log log D)$ para insertar o eliminar un elemento, donde $D$ es la diferencia entre los más cercanos. prioridades más pequeñas y más grandes a la prioridad del elemento insertado o eliminado. ^[11]

Ejemplo

Por ejemplo, considere una cola de depósitos con cuatro prioridades, los números 0, 1, 2 y 3. Consiste en una matriz cuyas cuatro celdas contienen cada una una colección de elementos, inicialmente vacíos. A los efectos de este ejemplo, se puede escribir como una secuencia entre corchetes de cuatro conjuntos: . Considere una secuencia de operaciones en la que insertamos dos elementos y con la misma prioridad 1, insertamos un tercer elemento con prioridad 3, cambiamos la prioridad de a 3 y luego realizamos dos extracciones del elemento de prioridad mínima. $A$ $A$ $A=[\emptyset,\emptyset,\emptyset,\emptyset]$ $x$ $y$ $z$ $x$

Después de insertar con prioridad 1, . $x$ $A=[\emptyset,\{x\},\emptyset,\emptyset]$
Después de insertar con prioridad 1, . $y$ $A=[\emptyset,\{x,y\},\emptyset,\emptyset]$
Después de insertar z con prioridad 3 ,. $A=[\emptyset,\{x,y\},\emptyset,\{z\}]$
Cambiar la prioridad de x de 1 a tres implica eliminarlo y agregarlo , después de lo cual . $A[1]$ $A[3]$ $A=[\emptyset,\{y\},\emptyset,\{x,z\}]$
Al extraer el elemento de prioridad mínima, en la versión básica de la cola del depósito, busca desde el principio para encontrar su primer elemento no vacío: está vacío pero , un conjunto no vacío. Elige un elemento arbitrario de este conjunto (el único elemento, ) como elemento de prioridad mínima. Quitar de la estructura las hojas . $A$ $A[0]$ $A[1]=\{y\}$ $y$ $y$ $A=[\emptyset,\emptyset,\emptyset,\{x,z\}]$
La segunda operación de extracción, en la versión básica de la cola del depósito, busca nuevamente desde el inicio de la matriz: , , no vacía . En las variantes mejoradas de la cola de depósitos, esta búsqueda comienza en la última posición que no estaba vacía, . En cualquier caso, se encuentra que es el primer conjunto no vacío. Uno de sus elementos se elige arbitrariamente como elemento de mínima prioridad; por ejemplo, podría ser elegido. Este elemento se elimina, quedando . $A[0]=\emptyset$ $A[1]=\emptyset$ $A[2]=\emptyset$ $A[3]={}$ $A[1]$ $A[3]=\{x,z\}$ $z$ $A=[\emptyset,\emptyset,\emptyset,\{x\}]$

Aplicaciones

Degeneración gráfica

Se puede utilizar una cola de depósitos para mantener los vértices de un gráfico no dirigido , priorizados por sus grados , y encontrar y eliminar repetidamente el vértice de grado mínimo. ^[1] Este algoritmo codicioso se puede utilizar para calcular la degeneración de un gráfico dado, igual al mayor grado de cualquier vértice en el momento de su eliminación. El algoritmo toma tiempo lineal , con o sin la optimización que mantiene un límite inferior en la prioridad mínima, porque cada vértice se encuentra en el tiempo proporcional a su grado y la suma de todos los grados de los vértices es lineal en el número de aristas del gráfico. ^[12]

Algoritmo de Dial para caminos más cortos.

En el algoritmo de Dijkstra para caminos más cortos en gráficos dirigidos con pesos de borde que son enteros positivos, las prioridades son monótonas, ^[13] y se puede usar una cola de cubos monótona para obtener un límite de tiempo de $O (m + dc)$ , donde $m$ es el número de bordes, $d$ es el diámetro de la red y $c$ es el costo máximo (entero) del enlace. ^[9]^[14] Esta variante del algoritmo de Dijkstra también se conoce como algoritmo de Dial , ^[9] en honor a Robert B. Dial, quien lo publicó en 1969. ^[7] La misma idea también funciona, utilizando una cola de cubos cuantificada, para gráficos con pesos de borde reales positivos cuando la relación entre el peso máximo y el mínimo es como máximo $c$ . ^[15] En esta versión cuantificada del algoritmo, los vértices se procesan fuera de orden, en comparación con el resultado con una cola de prioridad no cuantificada, pero aún se encuentran las rutas más cortas correctas. ^[5] En estos algoritmos, las prioridades solo abarcarán un rango de ancho $c + 1$ , por lo que la optimización modular se puede utilizar para reducir el espacio a $O (n + c)$ . ^[8]^[14]

Se puede utilizar una variante del mismo algoritmo para el problema del camino más amplio . En combinación con métodos para dividir rápidamente pesos de borde no enteros en subconjuntos a los que se les pueden asignar prioridades enteras, conduce a soluciones en tiempo casi lineal para la versión de fuente única y destino único del problema de ruta más amplia. ^[dieciséis]

Cubierta codiciosa

El problema de la cobertura de conjuntos tiene como entrada una familia de conjuntos . El resultado debe ser una subfamilia de estos conjuntos, con la misma unión que la familia original, incluyendo la menor cantidad de conjuntos posible. Es NP-duro , pero tiene un algoritmo de aproximación codicioso que logra una relación de aproximación logarítmica, esencialmente la mejor posible a menos que P = NP . ^[17] Este algoritmo de aproximación selecciona su subfamilia eligiendo repetidamente un conjunto que cubra el máximo número posible de elementos restantes descubiertos. ^[18] Un ejercicio estándar en el diseño de algoritmos solicita una implementación de este algoritmo que tome un tiempo lineal en el tamaño de entrada, que es la suma de los tamaños de todos los conjuntos de entrada. ^[19]

Esto se puede resolver utilizando una cola de conjuntos de conjuntos en la familia de entrada, priorizados por la cantidad de elementos restantes que cubren. Cada vez que el algoritmo codicioso elige un conjunto como parte de su salida, los elementos del conjunto recién cubiertos deben restarse de las prioridades de los otros conjuntos que los cubren; en el transcurso del algoritmo, el número de estos cambios de prioridades es solo la suma de los tamaños de los conjuntos de entrada. Las prioridades son números enteros monótonamente decrecientes, cuyo límite superior es el número de elementos a cubrir. Cada elección del algoritmo codicioso implica encontrar el conjunto con la máxima prioridad, lo que se puede hacer escaneando hacia abajo a través de los depósitos de la cola de depósitos, comenzando desde el valor máximo anterior más reciente. El tiempo total es lineal en el tamaño de entrada. ^[10]

Planificación

Las colas de depósitos se pueden utilizar para programar tareas con fechas límite, por ejemplo, en el reenvío de paquetes de datos de Internet con garantías de calidad de servicio . Para esta aplicación, los plazos deben cuantificarse en intervalos discretos, y las tareas cuyos plazos caen en el mismo intervalo se consideran de prioridad equivalente. ^[2]

Se ha aplicado una variación de la estructura de datos de la cola de depósitos cuantificados, la cola de calendario , a la programación de simulaciones de eventos discretos , donde los elementos de la cola son eventos futuros priorizados por el tiempo dentro de la simulación en el que deberían ocurrir los eventos. En esta aplicación, el orden de los eventos es fundamental, por lo que las prioridades no se pueden aproximar. Por lo tanto, la cola del calendario realiza búsquedas del elemento de prioridad mínima de una manera diferente a la cola del depósito: en la cola del depósito, se puede devolver cualquier elemento del primer depósito que no esté vacío, pero en su lugar la cola del calendario busca todos los elementos en ese depósito para determinar cuál de ellos tiene la prioridad no cuantificada más pequeña. Para mantener estas búsquedas rápidas, esta variación intenta mantener la cantidad de depósitos proporcional a la cantidad de elementos, ajustando la escala de cuantificación y reconstruyendo la estructura de datos cuando se desequilibra. Las colas de calendario pueden ser más lentas que las colas de depósitos en el peor de los casos (cuando muchos elementos terminan en el mismo depósito más pequeño), pero son rápidas cuando los elementos se distribuyen uniformemente entre los depósitos, lo que hace que el tamaño promedio del depósito sea constante. ^[20]^[21]

marcha rapida

En matemáticas aplicadas y métodos numéricos para la solución de ecuaciones diferenciales , se han utilizado colas de prioridad desordenadas para priorizar los pasos del método de marcha rápida para resolver problemas de valores límite de la ecuación de Eikonal , utilizada para modelar la propagación de ondas . Este método encuentra los momentos en los que un límite en movimiento cruza un conjunto de puntos discretos (como los puntos de una cuadrícula de números enteros) utilizando un método de priorización que se asemeja a una versión continua del algoritmo de Dijkstra , y su tiempo de ejecución está dominado por su cola de prioridad. de estos puntos. Se puede acelerar al tiempo lineal redondeando las prioridades utilizadas en este algoritmo a números enteros y usando una cola de depósitos para estos números enteros. Al igual que en los algoritmos de Dijkstra y Dial, las prioridades son monótonas, por lo que la marcha rápida puede utilizar la optimización monótona de la cola de depósitos y su análisis. Sin embargo, la discretización introduce algunos errores en los cálculos resultantes. ^[4]

Ver también

Soft heap , una forma diferente de acelerar las colas de prioridad mediante el uso de prioridades aproximadas

Referencias

^ abcde Skiena, Steven S. (1998), Manual de diseño de algoritmos, Springer, p. 181, ISBN 9780387948607.
^ abc Figueira, NR (1997), "Una solución para el problema de la cola de prioridad de las disciplinas de servicio ordenadas con fecha límite", Actas de la Sexta Conferencia Internacional sobre Redes y Comunicaciones Informáticas , IEEE Computer Society Press, págs. 320–325, doi :10.1109 /icccn.1997.623330, S2CID 5611516
^ ab Henzinger, Monika ; Noé, Alejandro; Schulz, Christian (2019), "Cortes mínimos exactos de memoria compartida", Simposio internacional de procesamiento distribuido y paralelo IEEE de 2019, IPDPS 2019, Río de Janeiro, Brasil, 20 al 24 de mayo de 2019 , págs. 13 a 22, arXiv : 1808.05458 , doi :10.1109/IPDPS.2019.00013, S2CID 52019258
^ abc Rasch, cristiano; Satzger, Thomas (2009), "Observaciones sobre la implementación O(N) del método de marcha rápida" (PDF) , IMA Journal of Numerical Analysis , 29 (3): 806–813, doi :10.1093/imanum/drm028, MR 2520171
^ ab Robledo, Alicia; Guivant, José E. (2010), "Colas de pseudoprioridad para el desempeño en tiempo real en procesos de programación dinámica aplicados a la planificación de rutas" (PDF) , en Wyeth, Gordon; Upcroft, Ben (eds.), Conferencia de Australasia sobre robótica y automatización
^ ab Edelkamp, Stefan; Schroedl, Stefan (2011), "3.1.1 Estructuras de datos de cubo", Búsqueda heurística: teoría y aplicaciones , Elsevier, págs. 90–92, ISBN 9780080919737. Véase también pág. 157 para conocer la historia y el nombre de esta estructura.
^ abc Dial, Robert B. (1969), "Algoritmo 360: bosque de camino más corto con ordenamiento topológico [H]", Comunicaciones del ACM , 12 (11): 632–633, doi : 10.1145/363269.363610 , S2CID 6754003.
^ abcMehlhorn , Kurt ; Sanders, Peter (2008), "10.5.1 Colas de depósitos", Algoritmos y estructuras de datos: la caja de herramientas básica , Springer, p. 201, ISBN 9783540779773.
^ abcd Bertsekas, Dimitri P. (1991), "Algoritmo de Dial", Optimización de red lineal: algoritmos y códigos , Cambridge, Massachusetts: MIT Press, págs. 72–75, ISBN 0-262-02334-2, SEÑOR 1201582
^ ab Lim, CL; Moffat, Alistair; Wirth, Anthony Ian (2014), "Enfoques perezosos y entusiastas para el problema de la cobertura del decorado", en Thomas, Bruce; Parry, Dave (eds.), Trigésima séptima Conferencia de Informática de Australasia, ACSC 2014, Auckland, Nueva Zelanda, enero de 2014 , CRPIT, vol. 147, Sociedad Australiana de Informática, págs. 19-27. Consulte en particular la Sección 2.4, "Cola de prioridad", p. 22.
^ Johnson, Donald B. (1981), "Una cola de prioridad en la que las operaciones de inicialización y cola toman tiempo $O$ $(log log$ $D$ $"$ ), Teoría de sistemas matemáticos , 15 (4): 295–309, doi :10.1007/BF01786986, MR 0683047, S2CID 35703411
^ Matula, David W .; Beck, LL (1983), "Algoritmos de ordenación, agrupación y coloración de gráficos de menor a último", Journal of the ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826, S2CID 4417741.
^ Varghese, George (2005), Algorítmica de redes: un enfoque interdisciplinario para diseñar dispositivos rápidos en red, Morgan Kaufmann, págs. 78–80, ISBN 9780120884773.
^ ab Festa, Paola (2006), "Algoritmos de ruta más corta", en Resende, Mauricio GC ; Pardalos, Panos M. (eds.), Manual de optimización en telecomunicaciones , Boston: Springer, págs. 185–210, doi :10.1007/978-0-387-30165-5_8; consulte en particular la Sección 8.3.3.6, "Implementación de Dial", págs. 194-195.
^ Mehlhorn & Sanders (2008) (Ejercicio 10.11, p. 201) atribuyen esta idea a un artículo de 1978 de EA Dinic (Yefim Dinitz).
^ Gabow, Harold N .; Tarjan, Robert E. (1988), "Algoritmos para dos problemas de optimización de cuellos de botella", Journal of Algorithms , 9 (3): 411–417, doi :10.1016/0196-6774(88)90031-4, MR 0955149
^ Dinur, Irit ; Steurer, David (2014), "Analytical approach to paralelo repetition", en Shmoys, David B. (ed.), Simposio sobre Teoría de la Computación, STOC 2014, Nueva York, NY, EE. UU., 31 de mayo - 3 de junio de 2014 , ACM, págs. 624–633, arXiv : 1305.1979 , doi : 10.1145/2591796.2591884, MR 3238990, S2CID 15252482
^ Johnson, David S. (1974), "Algoritmos de aproximación para problemas combinatorios", Journal of Computer and System Sciences , 9 (3): 256–278, doi :10.1016/S0022-0000(74)80044-9, MR 0449012
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990], "Ejercicio 35.3-3", Introducción a los algoritmos (3.ª ed.), MIT Press y McGraw-Hill, p. 1122, ISBN 0-262-03384-4
^ Brown, R. (octubre de 1988), "Colas de calendario: una implementación rápida de cola de prioridad para el problema del conjunto de eventos de simulación", Comunicaciones del ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID 32086497 $O(1)$
^ Erickson, K. Bruce; Ladner, Richard E .; LaMarca, Anthony (2000), "Optimización de colas de calendario estático", Transacciones ACM sobre modelado y simulación por computadora , 10 (3): 179–214, doi : 10.1145/361026.361028