El problema del camino más corto: algoritmos y aplicaciones

Traballo Fin de Grao EL PROBLEMA DEL CAMINO MÁS CORTO: ALGORITMOS Y APLICACIONES Alba Gude Santos 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRADO DE MATEMÁTICAS Traballo Fin de Grao EL PROBLEMA DEL CAMINO MÁS CORTO: ALGORITMOS Y APLICACIONES Alba Gude Santos 05/Xullo/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estadística e Investigación Operativa Título: El problema del camino más corto: Algoritmos y aplicaciones Breve descrición do contido Neste traballo de fin de grao profundizarase no estudio do problema do camiño máis curto, tanto desde o punto de vista teórico como do punto de vista da implementación práctica de algoritmos e aplicacións. Recomendacións Outras observacións iii Índice general Resumen viii Introducción xi 1. Conceptos y resultados de problemas de flujo en redes 1 1.1. Grafos ....................................... 1 1.2. Matrices de información de un grafo ...................... 3 1.3. Listas ....................................... 4 1.4. Árboles ...................................... 4 2. Problema del camino más corto 5 2.1. Formulación del problema del camino más corto ................ 6 2.2. Símil físico del problema del camino más corto ................ 8 2.3. Árbol de caminos más cortos .......................... 9 3. Definición, análisis y tipos de algoritmos 11 3.1. Análisis de complejidad de un algoritmo .................... 12 3.1.1. Diferentes medidas de complejidad ................... 12 3.1.2. Tamaño del problema .......................... 13 3.1.3. Complejidad en el peor caso ....................... 13 3.1.4. Tipos de notaciones ........................... 14 3.1.5. Algoritmos de tiempo polinomial y exponencial ............ 15 3.1.6. Funciones potenciales y complejidad amortizada ........... 16 3.2. Desarrollo de algoritmos de tiempo polinomial ................. 16 3.2.1. Enfoque de mejora geométrica ...................... 17 3.2.2. Enfoque de escala ............................. 18 3.2.3. Enfoque de programación dinámica ................... 18 3.2.4. Búsqueda binaria ............................. 19 v vi ÍNDICE GENERAL 3.3. Tipos de algoritmos ............................... 19 3.3.1. Algoritmos de búsqueda ......................... 19 3.3.2. Algoritmos de descomposición de flujo ................. 22 3.3.3. Algoritmos de ajuste y corrección de etiquetas ............. 25 3.4. Algoritmo en redes acíclicas ........................... 25 4. Algoritmos de configuración de etiquetas 29 4.1. Algoritmo de Dijkstra .............................. 29 4.1.1. Tiempo de ejecución del algoritmo de Dijkstra ............. 31 4.1.2. Implementación del algoritmo de Dijkstra en R ............ 32 4.2. Algoritmo de Dial ................................. 33 4.3. Algoritmo de Radix-Heap ............................ 35 5. Algoritmos de corrección de etiquetas 41 5.1. Condiciones de optimalidad ........................... 42 5.2. Detección de ciclos negativos .......................... 43 5.3. Algoritmo genérico de corrección de etiquetas ................. 44 5.4. Algoritmo de corrección de etiquetas modificado ................ 47 5.4.1. Implementación de eliminación de cola ................. 48 6. Aplicaciones del problema del camino más corto 49 6.1. El problema de la mochila ............................ 49 Bibliografía 53 2CAPÍTULO 1. CONCEPTOS Y RESULTADOS DE PROBLEMAS DE FLUJO EN REDES Definición 1.5. Un ciclo es una cadena cerrada en la que no coinciden más nodos que el primero y el último. Diremos que un ciclo es de longitud total negativa si al sumar la longitud de los arcos que lo forman obtenemos un valor negativo. Para abreviar, nos referiremos a este tipo de ciclos como ciclos negativos. Definimos a continuación dos tipos de grafos: Definición 1.6. Un grafo G= (N, A)es un grafo dirigido si los arcos son pares ordenados. Es decir, el arco (i, j)empieza en el nodo iy termina en el nodo j. Definición 1.7. Un grafo G= (N, A)es un grafo no dirigido si (i, j)y(j, i)representan la misma arista. Es decir, podemos ir de iajy de jai. También diremos que el arco (i, j)empieza en el nodo iy termina en el nodo j, ya que es una arista saliente del nodo iy entrante del nodo j. Cuando (i, j)∈A, diremos que el nodo jes adyacente al nodo i. Si existe un camino compuesto de uno o más arcos que una icon j, diremos que ies el nodo predecesor de jy lo denotaremos por pred(j) = i. Definición 1.8. Un grafo predecesor es aquel que se forma a partir de los índices predecesores de todos los nodos que forman un camino. Ejemplo 1.9. Dado el siguiente grafo, vamos a obtener los conjuntos NyAen diferentes casos: 1 2 3 El conjunto de nodos de este grafo dirigido es N={1,2,3}y el de aristas A={(1,2),(2,3),(3,1)}. Sin embargo, si el grafo fuera no dirigido, N={1,2,3}yA={(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}. 1.2. MATRICES DE INFORMACIÓN DE UN GRAFO 3 Definición 1.10. Diremos que un grafo es acíclico si no contiene ningún ciclo dirigido. Definición 1.11. Diremos que un grafo es bipartito si sus nodos se pueden separar en dos conjuntos disjuntos, de manera que los nodos de un mismo conjunto no están relacionados. 1.2. Matrices de información de un grafo Definición 1.12. Dado un grafo G= (N, A), este puede ser representado por su matriz de adyacencia, que es una matriz Anxn (nes el número de nodos) definida por: aij =(1se (i, j)é unha arista en G 0noutro caso. Definición 1.13. Dado un grafo G= (N, A), para un nodo i∈N, definimos su lista de adyacencia, y será denotada por A(i), como la i-ésima fila de la matriz de adyacencia de G. Ejemplo 1.14. Dado el siguiente grafo dirigido: 1 2 3 45 Su matriz de adyacencia sería:          01000 10101 00001 10000 10010          Y la lista de adyacencia del nodo 1 será: A(1) = (0,1,0,0,0) 4CAPÍTULO 1. CONCEPTOS Y RESULTADOS DE PROBLEMAS DE FLUJO EN REDES 1.3. Listas Una lista enlazada individualmente puede almacenar elementos en un orden arbitrario (en vez de un conjunto ordenado secuentalmente como en una matriz), pero requiere información adicional que nos permita acceder a los datos en el orden especificado en el conjunto ordenado. Una celda es un componente esencial de las listas enlazadas y podemos pensarla como una caja capaz de contener varios valores, llamados campos. Definición 1.15. Entonces, una lista enlazada individualmente es una colección de celdas enlazadas entre sí. Cada celda tiene dos campos: un campo de datos y un campo de enlace. Definición 1.16. Una lista doblemente enlazada es lo mismo que una lista enlazada individualmente, excepto que cada celda tiene dos enlaces, uno a la celda anterior y el otro a la celda siguiente. Una ventaja de las listas doblemente enlazadas es que podemos recorrer la lista fácilmente en ambas direcciones y realizar una eliminación arbitraria de un elemento en O(1) tiempo. 1.4. Árboles Diremos que un grafo es conexo si para cada par de nodos existe una cadena no dirigida que los une. Si, además, existe una cadena dirigida que los une, diremos que es un grafo fuertemente conexo. Definición 1.17. Un árbol es un grafo conexo que no contiene ciclos. Definición 1.18. Un árbol de camino más corto es un árbol externo dirigido enraizado en el nodo origen, con la propiedad de que el único camino desde el origen a cualquier nodo del grafo es el camino más corto a ese nodo. Capítulo 2 Problema del camino más corto: formulación y resultados Los problemas del camino más corto son un caso particular de los problemas de flujo en redes y aparecen muchas veces en la práctica cuando, por ejemplo, queremos enviar un objeto entre dos lugares concretos de la forma más rápida y económica posible. Además de ser problemas fáciles de resolver de forma eficiente, son un punto de referencia para analizar problemas de red más complejos; y aparecen muchas veces como subproblemas al resolver problemas de optimización en redes. A pesar de que estos problemas son fáciles de resolver, el estudio del problema del camino más corto es un punto de partida para introducir ideas importantes de los problemas de optimización en redes, como son las estructuras de datos inteligentes o el escalado de datos para mejorar el rendimiento de un algoritmo en el peor caso. Definición 2.1. El problema del camino más corto en un grafo dirigido G= (N, A)con longitudes c∈Rnconsiste en encontrar el camino más corto de un nodo s, llamado nodo fuente, al resto de los nodos i∈N\ {s}de la red. Hasta el momento se han estudiado diferentes tipos del problema del camino más corto: 1. Descubrir el camino más corto de un nodo a todos los demás cuando las longitudes de arco no son negativas. 2. Hallar el camino más corto de un nodo a todos los demás para redes con longitudes 5 6CAPÍTULO 2. PROBLEMA DEL CAMINO MÁS CORTO de arco arbitrarias. 3. Encontrar el camino más corto de cada nodo al resto de nodos de la red. Los dos primeros tipos se conocen como problema del camino más corto de fuente única, mientras que el tercer tipo se conoce como problema del camino más corto de todos los pares; que consiste en determinar la distancia más corta que hay entre cada par de nodos de una red. 2.1. Formulación del problema del camino más corto El problema del camino más corto consiste en determinar para cada nodo i∈N,i6=s, un camino dirigido de longitud mínima desde el nodo s, que es el nodo fuente de la red, al nodo i. Por otra parte, podemos pensar el problema como enviar 1 unidad de flujo de la forma más económica desde el nodo sa cada uno de los nodos en N\ {s}. Sea una red dirigida G= (N, A), siendo Nel conjunto de nodos y Ael conjunto de arcos que forman la red, con un coste de arco cij 1asociado a cada arco (i, j)∈A. Sea A(i) la lista de adyacencia del nodo i y sea C= m´ax {cij : (i, j)∈A}. Para calcular el coste de un camino dirigido sumamos los costes de los arcos que lo forman. Todo esto da lugar a la siguiente formulación en forma matricial del problema del camino más corto: m´ın cT·f sujeto a An×m·f=e Im×m·f≥0 donde An×m2es la matriz de incidencia nodo-arco asociada al grafo en el que está definido el problema y es=1, en=-1 , con i∈N\ {s}. 1Utilizaremos coste ylongitud indistintivamente. 2mdenota el número de aristas 2.1. FORMULACIÓN DEL PROBLEMA DEL CAMINO MÁS CORTO 7 Además, podemos formular el problema del camino más corto en términos de flujos y costes para cada arista (i, j)∈Ade la siguiente forma: m´ın P{(i,j)∈A}cijxij sujeto a P{j:(i,j)∈A}xij −P{j:(i,j)∈A}xji =       −1, si ies el nodo inicial 1, si ies el nodo terminal 0, en otro caso xij ≥0∀(i, j)∈A. Haremos los siguientes supuestos para el estudio del problema del camino más corto: 1. Supuesto de parámetros enteros: todas las longitudes de arco son números enteros. Los algoritmos cuyo límite de complejidad depende de C, donde Ces la mayor longitud de arco de la red, asumen que los datos son enteros. Por otra parte, siempre podemos multiplicar por un número suficientemente grande para transformar un número racional en entero. Además, necesitamos convertir los números en racionales para poder introducirlos en un ordenador, con lo cual este supuesto no es una restricción en la práctica. 2. Existe un camino dirigido desde el nodo sa los demás nodos de la red. Para cumplir esta condición, siempre podemos añadir un arco “ficticio” (s, j)con un coste muy alto para cada nodo jque no está conectado con sa través de un camino dirigido. En este caso, cuando un arco ficticio forme parte de alguna solución, nos estará indicando que en el grafo original no existía ningún camino entre los dos nodos unidos por dicho arco. 3. La red no contiene ciclos negativos. En caso de tener ciclos negativos en nuestra red, el problema tendría solución ilimitada porque a través de un ciclo de longitud total negativa podemos enviar una cantidad infinita de flujo (es decir, la función objetivo decrecería en cada iteración). El problema del camino más corto con ciclos negativos es difícil de resolver, ya que se trata de un problema NP-completo y es posible que no existan algoritmos polinomiales para hallar su solución. Cuando tenemos un problema del camino más corto con un ciclo negativo, el camino dirigido de menor coste puede pasar por un ciclo negativo infinitas veces, ya que en cada paso por el ciclo, se reduce el coste del camino. Para controlar esto, describiremos algoritmos que detecten la presencia de estos ciclos. 8CAPÍTULO 2. PROBLEMA DEL CAMINO MÁS CORTO 4. La red es dirigida. En caso contrario, podemos transformar la red en dirigida añadiendo un arco en cada dirección. Nótese que si los costes son negativos, se produciría un ciclo con longitud total negativa. 1 2 3 4 5 6 7 1 3 6 2 8 3 8 2 Este grafo es un ejemplo que cumple los cuatro supuestos (podemos tomar s= 1) 2.2. Símil físico del problema del camino más corto Debido a la sencilla estructura del problema del camino más corto, se han podido desarrollar multitud de algoritmos de gran eficiencia computacional. Vamos a considerar ahora un problema del camino más corto entre dos nodos syt. Intentamos modelizar el problema con una cuerda de la siguiente manera: cogemos una cuerda y le hacemos nudos, cada nudo representará un nodo de nuestra red. Denotaremos por cij a la longitud de cuerda que hay entre los nodos iyj. Suponiendo que la cuerda no se puede estirar, cogemos en una mano el nudo que representa el nodo sy en la otra el que representa el nodo i. Cuando separamos las manos, vemos que hay uno o más trozos de cuerda que están tensos, que son los que representan los caminos más cortos de sai. Del anterior modelo, obtenemos las siguientes ideas del problema del camino más corto: Al estar la cuerda tensa para cualquier arco en un camino más corto, la distancia del camino más corto entre dos nodos sucesivos iyjserá la longitud de cuerda que hay entre ellos, es decir, cij. Si conocemos la distancia más corta del nodo fuente, s, al nodo i, se cumple que la distancia de sajes igual a la distancia de saimás cij, cuando los nodos iyjestán conectados en la red. La distancia puede ser mayor si la cuerda entre iyjno está tensa. 2.3. ÁRBOL DE CAMINOS MÁS CORTOS 9 En general, todos los problemas de flujo de red expresados como problemas de minimización tienen un problema “dual” asociado, que es un problema de maximización. Al resolver uno de ellos, también resolvemos el otro. 2.3. Árbol de caminos más cortos En el problema del camino más corto, nuestro objetivo es determinar un camino más corto desde el nodo fuente, s, a los n−1nodos restantes de la red, siendo nel número total de nodos. En un principio, podemos pensar que un límite superior para almacenar estos caminos sería (n−1)2, ya que cada camino puede contener como máximo n−1arcos. Pero esto no es necesario porque, como mostramos a continuación, se puede encontrar un árbol externo dirigido desde el nodo fuente con la propiedad de que el único camino de sa cada nodo i∈N\ {s}es el camino más corto a ese nodo. Por tanto, como un árbol con nnodos tiene como mucho n−1arcos, este será el número que necesitaremos para almacenar todos los caminos. Ejemplo 2.2. En el siguiente grafo queremos encontrar el camino más corto entre los nodos 1 y 5. Si calculamos todos los caminos posibles para ir del nodo 1 al 5, el que tiene menor coste será el camino 1−2−3−5con un coste c15 = 11 1 2 3 4 5 6 3 5 7 24 8 1 6 La existencia del árbol del camino más corto se debe a la siguiente propiedad: 10 CAPÍTULO 2. PROBLEMA DEL CAMINO MÁS CORTO Proposición 2.3. Si el camino s=i1−i2− · · · − ih=kes un camino más corto desde sak, entonces para cada q= 2,3, . . . , h −1, el camino s=i1−i2− · · · − iqes el camino más corto del nodo origen, s, al nodo q. Para cada i∈N\ {s}, denotamos por d(i)a la distancia del camino más cortos de sa i. La proposición 2.3 implica que Pes un camino más corto de sa algún nodo jsi, y sólo si, d(j) = d(i) + cij para cada arco (i, j)∈P. Establecemos ahora el siguiente resultado: Proposición 2.4. Sea Pel camino más corto de sak, y sea s=i1−i2− · · · − ih=kla secuencia de nodos en P, entonces: d(k) = d(ih)=(d(ih)−d(ih−1)+(d(ih−1)−d(ih−2)) + · · · + (d(i2)−d(i1)), donde d(i1)=0. También se cumple que d(j)−d(i) = cij para cada arco (i, j)∈P. Usando esta igualdad vemos que: d(k) = cih−1ih+cih−2ih−1+· · · +ci1i2=P(i,j)∈Pcij Como consecuencia, Pserá un camino dirigido del nodo origen al nodo kde longitud d(k), y será el camino más corto al nodo k. Introducimos así la siguiente propiedad: Proposición 2.5. Si d(·)denota las distancias de caminos más cortos. Entonces, un camino dirigido Pdesde el nodo origen, s, al nodo j,j∈N\ {s}, es el camino más corto si y solo si d(j) = d(i) + cij para cada arco (i, j)∈P. Esta propiedad es inmediata e implica que siempre existe un camino más corto desde sa todos los demás nodos que satisfacen que para cada arco (i, j)en el camino, d(j) = d(i)+cij. Capítulo 3 Definición, análisis y tipos de algoritmos En este capítulo hablaremos de qué es un algoritmo y los diferentes tipos que existen, que son una parte fundamental en el campo de los problemas computacionales ya que sirven para resolver un determinado tipo de problema. Un algoritmo es un procedimiento paso a paso que resuelve un problema. Los problemas pueden ser subproblemas unos de otros: por ejemplo, no solo define un problema el conjunto de problemas del camino más corto, sino que la clase de los problemas del camino más corto con longitudes no negativas, también lo define. Definimos una instancia como un caso de un problema, donde todos los parámetros del problema están determinados. Para definir una instancia del problema del camino más corto, necesitaríamos saber cuál es la topología de la red G= (N, A), los nodos de origen y destino, y los costes de cada arco, los cij. Entonces, diremos que un algoritmo resuelve un cierto problema Psi devuelve una solución para cada instancia de P. Como resolver un problema requiere la solución de un modelo de optimización que puede tener muchas variables, ecuaciones y desigualdades, utilizaremos un ordenador para resolverlo. Por tanto, tendremos que ser capaces de implementar los pasos de un algoritmo en un programa de ordenador. Aunque los matemáticos chinos del siglo III a.C. habían ideado algoritmos para resolver pequeñas ecuaciones, no fue hasta 1970 que comenzaron a estudiar el concepto de eficiencia de los algoritmos. Esta materia, denominada teoría de la complejidad computacional, proporciona diferentes maneras de medir el trabajo de los algoritmos contando las operaciones elementales que realiza. Para medir la eficiencia de un algoritmo, contaremos el tiempo que tarda debido a que el tiempo es un recurso informático dominante. 11 18 CAPÍTULO 3. DEFINICIÓN, ANÁLISIS Y TIPOS DE ALGORITMOS Podemos resumir el enfoque de mejora geométrica con la afirmación : "los algoritmos de red que tienen una tasa de convergencia geométrica son algoritmos de tiempo polinomial". Para desarrollar algoritmos de tiempo polinomial usando este enfoque, lo que hacemos es buscar técnicas de mejora local que produzcan grandes mejoras en la función objetivo en cada iteración. 3.2.2. Enfoque de escala Con el tiempo, se han usado muchos métodos de escalado para desarollar algoritmos polinomiales para muchos problemas de optimización, combinatoria y de red. Para los problemas que cumplen el supuesto de similitud, los algoritmos de este tipo consiguen el mejor tiempo de ejecución en el peor caso para casi todos los problemas de optimización en redes. La forma más sencilla de escalado es el escalado de bits, que consiste en representar los datos con números binarios y resolver un problema Pcomo una sucesión de problemas P1, . . . , Pk. El problema P1aproxima los datos al primer bit más significativo, el problema P2a los dos primeros bits más significativos, y así sucesivamente, hasta que P=Pk. Por otra parte, para cada i= 2, . . . , k, utilizamos la solución óptima de Pi−1como solución inicial del problema Pi. Propiedad 3.11. La capacidad de un arco en Pkes el doble que en Pk−1más 0 ó 1. El enfoque de escala resuelve bien estos problemas porque: 1. P1suele ser fácil de resolver. 2. La solución óptima de Pi−1es una buena solución inicial para el problema Pi, y esto se debe a que estos dos problemas son parecidos. 3. El número de problemas de reoptimización que resolvemos es O(log C)óO(log U). Con esto vemos que para llevar a cabo este enfoque, la reoptimización debe ser más eficiente que la optimización. 3.2.3. Enfoque de programación dinámica Definiremos la programación dinámica como un enfoque de “llenado de tablas” donde completamos recursivamente las entradas de un cuadro de dos dimensiones. 3.3. TIPOS DE ALGORITMOS 19 3.2.4. Búsqueda binaria La búsqueda binaria es una técnica para conseguir algoritmos polinomiales para muchos problemas de optimización en redes. Este método se usa para encontrar una solución que cumpla las condiciones requeridas entre un conjunto de soluciones factibles y lo que hace es eliminar, en cada paso, un porcentaje fijo del conjunto de soluciones hasta que el conjunto es tan pequeño que todas las soluciones factibles son una solución que cumple las propiedades que queremos. Veamos qué es la búsqueda binaria con el siguiente ejemplo: Ejemplo 3.12. Supongamos una función continua f(x)que cumple que f(0) <0yf(1) > 0. Queremos encontrar un intervalo de tamaño εque contenga el cero de esa función, esto es, un valor xtal que f(x)=0. El primer paso es dividir el intervalo inicial a la mitad, en este caso [0,1], que sabemos que contiene un cero. Evaluamos la función en x= 0.5y vemos si f(0.5) = 0,f(0.5) <0óf(0.5) >0. Si sucede el primer caso, x= 0.5sería el cero del intervalo y terminaríamos el proceso. En el segundo caso, como f(1) >0, sabemos que el intervalo [0.5,1] contiene un cero, ya que estamos suponiendo que fes continua. Análogamente haríamos con el tercer caso, en el cual el cero estaría en el intervalo [0,0.5]. En los dos últimos casos, el punto nuevo con el que probaremos será, otra vez, con el punto medio, es decir con x= 0.75 o con x= 0.25, respectivamente. Repetimos el proceso hasta que el tamaño del intervalo sea menor que ε. Este método termina en O(log 1 ε). Normalmente, usaremos esta técnica para buscar el valor deseado de un parámetro dentro de un intervalo de posibles valores. También existe una versión generalizada que nos permite buscar valores de múltiples parámetros. El proceso que acabamos de ver en el anterior ejemplo se corresponde con el método de dicotomía que vimos en el grado. 3.3. Tipos de algoritmos 3.3.1. Algoritmos de búsqueda Estos algoritmos son técnicas de grafos que intentan encontrar todos los nodos de una red que cumplan una cierta propiedad. Los algoritmos de búsqueda son útiles para: Encontrar todos los nodos que son accesbiles desde un determinado nodo en una red por un camino dirigido. Encontrar todos los nodos en una red que puedan llegar mediante un camino dirigido a un nodo i. 20 CAPÍTULO 3. DEFINICIÓN, ANÁLISIS Y TIPOS DE ALGORITMOS Identificar los nodos de una red que están conectados y determinar si es una red bipartita o no. Identificar en una red un ciclo dirigido y, si la red es acíclica, reordenar los nodos 1,2, . . . , n para que i<jpara cada arco (i, j)∈A. Para expresar las nociones básicas de estos algoritmos, supondremos que queremos encontrar todos los nodos que son accesibles mediante caminos dirigidos desde un nodo s, llamado nodo fuente, en una red G= (N, A). Un algoritmo de búsqueda comienza desde el nodo fuente e identifica un número de nodos que son accesibles desde él. En cada ejecución, el algoritmo designa todos los nodos de una red como si estuvieran en uno de los dos estados siguientes: “marcado” o “no marcado”. Los nodos marcados son accesibles desde el nodo fuente, y aún no se determinó el estado de los nodos sin marcar. Nótese que si el nodo iestá marcado, la red contiene el arco (i, j)y el nodo jno está marcado, podemos marcar también este nodo, ya que es accesible desde el nodo smediante un camino dirigido hasta el nodo imás el arco (i, j). En este caso, de estar marcado iy no j, llamaremos al arco (i, j)admisible. En caso contrario, lo llamaremos inadmisible. Cuando el algoritmo marca un nuevo nodo janalizando un arco admisible (i, j), decimos que el nodo ies un predecesor del nodo j(pred(j) = i). El algoritmo termina cuando la red no contiene arcos admisibles. El algoritmo de búsqueda va examinando los nodos marcados en un cierto orden; el orden de entrada (i)es el orden del nodo ien el recorrido. En la descripción de este tipo de algoritmos, LIST denota el conjunto de nodos marcados que aún tiene que examinar el algoritmo ya que alguno de los arcos admisibles podrían derivar de ellos. Cuanto termina el algoritmo, ha señalado todos los nodos en Gque son admisibles desde smediante un camino dirigido. Los índices predecesores definen un árbol que llamaremos árbol de búsqueda. Usaremos la estructura de datos “current-arc”, que definimos a continuación, para identificar los arcos admisibles en una red Gy para implementar algoritmos de flujos máximo y flujo de coste mínimo. Con cada nodo imantenemos la lista de adyacencua A(i) de los arcos que salen de él. El algoritmo examina los nodos dependiendo de cómo hayamos organizado los arcos en las listas de adyacencia de cada arco A(i). Para cada nodo i, definimos un arco actual (i, j), que es el siguiente candidato que vamos a examinar. Al prinicipio, el arco actual del nodo ies el primer arco en A(i). El algoritmo de búsqueda examina la lista A(i)de forma secuencial: en una etapa, si el arco actual es inadmisible, el algoritmo determina el siguiente arco en la lista como el arco actual. Cuando el algoritmo acaba de examinar la lista de arcos, determina que el nodo no tiene un arco admisible. Suponemos ahora que hemos ordenado los arcos en A(i)en el orden creciente de sus nodos principales, esto quiere decir que si (i, j)y(i, k)son dos arcos consecutivos en A(i), entonces j < k. El 3.3. TIPOS DE ALGORITMOS 21 algoritmo de búsqueda tarda, en total, O(m+n) = O(m)tiempo ya que, como el algoritmo marca cualquier nodo como máximo una vez, este proceso teminará después de 2nveces, como mucho. Además, para cada nodo i, examinamos los arcos de A(i), como máximo, una vez. Con lo cual, el algoritmo de búsqueda escanea un total de Pi∈N|A(i)|=marcos, por tanto termina en O(m)tiempo. Existen dos estrategias de búsqueda fundamentales: búsqueda en amplitud y búsqueda en profundidad. Búsqueda en amplitud o BFS (Breadth First Search) Si mantenemos el conjunto LIST como una cola, siempre seleccionamos los nodos del frente de LIST y los agregamos al final. Así, el algoritmo seleccionará los nodos marcados en un orden de primero en entrar, primero en salir. Definimos la distancia de un nodo icomo el número mínimo de arcos en un camino dirigido desde el nodo sal nodo i. Lo que hace este tipo de búsqueda es marcar primero los nodos con distancia 1, luego aquellos con distancia 2, y así sucesivamente. Entonces, esta versión de búsqueda se llama búsqueda en amplitud y el árbol resultante es un árbol de búsqueda en amplitud. 1 2 3 4 5 6 Figura 3.1: Árbol de búsqueda en amplitud Presentamos a continuación una propiedad importante de este tipo de árbol. Propiedad 3.13. En el árbol de búsqueda de amplitud, el camino desde el nodo de origen a cualquier nodo ies el camino más corto, es decir, contiene el menor número de arcos entre todos los caminos que unen estos dos nodos. 22 CAPÍTULO 3. DEFINICIÓN, ANÁLISIS Y TIPOS DE ALGORITMOS Búsqueda en profundidad o DFS (Depth First Search) Ahora, mantenemos el conjunto LIST como una pila, es decir, seleccionamos los primeros nodos de LIST y los añadimos al principio, en lugar de al final, como hacíamos con el algoritmo de búsqueda en amplitud. Lo que hace en este caso el algoritmo de búsqueda es seleccionar el nodo marcado en un orden de último en entrar, primero en salir. Este algoritmo hace una prueba profunda intentando crear un camino lo más largo posible, y hace una copia de seguridad de un nodo para iniciar una nueva búsqueda cuando no marque ningún nuevo nodo desde el inicio del camino. Por eso llamamos a esta técnica de búsqueda, búsqueda en profundidad y al árbol resultante, árbol de búsqueda en profundidad. 1 2 3 4 5 6 Figura 3.2: Árbol de búsqueda en profundidad Al igual que antes, existe una propiedad importante del árbol de búsqueda en profundidad: Proposición 3.14. Si el nodo jes un descendiente del nodo iyj6=i, entonces orden(j)> orden(i). Además, todos los descendientes de cualquier nodo se ordenan consecutivamente. 3.3.2. Algoritmos de descomposición de flujo Cuando formulamos problemas de flujo en redes, podemos elegir entre: definir flujos en arcos o definir flujos en caminos y ciclos. En esta sección, desarrollaremos varias relaciones entre estas dos formulaciones alternativas. Cuando nos referimos a “flujo de arco”, estamos hablando de un vector x={xij}que cumple lo siguiente: 3.3. TIPOS DE ALGORITMOS 23 X {j:(i,j)∈A} xij −X {j:(j,i)∈A} xji =−e(i)∀i∈N 0≤xij ≤uij ∀(i, j)∈A donde Pn i=1 e(i)=0, y donde el término e(i)representa la entrada de flujo menos la salida de flujo del nodo i. Con esto, si e(i)>0, entonces el flujo de entrada es mayor que el flujo que sale, y decimos que ies un nodo con exceso. En caso de ser el flujo de salida mayor que el flujo de entrada, e(i)<0, diremos que ies un nodo con déficit. Finalmente, si el flujo que entra es igual al flujo que sale, entonces e(i)=0, y diremos que ies un nodo equilibrado. La formulación de flujo de camino y ciclo comienza con una enumeración de todos los caminos dirigidos Pentre cualquier par de nodos y todos los ciclos dirigidos W de la red. Las variables de decisión serán f(P), que representa el flujo del camino P, y f(W), el flujo del ciclo W. Denotamos por Pal conjunto de caminos y por Wal conjunto de ciclos. Nótese que cada conjunto de caminos y ciclos determina de forma única los flujos de arco de manera natural: el flujo xij en el arco (i, j)es igual a la suma de f(P)yf(W) para todos los caminos Py todos los ciclos Wque contienen a ese arco. Formalizamos esto de la siguiente manera: δij(P) = 1 si el arco (i, j)pertenece al camino P, y 0 en otro caso. De la misma forma, δij(W) = 1 si el arco (i, j)está en el ciclo Wy 0 en otro caso. De esta forma: xij =X P∈P δij(P)f(P) + X W∈W δij(W)f(W) Con el siguiente teorema, observamos que podemos descomponer cualquier flujo de arco en flujo de camino y ciclo. Teorema 3.15 (Teorema de descomposición de flujo).Cada flujo de camino y ciclo tiene una representación única como flujos de arco no negativos. Asimismo, cada flujo de arco no negativo xse puede representar como un flujo de camino y ciclo (aunque no siempre de forma única) con las siguiente propiedades: 1. Todo camino dirigido con flujo positivo conecta un nodo en defecto con un nodo en exceso. 2. Como máximo, n+mcaminos y ciclos tienen un flujo distinto de cero. De estos, como máximo, mciclos tienen un flujo distinto de 0. 24 CAPÍTULO 3. DEFINICIÓN, ANÁLISIS Y TIPOS DE ALGORITMOS Demostración. Basándonos en observaciones previas, necesitamos establecer solamente la segunda afirmación. Damos una prueba algorítmica para mostrar cómo descomponer cualquier arco de flujo xen un camino y un ciclo de flujo. Supongamos que i0es un nodo en defecto. Entonces, algún arco (i0, i1)lleva un flujo positivo. Si i1es un nodo en exceso, nos detenemos; de lo contrario, algún otro arco (i1, i2)lleva un flujo positivo. Repetimos este proceso hasta que encontramos un nodo en exceso o volvemos a visitar un nodo previamente examinado. Uno de estos dos casos ocurrirá en npasos. En el primer caso, obtenemos un camino dirigido Pdesde el nodo en defecto i0a algún nodo en exceso ik, y en el último caso obtenemos un ciclo dirigido W. En cualquier caso, el camino o el ciclo consta únicamente de arcos con flujo positivo. Si obtenemos un camino dirigido, tenemos f(P) = m´ın {−e(i0), e(ik), min{xij : (i, j)∈P}} y redefinimos e(i0) = e(i0) + f(P), e(ik) = e(ik)−f(P)yxij =xij −f(P)para cada arco (i, j)∈P. Si obtenemos un ciclo dirigido W, ponemos f(W) = min{xij : (i, j)∈W}y redefinimos xij =xij −f(W)para cada (i, j)∈W. Repetimos este proceso con el problema redefinido hasta que todos los desequilibrios de nodos sean cero. Luego seleccionamos cualquier nodo con, al menos, un arco saliente con un flujo positivo como nodo inicial, y repetimos el procedimiento, que en este caso debe encontrar un ciclo dirigido. Terminamos cuando x= 0 para el problema redefinido. Claramente, el flujo original es la suma de los flujos en los caminos y ciclos identificados por este método. Nótese que cada vez que identificamos un camino dirigido, reducimos el exceso/déficit de algún nodo a cero o el flujo en algún arco a cero; y cada vez que identificamos un ciclo dirigido, reducimos el flujo en algún arco a cero. En conclusión, la representación de camino y ciclo del flujo xdado contiene como máximo n+mcaminos y ciclos dirigidos y , como máximo, mde estos son ciclos dirigidos. [2] Analizamos ahora cuál es el tiempo requerido por el algoritmo. Primero, construimos una lista de nodos en defecto. Mantenemos la lista como una lista doblemente enlazada (ver definición 1.16), de forma que tanto la selección de un elemento, como la adición o eliminación de un elemento, requieren O(1) tiempo. El algoritmo va eliminando los nodos de la lista a medida que avanza y, cuando la lista queda vacía, lo inicializamos como el conjunto de arcos con flujo positivo. Otra operación básica del algoritmo es identificar, mediante la estructura de “current arc” (definida en la página 21), un arco con flujo positivo que sale de un nodo. Estos arcos se llamarán arcos admisibles. En cualquier iteración, el algoritmo necesita O(n)tiempo más el tiempo que se gastó en la búsqueda de arcos para identificar aquellos que son admisibles. Debido a que los flujos de arco no aumentan, un arco que se considera inadmisible en una iteración, también será inadmisible en iteraciones posteriores. Como la estructura de datos de arco actual necesita un tiempo total de O(m) 3.4. ALGORITMO EN REDES ACÍCLICAS 25 en el escaneo del arco para identificar los arcos admisibles y el algoritmo realiza como máximo n+miteraciones, entonces el algoritmo de descomposición de flujo se ejecuta en un tiempo total de O(m+ (n+m)n) = O(nm). El teorema 3.15 nos permite comparar dos soluciones de un problema de flujo de red y ver cómo podemos construír una solución a partir de otra a partir de simples operaciones. 3.3.3. Algoritmos de ajuste y corrección de etiquetas Los enfoques algorítmicos para resolver problemas del camino más corto se clasifican en dos grupos: 1. Configuración de etiquetas. 2. Corrección de etiquetas. Ambos enfoques son iterativos, asignan etiquetas de distancia a los nodos en cada paso. Estas etiquetas de distancia son estimaciones de límites superiores en las distancias de caminos más cortos. Los algoritmos que establecen etiquetas definen una etiqueta como permanente (óptima) en cada iteración. Por otra parte, los algoritmos de correción de etiquetas definen todas las etiquetas como temporales hasta el último paso, cuando todas se convierten en permanentes. Los enfoques se distinguen, por tanto, en la forma que actualizan las etiquetas de distancia de un paso a otro y en cómo “convergen” hacia las distancias de camino más corto. Los algoritmos de establecimiento de etiquetas se aplican solamente a problemas de camino más corto con redes acíclicas con longitudes de arco arbitrarias y a problemas de camino más corto con longitudes de arco no negativas. Sin embargo, los algoritmos de corrección de etiquetas son más generales y pueden aplicarse a todos los tipos de problemas, incluso a aquellos con longitudes totales negativas, por lo que ofrece más flexibilidad algorítmica. Sin embargo, los algoritmos de configuración de etiquetas son más eficientes. Podemos ver los algoritmos de etiquetas como casos particulares de algoritmos de correcicón de etiquetas. 3.4. Algoritmo para el problema del camino más corto en redes acíclicas Como ya sabemos, una red es acíclica si no contiene ningún ciclo dirigido (véase la definición 1.10). En esta sección, veremos como resolver el problema del camino más corto 26 CAPÍTULO 3. DEFINICIÓN, ANÁLISIS Y TIPOS DE ALGORITMOS en tiempo O(m)cuando la red es acíclica. Nótese que ningún algoritmo puede resolver el problema del camino más corto en redes acíclicas en un tiempo menor, ya que para resolverlo necesitaríamos examinar cada arco. Tengamos en cuenta que en una red acíclica G= (N, A)siempre podemos establecer lo que se conoce como orden topológico, es decir, podemos numerar los nodos, en tiempo O(m), de manera que i < j para cada arco (i, j)∈A. Supongamos que calculamos cada d(i), que es la distandia más corta del nodo s a los nodos i= 1,2, . . . , k −1. El orden topológico establece que todos los arcos dirigidos al nodo kproceden de un nodo i, donde i∈ {1,2, . . . , k −1}. Como ya vimos, el camino más corto al nodo kes el camino más corto a uno de los nodos. Por tanto, para calcular el camino más corto al nodo k, lo que tenemos que hacer es calcular min{d(i) + cik}para todos los arcos (i, k). Como para implementar el algoritmo necesitamos acceder a todos los arcos dirigidos a cada nodo, lo que haremos es utilizar la lista de adyacencia A(i)de cada nodo i∈N. A continuación, decribimos los pasos del algoritmo: Empezamos estableciendo d(s) = 0, donde ses el nodo fuente, y le damos un valor muy grande al resto de etiquetas de distancia. Analizamos, en orden topológico, cada nodo y, para cada nodo i, construimos la lista de adyacencia A(i). Si para alguna arista (i, j)∈A se cumple que d(j)> d(i)+cij, ponemos d(j) = d(i)+cij. Una vez que el algoritmo analiza todos los nodos una vez en el orden indicado, las etiquetas de distancia son óptimas. Demostración 3.16.Demostramos por inducción que cuando el algoritmo examina un nodo, su etiqueta de distancia es óptima. Supongamos que el algoritmo ha examinado los nodos 1,2, . . . , k y sus etiquetas de distancia son óptimas. A continuación, examinaremos el nodo k+1. Sea s=i1−i2−· · ·− ih−k+1 el camino más corto del nodo sal nodo k, entonces, s=i1−i2− · · · − ihserá el camino más corto de sal nodo ih. Como tenemos los nodos ordenados en el orden topológico, (ih, k + 1) ∈Aimplica que ih∈1,2, . . . , k y, por hipótesis de inducción, sabemos que la etiqueta de distancia del nodo ihes igual a la longitud del camino i1−i2− · · · − ih, al examinar el nodo ih, el algoritmo debe haber analizado el arco (ih, k + 1) y establecer la etiqueta de distancia del nodo k+ 1 igual a la longitud del camino i1−i2− · · ·−ih−k+1. En consecuencia, cuando el algoritmo examina el nodo k+ 1, su etiqueta de distancia es óptima. Establecemos ahora el siguiente resultado. Teorema 3.17. El algoritmo de alcance resuelve el problema del camino más corto en redes acíclicas en tiempo O(m) 3.4. ALGORITMO EN REDES ACÍCLICAS 27 En esta sección, hemos visto como resolver un problema del camino más corto en caso de tener una red que es acíclica con el algoritmo más simple posible. Pero no podemos aplicar este algoritmo de un paso y cada arco exactamente una vez cuando la red contiene algún ciclo. Sin embargo, esta estrategia de alcance se puede utilizar para resolver cualquier problema del camino más corto con longitudes de arco no negativas, pero en este caso no tendríamos un orden establecido de los nodos y en cada paso tendríamos que investigar varios nodos para determinar de qué nodo llegar. 34 CAPÍTULO 4. ALGORITMOS DE CONFIGURACIÓN DE ETIQUETAS nodos de este depósito de uno en uno, diremos que están etiquetados permanentemente y escanearemos sus listas de adyacencia para actualizar las etiquetas de distancia de los nodos adyacentes. Cuando actualizamos la etiqueta de distancia de un nodo ide d1ad2, movemos el nodo ide contenido(d1)acontenido(d2). En la siguiente operación de selección de nodos, volvemos a examinar los depósitos numerados k+1, k +2, . . . para seleccionar el siguiente que sea no vacío. Sabemos que los depósitos 0,1,2, . . . , k estarán vacíos, debido a la propiedad 4.3, y el algoritmo no necesita examinarlos de nuevo. Almacenamos el contenido de cada contenido(k)como una lista doblemente enlazada (ver la definición 1.16) porque esta estructura de datos nos permite realizar cada una de las siguiente operaciones en tiempo O(1): 1. Verificar si un depósito está vacío o no. 2. Eliminar un elemento de un depósito. 3. Agregar un elemento a un depósito. Por tanto, el algoritmo necesitará un tiempo total O(m)para realizar todas las actualizaciones de distancia. La operación más complicada en este procedimiento es analizar los nC + 1 depósitos durante la selección de nodos. En consecuencia, el tiempo de ejecución del algoritmo de Dial es O(m+nC). Como nC + 1 es un número muy grande, la siguiente propiedad nos permite reducir el número de depósitos a C+ 1. Propiedad 4.4. Si d(i)es la etiqueta de distancia que el algoritmo designa como permanente al comienzo de una iteración, entonces al final de esa iteración, d(j)≤d(i)+Cpara cada nodo jetiquetado de forma finita. Esto se debe a que, por la propiedad 4.3,d(l)≤d(i)para cada nodo l∈S. Además, para cada j∈S, se tiene que d(j) = d(l) + clj para algún nodo l∈S, debido a la propiedad de actualizaciones de distancia. Por tanto, d(j) = d(l) + clj ≤d(i) + C. Esto quiere decir que todas las etiquetas temporales finitas están entre d(i)yd(i)+C. Por tanto, C+1 depósitos son suficientes para almacenar nodos con etiquetas de distancia temporales finitas. Por tanto, el algoritmo de Dial utiliza C+ 1 depósitos numerados 0,1,2, . . . que podemos ver ordenados en forma circular en la imagen 4.1. Un nodo ique está etiquetado de manera temporal con la etiqueta de distancia d(i)lo almacenamos en el cubo d(i) m´od C+ 1. En consecuencia, el depósito kalmacena nodos con etiquetas de distancia temporales k, k + (C+ 1), k + 2(C+ 1), . . . y así sucesivamente. 4.3. ALGORITMO DE RADIX-HEAP 35 Figura 4.1: Algoritmo de Dial Pero, en algún momento, este depósito solamente contendrá nodos con la misma etiqueta de distancia, debido a la propiedad 4.4. Esto implica que si el cubo kcontiene un nodo con la etiqueta de distancia mínima, entonces el cubo k+ 1, k + 2, . . . , C, 0,1,2, . . . , k −1 almacena nodos en valores crecientes de las etiquetas de distancia. Una posible desventaja del algoritmo de Dial en comparación con la implementación O(n2)original del algoritmo de Dijkstra es que necesita mucho espacio de almacenamiento cuando Ces muy grande. Además, el tiempo de cálculo puede ser grande porque el algoritmo puede actualizarse hasta n−1veces. El algoritmo es pseudopolinomial, ya que se ejecuta en tiempo O(m+nC). Sin embargo, casi nunca alcanza este límite, por lo que el tiempo de ejecución del algoritmo de Dial es mucho mejor que el indicado por su complejidad en el peor caso. 4.3. Algoritmo de Radix-Heap La implementación Radix-Heap del algoritmo de Dijkstra es una combinación entre la implementación original O(n2)y la implementación del Dial, que utiliza nC + 1 depósitos. La implementación original del algoritmo de Dijkstra considera todos los nodos que están etiquetados de manera permanente juntos, es decir, los almacena todos en el mismo depósito. Por otra parte, el algoritmo de Dial utiliza muchos depósitos y almacena nodos con diferentes etiquetas de distancia en depósitos diferentes. La implementación que presentamos en esta sección adopta un punto medio y mejora estos dos métodos. Almacena etiquetas en varios depósitos, pero que no serán muchos. Por ejemplo, en vez de almacenar solo los nodos con una etiqueta temporal ken el k-ésimo depósito, podríamos almacenar etiquetas temporales de 100ka100k+ 99 en el depósito k. Las diferentes etiquetas temporales que se pueden almacenar en un cubo o depósito determinan su rango y la cardinalidad del rango se denomina anchura. Para el anterior ejemplo, el rango del depósito es (100k, 100k+99) y su longitud es 100. El uso de estas anchuras de tamaño kpermite reducir el número de depósitos necesarios por un factor de k, pero para encontrar la etiqueta de distancia más pequeña, tenemos que buscar todos los elementos en el depósito no vacío 36 CAPÍTULO 4. ALGORITMOS DE CONFIGURACIÓN DE ETIQUETAS que tenga el índice más pequeño. Además, si kes grande, solo necesitaremos un depósito, y el algoritmo resultante se reduce a la implementación original del algoritmo de Dijkstra. La implementación con Radix-Heap que consideramos a continuación utiliza diferentes anchuras y cambia los rangos de manera dinámica. En esta versión que presentamos se cumple que: Proposición 4.5. Introducimos las siguientes propiedades del algoritmo: 1. Las anchuras de los depósitos son 1,1,2,4,8,16,..., de modo que el número de depósitos necesarios es solo O(log(nC)). 2. Modificamos los rangos de los cubos y reasignamos las etiquetas temporales de los nodos, de forma que siempre se almacena la etiqueta de distancia mínima en el depósito de anchura 1. La primera propiedad de la proposición anterior nos permite mantener solamente O(log(nC)) depósitos y, por tanto, evita el inconveniente del Dial de usar demasiados cubos. La segunda propiedad evita la necesidad de buscar en todo el depósito para encontrar un nodo con la etiqueta de distancia mínima. Cuando implementamos el algoritmo Radix-Heap de esta manera, su tiempo de ejecución es O(m+nlog(nC)). Para un problema del camino más corto, el algoritmo consta de d1 + log(nC)edepósitos. Estos cubos se enumeran 0,1,2, . . . , K =dlog(nC)e. Denotaremos el rango del cubo kpor rango(k)que es un intervalo cerrado de números enteros, posiblemente vacío y, como ya vimos, contenido(k) denota los nodos del depósito k. Cada vez que el algoritmo modifica los rangos de los depósitos, redistribuye los nodos en estos. Inicialmente, los depósitos tienen los siguientes rangos: rango(0) = [0] rango(1) = [1] rango(2) = [2,3] rango(3) = [4,7] rango(4) = [8,15] . . . rango(k) = [2k−1,2k−1] A medida que se ejecuta el algoritmo, estos rangos cambian, pero las anchuras de los cubos nunca aumentan más que las iniciales. En conclusión, cada vez que el algoritmo encuentra que los nodos con la etiqueta de distancia mínima están en un depósito con una anchura mayor que 1, examina todos los nodos 4.3. ALGORITMO DE RADIX-HEAP 37 de ese depósito para identificar un nodo con la etiqueta de distancia mínima. Por tanto, el algoritmo reorganiza el rango del depósito y cambia cada nodo al depósito de índice inferior. Como esta implementación contiene Kdepósitos, un nodo puede deplazarse como máximo Kveces, con lo cual el número total de examinación de nodos es O(nK). Ejemplo 4.6. Ilustramos ahora esta implementación para el problema del camino más corto. Consideramos el siguiente grafo, donde los números en los arcos representan la longitud entre los diferentes nodos: 1 2 3 4 5 6 7 8 9 10 1 7 7 2 6 3 4 3 4 3 5 9 6 4 26 7 16 En este grafo, se tiene que : C= 9 yK=dlog(900)e= 10 2. Por tanto, en la etapa inicial del algoritmo tendremos: nodo i1 2 3 4 5 6 7 8 9 10 etiqueta d(i)0677∞ ∞ ∞ ∞ ∞ ∞ cubo k0 1 2 3 4 5 6 rango(k) [0] [1] [2,3] [4,7] [8,15] [16,31] [32,63] contenido (k)∅ ∅ ∅ {2,3,4} ∅ ∅ ∅ cubo k7 8 9 10 rango (k) [64,127] [128,255] [256,511] [512,1023] contenido (k)∅ ∅ ∅ ∅ 2Utilizamos el logaritmo en base 2 (binario). 38 CAPÍTULO 4. ALGORITMOS DE CONFIGURACIÓN DE ETIQUETAS Las tablas anteriores representan las etiquetas de distancia determinadas por el algoritmo de Dijktra después de haber examinado el primer nodo, y muestra también el algoritmo Radix-Heap. Para elegir el nodo con la etiqueta de distancia más pequeña. examinamos los cubos 0,1,2, . . . , K para encontrar el primer cubo no vacío. El primer (y único) cubo no vacío que tenemos en la primera etapa es el cubo 3, que contiene a los nodos 2, 3 y 4. Como el rango de este cubo contiene más de un número entero, no es necesario que el primer nodo del cubo tenga la etiqueta de distancia mínima. En nuestro ejemplo, el rango del cubo 3 es [4,7], pero la etiqueta de distancia más pequeña en ese cubo es 6. Por tanto, redistribuimos el rango del cubo 3 a [6,7] entre los segmentos de indice inferior de la siguiente manera: rango(0) = [6] rango(1) = [7] rango(2) = ∅ rango(3) = ∅ El rango de los otros cubos no cambia. El rango del cubo 3 está vacío y tenemos que reasignar el contenido del cubo 3 a los cubos 0,1,2. Para eso, seleccionamos los nodos del cubo 3, escaneamos secuencialmente los cubos 2,1,0 e insertamos los nodos en el cubo adecuado. Los depósitos resultantes tienen el siguiente contenido: contenido(0) = {2} contenido(1) = {3,4} contenido(2) = ∅ contenido(3) = ∅ Esta redistribución vacía el cubo 3 y mueve el nodo con la etiqueta de distancia más pequeña al cubo 0. Ahora, ya podemos analizar la complejidad del algoritmo. Supongamos que j∈contenido(k) y que reasignamos el nodo ja un cubo de menor índice. Si d(j)/∈rango(k), escaneamos los cubos de manera secuencial con índices más bajos de derecha a izquierda y agregamos el 4.3. ALGORITMO DE RADIX-HEAP 39 nodo en el cubo correspondiente. En general, esta operación requiere O(m+nK)tiempo, donde mdenota el número de actualizaciones de distancia, y el término nK es consecuencia de que cada vez que movemos un nodo, lo movemos a un depósito con un índice más bajo: dado que tenemos K+1 cubos, un nodo podrá moverse, como máximo, Kveces. Entonces, O(nK)es un límite en el número total de movimientos de nodos. Consideramos ahora la operación de selección de nodos, que comienza escaneando los cubos de izquierda a derecha para identificar el primer cubo no vacío. Supongamos que este primer cubo no vacío es el cubo k. Esta operación necesita O(K)tiempo por iteración y tiempo O(nK)en total. Si k= 0,1, entonces cualquier nodo en ese cubo tiene la etiqueta de distancia mínima. Por otra parte, si k≥2, redistribuimos el rango del depósito ken los depósitos 0,1, . . . , k −1 y reinsertamos su contenido en esos cubos. Es decir, si el rango del depósito kes [l, u]y la etiqueta de distancia más pequeña de un nodo en ese depósito es dmin, el rango útil del depósito será [dmin, u]. El algoritmo redistribuye el rango útil de la siguiente forma: asignamos el primer número entero al cubo 0, después el siguiente entero al cubo 1, los dos siguientes al cubo 2, y así sucesivamente. Como el cubo ktiene un ancho menos que 2k−1 y los anchos de los primeros kcubos pueden ser 1,1,2,...,2k−2para un ancho potencial total de 2k−1, podemos redistribuir el rango útil del cubo entre los cubos 0,1, . . . , k −1 de la forma que explicamos. Esta redistribución de rangos vacía el depósito ky mueve los nodos con las etiquetas de distancia más pequeñas al depósito 0. La redistribución de rangos requiere O(K)tiempo por iteración y O(nK)tiempo en todas las iteraciones. En consecuencia, el tiempo que requiere el algoritmo es O(m+nK). Como K=dlog(nC)e, el algoritmo se ejecuta en O(m+nlog(nC)) tiempo. Teorema 4.7. La implementación Radix-Heap del algoritmo de Dijkstra resuelve el problema del camino más corto en O(m+nlog(nC)) tiempo. Este algoritmo requiere 1 + dlog(nC)edepósitos. Como en el algoritmo de Dial, la propiedad 4.4 nos permite reducir el número de cubos a 1+d(logC)e. Esta implementación del algoritmo se ejecuta en tiempo O(m+nlogC). Capítulo 5 Algoritmos de corrección de etiquetas para el problema del camino más corto En el capítulo anterior hemos visto diferentes algoritmos para resolver problemas del camino más corto cuando las longitudes de arco son no negativas. Pero este problema es más difícil de resolver cuando las redes tienen costes arbitrarios. La teoría de la complejidad computacional clasifica el problema del camino más corto para las redes con ciclos negativos como un problema NP −completo, por lo que resolverlo equivale a resolver muchos problemas en los campos de la combinatoria y la programación entera. En consecuencia, difícilmente podremos diseñar algoritmos de tiempo polinomial para la configuración de estos problemas, pero podemos describir algoritmos polinomiales que detecten un ciclo negativo cuando exista. Básicamente, todos los algoritmos del camino más corto se basan en las etiquetas de distancia. El algoritmo más básico que consideraremos en este capítulo, que es el algoritmo genérico de corrección de etiquetas, que reduce la etiqueta de distancia de un nodo en cada iteración al considerar solamente información local, es decir, la longitud del arco y las etiquetas de distancia actuales de sus nodos adyacentes. Bajo el supuesto de costes enteros, las etiquetas de distancia serán enteras y, por tanto, el algoritmo genérico siempre será finito. Pero también queremos trabajar con algoritmos que no solo sean finitos, sino que requieran una cantidad de cálculos que crezcan polinomialmente en el tamaño del problema. Comenzaremos este capítulo hablando de las condiciones de optimalidad, que nos permiten decidir cuándo un conjunto de etiquetas de distancia es óptimo. Estas condiciones nos permiten saber cuando una solución factible de nuestro problema es 41 42 CAPÍTULO 5. ALGORITMOS DE CORRECCIÓN DE ETIQUETAS óptima y, cuando una posible solución no satisface estas condiciones, nos sugieren cómo podríamos modificar la solución actual para que se acerce más a la óptima. Los algoritmos de corrección de etiquetas establecen d(s)=0, donde ses el nodo origen, y mantienen una etiqueta de distancia d(i), para cada nodo i∈N, que es una aproximación de la distancia del camino más corto de “prueba” del nodo sal nodo iy que, finalmente, es la etiqueta del camino más corto. 5.1. Condiciones de optimalidad Si las etiquetas de distancia son distancias de los caminos más cortos, deben satisfacer la siguiente condición: d(j)≤d(i) + cij ∀(i, j)∈A(5.1) Esto quiere decir que la longitud del camino más corto al nodo jno es mayor que la longitud del camino más corto de saimás la longitud del arco (i, j), para cada (i, j)∈A. Por el contrario, si d(j)> d(i) + cij ∀(i, j)∈A, podemos mejorar la longitud del camino más corto al nodo jpasando por el nodo i, pero esto contradice la optimalidad de la etiqueta de distancia d(j). Además, si cada d(j)representa la longitud de algún camino dirigido de sajy esta solución satisface (5.1), entonces debe ser óptima. Consideremos cualquier solución d(j)que verifique (5.1). Sea s=i1−i2− · · · − ik=j, cualquier camino dirigido Pde saj, se tiene que: d(j) = d(ik)≤d(ik−1) + cik−1ik, d(ik−1)≤d(ik−2) + cik−2ik−1, . . . d(i2)≤d(i1) + ci1i2=ci1i2 La última igualdad se debe a que d(i1) = d(s)=0. Sumando estas desigualdades, obtenemos que: d(j) = d(ik)≤cik−1ik+cik−2ik−1+cik−3ik−2+· · · +ci1i2=X (i,j)∈P cij Entonces d(j)es un límite inferior en la longitud de cualquier camino dirigido desde shasta j. Como d(j)es la longitud de algún camino dirigido desde saj, también es un límite superior en la longitud del camino más corto. En conclusión, d(j)es la longitud del camino más corto y establecemos el siguiente resultado: 5.2. DETECCIÓN DE CICLOS NEGATIVOS 43 Teorema 5.1 (Condiciones de optimalidad del camino más corto).Para cada nodo j∈N, sea d(j)la longitud de algún camino dirigido desde el nodo origen al nodo j. Entonces, las etiquetas d(j)representan distancias de caminos más cortos si y solo si satisfacen las siguientes condiciones de optimización de camino más corto: d(j)≤d(i) + cij ∀(i, j)∈A(5.2) Definimos ahora la longitud de arco reducida cd ij de un arco (i, j)con respecto a las etiquetas de distancia d(·)como cd ij =cij +d(i)−d(j). Introducimos a continuación unas propiedades que serán útiles más tarde. Proposición 5.2. 1. Para cualquier ciclo dirigido W, se tiene que: P(i,j)∈Wcd ij =P(i,j)∈Wcij 2. Para cualquier camino dirigido Pdesde el nodo kal nodo l, se verifica: P(i,j)∈Pcd ij =P(i,j)∈Pcij +d(k)−d(l) 3. Si d(·)representa las distancias de caminos más cortos, entonces cd ij ≥0para cada arco (i, j)∈A. La tercera propiedad se obtiene directamente del teorema 5.1. Nótese que si la red tiene un ciclo negativo, ningún conjunto de etiquetas satisface 5.2. Supongamos que Gtiene un ciclo dirigido W. Entonces, por la propiedad 5.2,P(i,j)∈Wcd ij 6= 0 y, por tanto, Wno puede ser un ciclo negativo. 5.2. Detección de ciclos negativos Hasta ahora, hemos supuesto que no hay costes negativos y hemos descrito algoritmos que resuelven este tipo de problemas del camino más corto. En esta sección vamos a permitir costes negativos y veremos qué modificaciones son necesarias para que los algoritmos detecten la presencia de ciclos negativos. Como ya hemos dicho, si el grafo contiene un ciclo negativo, ningún conjunto de etiquetas de distancia cumple las condiciones de optimalidad y el algoritmo de corrección de etiquetas reducirá las etiquetas de distancia indefinidamente y no terminará.. Sin embargo, acabaríamos los cálculos si encontramos que la etiqueta de 50 CAPÍTULO 6. APLICACIONES DEL PROBLEMA DEL CAMINO MÁS CORTO m´ax Pn k=1 ukxk sujeto a Pn k=1 pkxk≤P xk∈ {0,1}k∈ {1, . . . , n} Donde xkes 0 si no metemos el objeto en la mochila y 1 en otro caso. El problema de la mochila es un problema NP-completo, pero existen algoritmos aproximados completamente polinomiales y algoritmos “pseudo-polinomiales” para resolverlo. Como vamos a ver a continuación, prácticamente cualquier problema de programación dinámica se puede reformular como un problema de camino más corto. Lo que haremos será plantear el problema como un problema del camino más largo (para pasarlo a un problema del camino más corto, cambiamos el signo a la longitud de todos los arcos) 1. Formulamos el problema de la siguiente forma: tenemos un nodo origen y un nodo destino y, para cada objeto i, tenemos una columna con P+ 1 nodos i0, i1, . . . , iP. El nodo ijrepresenta que los objetos 1, . . . , i consumen junidades de la capacidad de la mochila. De cada nodo salen dos arcos hacia la siguiente columna que representa la entrada o no entrada del objeto de esa columna en la mochila, y solamente saldrá uno si ese objeto no cabe ya en la mochila. El arco de no entrada tendrá utilidad 0 y el de entrada tiene la utilidad asociada a dicho objeto. Pongamos, por ejemplo, un caso en el que el peso máximo es P= 5 y la siguiente tabla representa las utilidades y los pesos de cada uno de los 4 objetos que podemos introducir en la mochila: k1 2 3 4 uk30 20 10 15 pk3 2 1 2 Entonces, por lo que dijimos en el anterior párrafo, el grafo tendría 4 “columnas” y 6 “filas”: 1Tenemos que tener cuidado de no obtener un ciclo de longitud total negativa. 6.1. EL PROBLEMA DE LA MOCHILA 51 O10203040 11213141 12223242 13233343 14243444 15253545 D 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 20 10 10 10 10 10 10 10 10 10 Por ejemplo, el camino O−10−22−33−45−Dindica que los elementos 2, 3 y 4 entrarían en la mochila. Además del problema de la mochila, existen muchas otras aplicaciones del problema del camino más corto a la vida real. Una aplicación curiosa del camino más corto es, por ejemplo, la teoría de los Seis grados de separación, que es la idea de intentar probar que cualquier persona está conectada con cualquier otra mediante una cadena de, como mucho, seis personas. Otra aplicación interesante es la de los dispositivos gps, los cuales nos indican el camino más corto desde el punto en el que nos encontramos y cualquier destino al que queramos llegar. En la realidad, varios departamentos económicos necesitan realizar consultas de redes de transporte a gran escala, los departamentos de logística deben cruzar ciudades y provincias para el transporte, los departamentos de turismo deben ir a atracciones turísticas lejos de las áreas urbanas, etc. 52 CAPÍTULO 6. APLICACIONES DEL PROBLEMA DEL CAMINO MÁS CORTO También cabe destacar que, otro ejemplo, son las empresas (tiendas, grandes almacenes, mensajeros, etc.) que necesitan repartir sus pedidos a diferentes lugares del mundo. Lo que hacen es diseñar el camino más corto para poder entregar todos los pedidos lo más rápido y económico posible. Para eso, tendrán en cuenta los lugares que deben visitar, la disponibilidad de los clientes para entregar los pedidos, el tiempo que tardará en llegar a cada sitio, etc. Bibliografía [1] González-Díaz, J. (2021): Apuntes de Programación Lineal y Entera, Universidad de Santiago de Compostela, Grado en Matemáticas. [2] K. Ahuja R. , L. Magnanti T. , B. Orlin J. (1993), Network Flows. Theory, Algorithms, and Applications. 53