En el diseño y análisis de estructuras de datos , una cola de depósito [1] (también llamada cola de prioridad de depósito [2] o cola de prioridad de altura limitada [3] ) es una cola de prioridad para priorizar elementos cuyas prioridades son números enteros pequeños . Tiene la forma de una matriz de depósitos: una estructura de datos de matriz , indexada por las prioridades, cuyas celdas contienen depósitos de elementos con la misma prioridad entre sí. Con esta estructura de datos, la inserción o eliminación de elementos lleva un tiempo constante. Las búsquedas del elemento de prioridad mínima toman un tiempo proporcional al número de depósitos o, al mantener un puntero al depósito encontrado más recientemente, un tiempo proporcional a la diferencia de prioridades entre los resultados de búsquedas sucesivas.
Cola de depósito | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | cola de prioridad | ||||||||||||||||||||
Inventado | 1969 | ||||||||||||||||||||
Inventado por | Robert Dial | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
La cola de cubos es el análogo de la cola de prioridad de la clasificación de casilleros (también llamada clasificación de cubos), un algoritmo de clasificación que coloca los elementos en cubos indexados por sus prioridades y luego concatena los cubos. El uso de una cola de cubos como cola de prioridad en una clasificación de selección proporciona una forma del algoritmo de clasificación de casillas. [4] Cuando se usa para aproximaciones cuantificadas a prioridades de números reales , también se le ha llamado cola de prioridad desordenada [5] o cola de pseudoprioridad , [6] y está estrechamente relacionada con la estructura de la cola de calendario para la 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 las rutas más cortas y más anchas para gráficos con pesos que son números enteros pequeños o que 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 [4] ya los cubos de marcha en gráficos por ordenador . [5] El primer uso de la cola de cubos [2] fue en un algoritmo de ruta más corta de Dial (1969) . [7]
Operación
Estructura de datos básica
Esta estructura puede manejar las inserciones y eliminaciones de elementos con prioridades enteras en el rango de 0 o 1 a algún límite C conocido , así como operaciones que encuentran el elemento con prioridad mínima (o máxima). Consiste en una matriz A de estructuras de datos de contenedor , donde la celda de matriz A [ p ] almacena la colección de elementos con prioridad p . Puede manejar las siguientes operaciones:
- Para insertar un elemento x con prioridad p , agregue x al contenedor en A [ p ] .
- Para eliminar un elemento x con prioridad p , elimine x del contenedor en A [ p ]
- Para encontrar un elemento con la prioridad mínima o máxima, realice una búsqueda secuencial para encontrar el primer o el último contenedor no vacío, respectivamente, y luego elija un elemento arbitrario de este contenedor.
De esta manera, las inserciones y remociones toman un tiempo constante, y encontrar el elemento de prioridad mínima o máxima toma tiempo O ( C ) . [1] [3]
Optimizaciones
Como optimización, la estructura de datos también puede mantener un índice L que limita la prioridad mínima de un elemento. 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 en cero, y después de la búsqueda, L debe dejarse igual a la prioridad que se encontró en la búsqueda. [3] De esta manera, el tiempo para buscar el elemento de prioridad mínima se reduce a la diferencia entre el límite inferior anterior y su siguiente valor; esta diferencia podría ser significativamente menor que C . En muchas aplicaciones de colas de prioridad monótona como el algoritmo de Dijkstra , las prioridades mínimos forman una sucesión monótona , por lo que las búsquedas secuenciales para cubos no vacíos cubren rangos disjuntos de baldes, y su número de pasos agregan en una serie telescópica a lo sumo 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. [7] Se puede aplicar una optimización correspondiente en aplicaciones donde se usa 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 balde debe proceder hacia abajo desde este límite superior. [8]
Otra optimización (ya dada por Dial 1969 ) se puede utilizar para ahorrar espacio cuando las prioridades son monotónica y, durante todo el curso de un algoritmo, siempre dentro de un intervalo de r valores en lugar de que se extiende sobre toda la gama de 0 a C . En este caso, se puede indexar la matriz por las prioridades módulo r en lugar de por sus valores reales. La búsqueda del elemento de prioridad mínima debe comenzar siempre 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 borde son números enteros en el rango de 1 a r . [1]
Aplicaciones
Degeneración gráfica
Se puede usar una cola de depósito 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. [3] Este algoritmo codicioso se puede utilizar para calcular la degeneración de un gráfico dado. Se necesita 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 vértice es lineal en el número de aristas del gráfico. [9]
Algoritmo de Dial para rutas más cortas
En el algoritmo de Dijkstra para las rutas más cortas en gráficos dirigidos con pesos de borde que son números enteros positivos, se puede usar una cola de cubos para obtener un límite de tiempo de O ( n + m + dc ) , donde n es el número de vértices, 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. [10] Esta variante del algoritmo de Dijkstra también se conoce como algoritmo de Dial , en honor a Robert B. Dial, quien lo publicó en 1969. [7] También se puede utilizar, con una cola de cubos cuantificada, para calcular las rutas más cortas correctas en un gráfico con pesos de borde reales positivos cuando la relación entre el peso máximo y mínimo es como máximo c ; en esta versión del algoritmo, los vértices se procesan fuera de orden, en comparación con el resultado con una cola de prioridad no cuantificada, pero los cambios de orden no afectan los resultados generales. [6] 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 ) . [1] [10]
Se puede utilizar una variante del mismo algoritmo para el problema de la ruta más amplia . 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 de tiempo casi lineal para la versión de destino único de fuente única del problema de la ruta más amplia. [11]
Portada del set codicioso
El problema de la cobertura de conjuntos tiene como entrada una familia de conjuntos , siendo la salida deseada una subfamilia de la menor cantidad posible de conjuntos que tengan la misma unión. Es NP-difícil , 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 . [12] Este algoritmo de aproximación selecciona su subfamilia eligiendo repetidamente un conjunto que cubre el número máximo posible de elementos descubiertos restantes. [13] Un ejercicio estándar en el diseño de algoritmos solicita una implementación de este algoritmo que toma un tiempo lineal en el tamaño de entrada, que es la suma de los tamaños de todos los conjuntos de entrada. [14]
Esto se puede resolver utilizando una cola de conjuntos de conjuntos en la familia de entrada, priorizados por el número 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. Las prioridades son números enteros decrecientes monótonamente, y 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 cubos de la cola de cubos, comenzando desde el valor máximo anterior más reciente. De esta forma, el tiempo total que tarda la estructura de datos en encontrar estos conjuntos es proporcional a la máxima prioridad inicial, que es como máximo el número de elementos a cubrir. [8]
Planificación
Las colas de depósito 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. [4]
Se ha aplicado una variación de la estructura de datos de la cola del depósito cuantificado, la cola del 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 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 de calendario realiza búsquedas para el elemento de prioridad mínima de una manera diferente a una cola de depósito: en la cola de depósito, se puede devolver cualquier elemento del primer depósito no vacío, pero en su lugar, la cola de calendario busca todos los elementos en ese depósito para determinar cuál de ellos tiene la menor prioridad no cuantificada. Para mantener estas búsquedas rápidas, esta variación intenta mantener el número de depósitos proporcional al número 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ósito en el peor de los casos (cuando muchos elementos aterrizan 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 medio del depósito sea constante. [15] [16]
Marcha rápida
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 valor límite de la ecuación de Eikonal , que se utiliza 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 hasta el tiempo lineal redondeando las prioridades utilizadas en este algoritmo a números enteros y utilizando una cola de depósito para estos números enteros. Al igual que en los algoritmos de Dijkstra y Dial, las prioridades son monótonas, por lo que se puede utilizar el análisis telescópico de la cola de cubos. Sin embargo, la discretización introduce algún error en los cálculos resultantes. [5]
Ver también
- Soft heap , una forma diferente de acelerar las colas de prioridad mediante el uso de prioridades aproximadas
Referencias
- ^ a b c d Mehlhorn, Kurt ; Sanders, Peter (2008), "10.5.1 Colas de cubos" , Algoritmos y estructuras de datos: La caja de herramientas básica , Springer, p. 201, ISBN 9783540779773.
- ^ a b Edelkamp, Stefan; Schroedl, Stefan (2011), "3.1.1 Estructuras de datos de depósito" , Búsqueda heurística: teoría y aplicaciones , Elsevier, págs. 90–92, ISBN 9780080919737. Ver también p. 157 para la historia y denominación de esta estructura.
- ^ a b c d Skiena, Steven S. (1998), Manual de diseño de algoritmos , Springer, p. 181, ISBN 9780387948607.
- ^ a b c Figueira, NR (1997), "Una solución para el problema de la cola de prioridad de las disciplinas de servicio ordenadas por fecha límite", Actas de la Sexta Conferencia Internacional sobre Comunicaciones y Redes de Computadoras, IEEE Computer Society Press, págs. 320–325, doi : 10.1109 / icccn .1997.623330
- ^ a b c Rasch, Christian; 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
- ^ a b Robledo, Alicia; Guivant, José E. (2010), "Colas de pseudo prioridad 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 Australasia sobre Robótica y Automatización
- ^ a b c Dial, Robert B. (1969), "Algorithm 360: Shortest-path forest with topological ordering [H]", Communications of the ACM , 12 (11): 632–633, doi : 10.1145 / 363269.363610.
- ^ a b Lim, CL; Moffat, Alistair; Wirth, Anthony Ian (2014), "Enfoques perezosos y ansiosos para el problema de la portada del set" , en Thomas, Bruce; Parry, Dave (eds.), Trigésima séptima Conferencia de Ciencias de la Computación de Australasia, ACSC 2014, Auckland, Nueva Zelanda, enero de 2014 , CRPIT, 147 , Sociedad Australiana de Computación, págs. 19–27. Consulte en particular la Sección 2.4, "Cola de prioridad", pág. 22.
- ^ Matula, David W .; Beck, LL (1983), "Smallest-last ordering and clustering and graph colour algoritmos", Journal of the ACM , 30 (3): 417–427, doi : 10.1145 / 2402.322385 , MR 0709826.
- ^ a b Varghese, George (2005), Algoritmos de red: un enfoque interdisciplinario para diseñar dispositivos de red rápidos , Morgan Kaufmann, págs. 78–80, ISBN 9780120884773.
- ^ 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), "Enfoque analítico de la repetición paralela", en Shmoys, David B. (ed.), Symposium on Theory of Computing, 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
- ^ Johnson, David S. (1974), "Algoritmos de aproximación para problemas combinatorios", Journal of Computer and System Sciences , 9 : 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), "Calendar queues: a fast implementación de la 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
- ^ Erickson, K. Bruce; Ladner, Richard E .; LaMarca, Anthony (2000), "Optimizing static calendar coues", ACM Transactions on Modelling and Computer Simulation , 10 (3): 179–214, doi : 10.1145 / 361026.361028