Transcript
CO-5422 (F09) 27/11/2009
58
Complejidad: Como un valor finito de d(j) está acotado entre −nC y nC (la cota superior queda como ejercicio, se sugiere hacerlo por inducción en el tamaño del árbol T ), el algoritmo actualiza cada etiqueta a los sumo 2nC veces (datos enteros). En consecuencia el número total de actualizaciones está acotado por 2n2C. No podemos mejorarla pues carecemos de información. Esta complejidad se puede mejorar, modificando el algoritmo.
Algoritmo modificado de corrección de etiquetas. La idea es encontrar un método de seleccionar el arco que viola HC que resulte en un algoritmo más eficiente (hasta ahora no se ha usado ninguna información). Una forma es mantener una lista de arcos candidatos a violar la condición (la lista contiene a todos los que violan la condición, pero puede contener “inocentes”). Se selecciona un arco (i, j) de la lista y, si éste viola la condición, se actualiza la etiqueta de j y se saca el arco de la lista. Al reducir una etiqueta d(j), los arcos (j, k) en A(j) son buenos candidatos a violar la condición de optimalidad (recordar cjk + d(j) − d(k)). Los que entran a j no violarán la condición si no lo hacían antes (en cuyo caso ya estaban en la lista de candidatos). Y esos son todos los que varían. Una buena forma de llevar esto a cabo es usar una lista de nodos, en vista de que ya tenemos almacenadas sus A (·) (en estrella, por ejemplo), en lugar de crear una nueva lista de arcos. En efecto, se guarda una lista de nodos que cumple que si un arco (i, j) viola HC, entonces el nodo salida i debe estar en la lista. De nuevo, puede haber nodos que no tengan “culpables” en su lista de adyacencia, pero ningún nodo que los tenga estará fuera. El algoritmo modificado queda: algoritmo modificado de corrección de etiquetas; begin d(s) := 0; pred (s) := 0; d(j) := +∞, j ∈ N \ {s}; LIST := {s} ; while (LIST 6= ∅) do begin quitar un nodo i de LIST ; for each (i, j) ∈ A (i) do if d(j) > d(i) + cij then begin d(j) := d(i) + cij; pred (j) := i; if j ∈ / LIST then añadir j a LIST ; end if end while end Este algoritmo cumple con la propiedad de que LIST contiene todo nodo i incidente a un arco (i, j) que viole HC (¡perdonen la insistencia!). Ejemplo (a ser agregado luego).
CO-5422 (F09) 27/11/2009
59
Complejidad: Al actualizar d(j) se añade el nodo j a LIST . Luego eventualmente se selecciona j y se revisa A(j). Como cada actualización de d(j) ocurre a lo sumo 2nC veces se obtiene X 2nC |A(i)| = O(nmC) i∈N
la cual todavía depende de C y no mejora la del algoritmo genérico. Sin embargo, nos pone en la ruta de implementaciones que sí lo hacen. Implementaciones: De nuevo, se trata de mejorar la complejidad práctica (y teórica) de este algoritmo. La primera idea es mantener LIST como una cola. Con esto se logra un tiempo de ejecución de O (mn) que es el mejor para este tipo de algoritmo, la eficiencia empírica es también muy buena. Con una pequeña modificación (usando una de-cola, se discrimina entre nodos previamente “atendidos” y los nuevos, como en un banco) se logra un excelente comportamiento empírico, aunque la complejidad teórica es mala. Los algoritmos que mejor se han comportado en la práctica para problemas arbitrarios, han sido implementaciones ingeniosas de este simple algoritmo de corrección de etiquetas. Se sugiere ver tabla al final del capítulo 5 de Ahuja, Magnanti y Orlin (p.155). Detección de ciclos negativos: La forma más obvia: Detectar si alguna etiqueta baja de −nC. Si esto ocurre para un nodo k, la detección del ciclo se logra iterando pred desde k. Hay otras formas ligeramente más complicadas que se pueden incorporar al algoritmo (genérico o modificado).