En la programación del taller de trabajo y el dibujo de gráficos , el algoritmo de Coffman-Graham es un algoritmo , que lleva el nombre de Edward G. Coffman, Jr. y Ronald Graham , para organizar los elementos de un conjunto parcialmente ordenado en una secuencia de niveles. El algoritmo elige una disposición tal que un elemento que viene después de otro en el orden se asigna a un nivel inferior, y de tal manera que cada nivel tiene un número de elementos que no exceda de un ancho fijo unido W . Cuando W = 2 , utiliza el número mínimo posible de niveles distintos, [1] y, en general, utiliza como máximo 2 - 2 /W veces tantos niveles como sea necesario. [2] [3]
Enunciado del problema y aplicaciones
En la versión del problema de programación del taller resuelto por el algoritmo de Coffman-Graham, se le da a uno un conjunto de n trabajos J 1 , J 2 , ..., J n , junto con un sistema de restricciones de precedencia J i < J j requiriendo que el trabajo J i se complete antes de que comience el trabajo J j . Se supone que cada trabajo requiere un tiempo unitario para completarse. La tarea de programación es asignar cada uno de estos trabajos a franjas horarias en un sistema de W procesadores idénticos, minimizando la duración de la asignación (el tiempo desde el comienzo del primer trabajo hasta la finalización del trabajo final). De manera abstracta, las restricciones de precedencia definen un orden parcial en los trabajos, por lo que el problema puede reformularse como uno de asignar los elementos de este orden parcial a niveles (ranuras de tiempo) de tal manera que cada ranura de tiempo tenga como máximo tantos trabajos como procesadores (como máximo W elementos por nivel), respetando las restricciones de precedencia. Esta aplicación fue la motivación original para que Coffman y Graham desarrollaran su algoritmo. [1] [4]
En el marco de dibujo de gráfico en capas descrito por Sugiyama, Tagawa y Toda (1981) [5] la entrada es un gráfico dirigido , y el dibujo de un gráfico se construye en varias etapas: [6] [7]
- Se elige un conjunto de arco de retroalimentación y los bordes de este conjunto se invierten para convertir la entrada en un gráfico acíclico dirigido .
- Los vértices del gráfico reciben coordenadas y enteras de tal manera que, para cada arista, el vértice inicial de la arista tiene una coordenada más alta que el vértice final, con como máximo los vértices W compartiendo la misma coordenada y .
- Los vértices ficticios se introducen dentro de cada borde para que todos los bordes subdivididos conecten pares de vértices que se encuentran en niveles adyacentes del dibujo.
- Dentro de cada grupo de vértices con el mismo y coordenada, los vértices están permutadas con el fin de minimizar el número de cruces en el dibujo resultante, y los vértices se asignan x coordenadas x consistente con esta permutación.
- Los vértices y aristas del gráfico se dibujan con las coordenadas que se les asignan.
En este marco, la asignación de la coordenada y nuevamente implica agrupar elementos de un conjunto parcialmente ordenado (los vértices del gráfico, con el orden de accesibilidad en el conjunto de vértices) en capas (conjuntos de vértices con la misma coordenada y ), que es el problema resuelto por el algoritmo de Coffman-Graham. [6] Aunque existen enfoques alternativos que el algoritmo de Coffman-Graham para el paso de capas, estas alternativas en general no pueden incorporar un límite en el ancho máximo de un nivel o dependen de procedimientos complejos de programación de enteros . [8]
Más abstractamente, ambos problemas se pueden formalizar como un problema en el que la entrada consiste en un conjunto parcialmente ordenado y un número entero W . La salida deseada es una asignación de números de nivel entero a los elementos del conjunto parcialmente ordenado de manera que, si x < y es un par ordenado de elementos relacionados del orden parcial, el número asignado ax es menor que el número asignado ay , de manera que a la mayoría de los elementos W se les asigna el mismo número entre sí, y se minimiza la diferencia entre los números asignados más pequeños y más grandes.
El algoritmo
El algoritmo de Coffman-Graham realiza los siguientes pasos. [6]
- Representan el orden parcial por su reducción transitiva o relación de cobertura , un gráfico acíclico dirigido G que tiene un borde de x a y siempre que x < y y no existe ningún tercer elemento z de la orden parcial para la que x < z < y . En las aplicaciones de dibujo de gráficos del algoritmo de Coffman-Graham, el gráfico acíclico dirigido resultante puede no ser el mismo que el gráfico que se está dibujando, y en las aplicaciones de programación puede que no tenga una ventaja para cada restricción de precedencia de la entrada: en ambos casos , la reducción transitiva elimina los bordes redundantes que no son necesarios para definir el orden parcial.
- Construya un ordenamiento topológico de G en el que los vértices estén ordenados lexicográficamente por el conjunto de posiciones de sus vecinos entrantes. Para hacerlo, agregue los vértices uno a la vez al orden, en cada paso eligiendo un vértice v para agregar de modo que los vecinos entrantes de v ya formen parte del orden parcial, y tal que el vecino entrante más recientemente agregado de v es anterior al vecino entrante agregado más recientemente de cualquier otro vértice que podría agregarse en lugar de v . Si dos vértices tienen el mismo vecino entrante agregado más recientemente, el algoritmo rompe el empate a favor del segundo cuyo segundo vecino entrante agregado más recientemente es anterior, etc.
- Asigne los vértices de G a niveles en el reverso del orden topológico construido en el paso anterior. Para cada vértice v , agregue v a un nivel que sea al menos un paso más alto que el nivel más alto de cualquier vecino saliente de v , que aún no tenga W elementos asignados y que sea lo más bajo posible sujeto a estos dos limitaciones.
Análisis
Como demostraron originalmente Coffman y Graham (1972) , su algoritmo calcula una asignación óptima para W = 2 ; es decir, para problemas de programación con trabajos de longitud unitaria en dos procesadores, o para problemas de dibujo de gráficos en capas con un máximo de dos vértices por capa. [1] Un algoritmo estrechamente relacionado también encuentra la solución óptima para la programación de trabajos con diferentes longitudes, lo que permite adelantar trabajos programados en dos procesadores. [9] Para W > 2 , el algoritmo de Coffman-Graham usa un número de niveles (o calcula un programa con un intervalo de tiempo) que está dentro de un factor de 2 - 2 / W del óptimo. [2] [3] Por ejemplo, para W = 3 , esto significa que utiliza como máximo 4/3 veces tantos niveles como es óptimo. Cuando el orden parcial de las restricciones de precedencia es un orden de intervalo , o pertenece a varias clases relacionadas de órdenes parciales, el algoritmo de Coffman-Graham encuentra una solución con el número mínimo de niveles independientemente de su límite de ancho. [10]
Además de encontrar programas con un margen pequeño, el algoritmo de Coffman-Graham (modificado de la presentación aquí para que ordene topológicamente el gráfico inverso de G y coloque los vértices lo antes posible en lugar de lo más tarde posible) minimiza el tiempo de flujo total de programas de dos procesadores, la suma de los tiempos de finalización de los trabajos individuales. Se puede utilizar un algoritmo relacionado para minimizar el tiempo de flujo total para una versión del problema en la que se permite la apropiación de trabajos. [11]
Coffman y Graham (1972) y Lenstra y Rinnooy Kan (1978) [12] establecen que la complejidad temporal del algoritmo de Coffman-Graham, en un orden parcial de n elementos, es O ( n 2 ) . Sin embargo, este análisis omite el tiempo para construir la reducción transitiva, que no se sabe que sea posible dentro de este límite. Sethi (1976) muestra cómo implementar la etapa de ordenamiento topológico del algoritmo en tiempo lineal , basándose en la idea del refinamiento de la partición . [13] Sethi también muestra cómo implementar la etapa de asignación de niveles del algoritmo de manera eficiente mediante el uso de una estructura de datos de conjuntos disjuntos . En particular, con una versión de esta estructura publicada más tarde por Gabow y Tarjan (1985) , esta etapa también toma tiempo lineal. [14]
Referencias
- ^ a b c Coffman, EG, Jr .; Graham, RL (1972), "Programación óptima para sistemas de dos procesadores" (PDF) , Acta Informatica , 1 : 200–213, doi : 10.1007 / bf00288685 , MR 0334913.
- ^ a b Lam, Shui; Sethi, Ravi (1977), "Análisis del peor caso de dos algoritmos de programación", SIAM Journal on Computing , 6 (3): 518–536, doi : 10.1137 / 0206037 , MR 0496614.
- ^ a b Braschi, Bertrand; Trystram, Denis (1994), "Una nueva visión del algoritmo Coffman-Graham", SIAM Journal on Computing , 23 (3): 662-669, doi : 10.1137 / S0097539790181889 , MR 1274650.
- ^ Leung, Joseph Y.-T. (2004), "Algunos algoritmos de programación básicos", Manual de programación: algoritmos, modelos y análisis de rendimiento , CRC Press, ISBN 978-1-58488-397-5.
- ^ Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Métodos para la comprensión visual de las estructuras del sistema jerárquico", IEEE Transactions on Systems, Man, and Cybernetics , SMC-11 (2): 109-125, doi : 10.1109 / TSMC.1981.4308636 , MR 0611436.
- ^ a b c di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1999), "Capítulo 9: Dibujos en capas de dígrafos", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall, págs. 265-302.
- ^ Bastert, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models , Lecture Notes in Computer Science, 2025 , Springer-Verlag, págs. 87-120, doi : 10.1007 / 3-540-44969-8_5. Bastert y Matuszewski también incluyen una descripción del algoritmo de Coffman-Graham; sin embargo, omiten la etapa de reducción transitiva del algoritmo.
- ^ Hola, Patrick; Nikolov, Nikola S. (2002), "Cómo superponer un gráfico acíclico dirigido", Dibujo gráfico: 9º Simposio Internacional, GD 2001 Viena, Austria, 23 al 26 de septiembre de 2001, Artículos revisados , Lecture Notes in Computer Science, 2265 , Springer-Verlag, págs. 16-30, doi : 10.1007 / 3-540-45848-4_2 , MR 1962416.
- ^ Muntz, RR; Coffman, EG (1969), "Optimal preventtive scheduling on two-process systems", IEEE Transactions on Computers , 18 : 1014–1020, doi : 10.1109 / TC.1969.222573.
- ^ Chardon, Marc; Moukrim, Aziz (2005), "El algoritmo de Coffman-Graham resuelve de manera óptima los sistemas de tareas de UET con órdenes de intervalo excesivo ", SIAM Journal on Discrete Mathematics , 19 (1): 109-121, doi : 10.1137 / S0895480101394999 , MR 2178187.
- ^ Coffman, EG, Jr .; Sethuraman, J .; Timkovsky, VG (2003), "Programas preventivos ideales en dos procesadores", Acta Informatica , 39 (8): 597–612, doi : 10.1007 / s00236-003-0119-6 , MR 1996238.
- ^ Lenstra, JK ; Rinnooy Kan, AHG (1978), "Complejidad de la programación bajo restricciones de precedencia", Investigación de operaciones , 26 (1): 22–35, doi : 10.1287 / opre.26.1.22 , hdl : 10338.dmlcz / 141477 , JSTOR 169889 , Señor 0462553.
- ^ 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.
- ^ Gabow, Harold N .; Tarjan, Robert Endre (1985), "Un algoritmo de tiempo lineal para un caso especial de unión de conjuntos disjuntos", Journal of Computer and System Sciences , 30 (2): 209-221, doi : 10.1016 / 0022-0000 (85) 90014-5 , MR 0801823.