En algoritmos de grafos , el problema de la ruta más ancha es el problema de encontrar una ruta entre dos vértices designados en un grafo ponderado , maximizando el peso de la arista de peso mínimo en la ruta. El problema de la ruta más ancha también se conoce como el problema de la ruta de capacidad máxima . Es posible adaptar la mayoría de los algoritmos de ruta más corta para calcular las rutas más anchas, modificándolos para usar la distancia del cuello de botella en lugar de la longitud de la ruta. [1] Sin embargo, en muchos casos son posibles algoritmos incluso más rápidos.
Por ejemplo, en un gráfico que representa conexiones entre enrutadores en Internet , donde el peso de un borde representa el ancho de banda de una conexión entre dos enrutadores, el problema de la ruta más ancha es el problema de encontrar una ruta de extremo a extremo entre dos nodos de Internet que tenga el máximo ancho de banda posible. [2] El peso de borde más pequeño en esta ruta se conoce como la capacidad o ancho de banda de la ruta. Además de sus aplicaciones en el enrutamiento de red, el problema de la ruta más ancha también es un componente importante del método Schulze para decidir el ganador de una elección multidireccional, [3] y se ha aplicado a la composición digital , [4] el análisis de la ruta metabólica , [5] y el cálculo de flujos máximos . [6]
Un problema estrechamente relacionado, el problema de la ruta minimax o problema de la ruta más corta en el cuello de botella, solicita la ruta que minimice el peso máximo de cualquiera de sus aristas. Tiene aplicaciones que incluyen la planificación del transporte . [7] Cualquier algoritmo para el problema de la ruta más ancha se puede transformar en un algoritmo para el problema de la ruta minimax, o viceversa, invirtiendo el sentido de todas las comparaciones de peso realizadas por el algoritmo, o equivalentemente reemplazando cada peso de la arista por su negación.
En un gráfico no dirigido , se puede encontrar un camino más ancho como el camino entre los dos vértices en el árbol de expansión máxima del gráfico, y se puede encontrar un camino minimax como el camino entre los dos vértices en el árbol de expansión mínima. [8] [9] [10] Se deduce inmediatamente de esta equivalencia que todos los pares de caminos más anchos en un gráfico no dirigido de -vértice se pueden calcular en tiempo . [11]
En cualquier grafo, dirigido o no, existe un algoritmo sencillo para encontrar el camino más ancho una vez que se conoce el peso de su arista de peso mínimo: simplemente elimine todas las aristas más pequeñas y busque cualquier camino entre las aristas restantes utilizando una búsqueda en amplitud o una búsqueda en profundidad . Con base en esta prueba, también existe un algoritmo de tiempo lineal para encontrar el camino más ancho s - t en un grafo no dirigido, que no utiliza el árbol de expansión máxima. La idea principal del algoritmo es aplicar el algoritmo de búsqueda de caminos en tiempo lineal al peso medio de la arista en el grafo, y luego eliminar todas las aristas más pequeñas o contraer todas las aristas más grandes según exista o no un camino, y recurrir al grafo más pequeño resultante. [9] [12] [13]
Fernández, Garfinkel y Arbiol (1998) utilizan rutas más cortas de cuello de botella no dirigidas para formar fotografías aéreas compuestas que combinan múltiples imágenes de áreas superpuestas. En el subproblema al que se aplica el problema de la ruta más amplia, ya se han transformado dos imágenes en un sistema de coordenadas común ; la tarea restante es seleccionar una costura , una curva que pasa por la región de superposición y divide una de las dos imágenes de la otra. Los píxeles de un lado de la costura se copiarán de una de las imágenes, y los píxeles del otro lado de la costura se copiarán de la otra imagen. A diferencia de otros métodos de composición que promedian los píxeles de ambas imágenes, esto produce una imagen fotográfica válida de cada parte de la región que se está fotografiando. Ponderan los bordes de un gráfico de cuadrícula mediante una estimación numérica de cuán visualmente aparente sería una costura a través de ese borde, y encuentran una ruta más corta de cuello de botella para estos pesos. Al utilizar este camino como costura, en lugar de un camino más corto más convencional, su sistema encuentra una costura que es difícil de discernir en todos sus puntos, en lugar de permitirle intercambiar una mayor visibilidad en una parte de la imagen por una menor visibilidad en otra parte. [4]
Se puede utilizar una solución al problema de la ruta minimax entre las dos esquinas opuestas de un gráfico de cuadrícula para encontrar la distancia de Fréchet débil entre dos cadenas poligonales . Aquí, cada vértice del gráfico de cuadrícula representa un par de segmentos de línea, uno de cada cadena, y el peso de una arista representa la distancia de Fréchet necesaria para pasar de un par de segmentos a otro. [14]
Si todos los pesos de los bordes de un grafo no dirigido son positivos , entonces las distancias minimax entre pares de puntos (los pesos máximos de los bordes de los caminos minimax) forman un ultramétrico ; a la inversa, todo espacio ultramétrico finito proviene de distancias minimax de esta manera. [15] Una estructura de datos construida a partir del árbol de expansión mínimo permite consultar la distancia minimax entre cualquier par de vértices en tiempo constante por consulta, utilizando consultas de ancestro común más bajo en un árbol cartesiano . La raíz del árbol cartesiano representa el borde más pesado del árbol de expansión mínimo, y los hijos de la raíz son árboles cartesianos construidos recursivamente a partir de los subárboles del árbol de expansión mínimo formados al eliminar el borde más pesado. Las hojas del árbol cartesiano representan los vértices del grafo de entrada, y la distancia minimax entre dos vértices es igual al peso del nodo del árbol cartesiano que es su ancestro común más bajo. Una vez que se han ordenado los bordes del árbol de expansión mínimo, este árbol cartesiano se puede construir en tiempo lineal. [16]
En los grafos dirigidos , no se puede utilizar la solución del árbol de expansión máxima. En su lugar, se conocen varios algoritmos diferentes; la elección de cuál algoritmo utilizar depende de si se fija un vértice de inicio o de destino para la ruta, o si se deben encontrar rutas para muchos vértices de inicio o de destino simultáneamente.
El problema de la ruta más amplia de todos los pares tiene aplicaciones en el método Schulze para elegir un ganador en elecciones con múltiples candidatos en las que los votantes clasifican a los candidatos en orden de preferencia . El método Schulze construye un grafo dirigido completo en el que los vértices representan a los candidatos y cada dos vértices están conectados por una arista. Cada arista está dirigida del ganador al perdedor de una contienda por pares entre los dos candidatos que conecta, y está etiquetada con el margen de victoria de esa contienda. Luego, el método calcula las rutas más amplias entre todos los pares de vértices, y el ganador es el candidato cuyo vértice tiene rutas más amplias hacia cada oponente que viceversa. [3] Los resultados de una elección que utiliza este método son consistentes con el método Condorcet (un candidato que gana todas las contiendas por pares automáticamente gana toda la elección), pero generalmente permite seleccionar un ganador, incluso en situaciones en las que el método Condorcet en sí falla. [17] El método Schulze ha sido utilizado por varias organizaciones, incluida la Fundación Wikimedia . [18]
Para calcular los anchos de ruta más amplios para todos los pares de nodos en un gráfico dirigido denso , como los que surgen en la aplicación de votación, el enfoque conocido asintóticamente más rápido toma tiempo O ( n (3+ω)/2 ) donde ω es el exponente para la multiplicación rápida de matrices . Usando los algoritmos más conocidos para la multiplicación de matrices, este límite de tiempo se convierte en O ( n 2.688 ) . [19] En cambio, la implementación de referencia para el método Schulze usa una versión modificada del algoritmo Floyd–Warshall más simple , que toma tiempo O ( n 3 ) . [3] Para gráficos dispersos , puede ser más eficiente aplicar repetidamente un algoritmo de ruta más ancha de una sola fuente.
Si las aristas se ordenan por sus pesos, entonces una versión modificada del algoritmo de Dijkstra puede calcular los cuellos de botella entre un vértice de inicio designado y cada uno de los demás vértices del grafo, en tiempo lineal. La idea clave detrás de la aceleración sobre una versión convencional del algoritmo de Dijkstra es que la secuencia de distancias de cuello de botella a cada vértice, en el orden en que los vértices son considerados por este algoritmo, es una subsecuencia monótona de la secuencia ordenada de pesos de aristas; por lo tanto, la cola de prioridad del algoritmo de Dijkstra se puede implementar como una cola de cubos : una matriz indexada por los números de 1 a m (el número de aristas en el grafo), donde la celda i de la matriz contiene los vértices cuya distancia de cuello de botella es el peso de la arista con la posición i en el orden ordenado. Este método permite que el problema de la ruta más amplia se resuelva tan rápidamente como la ordenación ; por ejemplo, si los pesos de las aristas se representan como números enteros, entonces los límites de tiempo para la ordenación de números enteros de una lista de m números enteros se aplicarían también a este problema. [13]
Berman y Handler (1987) sugieren que los vehículos de servicio y los vehículos de emergencia deberían utilizar rutas minimax al regresar de una llamada de servicio a su base. En esta aplicación, el tiempo de regreso es menos importante que el tiempo de respuesta si se produce otra llamada de servicio mientras el vehículo está en proceso de regreso. Al utilizar una ruta minimax, donde el peso de un borde es el tiempo máximo de viaje desde un punto en el borde hasta la llamada de servicio más lejana posible, se puede planificar una ruta que minimice el retraso máximo posible entre la recepción de una llamada de servicio y la llegada de un vehículo que responde. [7] Ullah, Lee y Hassoun (2009) utilizan rutas maximin para modelar las cadenas de reacción dominantes en redes metabólicas ; en su modelo, el peso de un borde es la energía libre de la reacción metabólica representada por el borde. [5]
Otra aplicación de los caminos más amplios surge en el algoritmo de Ford-Fulkerson para el problema de flujo máximo . Aumentar repetidamente un flujo a lo largo de un camino de capacidad máxima en la red residual del flujo conduce a un límite pequeño, O ( m log U ) , en el número de aumentos necesarios para encontrar un flujo máximo; aquí, se supone que las capacidades de borde son números enteros que son como máximo U . Sin embargo, este análisis no depende de encontrar un camino que tenga el máximo exacto de capacidad; cualquier camino cuya capacidad esté dentro de un factor constante del máximo es suficiente. La combinación de esta idea de aproximación con el método de aumento de camino más corto del algoritmo de Edmonds-Karp conduce a un algoritmo de flujo máximo con un tiempo de ejecución O ( mn log U ) . [6]
Es posible encontrar caminos de máxima capacidad y caminos minimax con una única fuente y un único destino de manera muy eficiente incluso en modelos de cálculo que solo permiten comparaciones de los pesos de los bordes del gráfico de entrada y no aritmética sobre ellos. [13] [20] El algoritmo mantiene un conjunto S de bordes que se sabe que contienen el borde de cuello de botella del camino óptimo; inicialmente, S es solo el conjunto de todos los m bordes del gráfico. En cada iteración del algoritmo, divide S en una secuencia ordenada de subconjuntos S 1 , S 2 , ... de tamaño aproximadamente igual; el número de subconjuntos en esta partición se elige de tal manera que todos los puntos de división entre subconjuntos se pueden encontrar mediante la búsqueda repetida de la mediana en el tiempo O ( m ) . Luego, el algoritmo vuelve a ponderar cada borde del gráfico por el índice del subconjunto que contiene el borde, y utiliza el algoritmo Dijkstra modificado en el gráfico reponderado; Basándose en los resultados de este cálculo, puede determinar en tiempo lineal cuál de los subconjuntos contiene el peso del borde del cuello de botella. Luego reemplaza S por el subconjunto S i que ha determinado que contiene el peso del cuello de botella y comienza la siguiente iteración con este nuevo conjunto S . El número de subconjuntos en los que S se puede dividir aumenta exponencialmente con cada paso, por lo que el número de iteraciones es proporcional a la función logarítmica iterada , O ( log * n ) , y el tiempo total es O ( m log * n ) . [20] En un modelo de cálculo donde cada peso del borde es un entero de máquina, el uso de bisección repetida en este algoritmo se puede reemplazar por una técnica de división de listas de Han & Thorup (2002), lo que permite dividir S en O ( √ m ) conjuntos más pequeños S i en un solo paso y conduce a un límite de tiempo general lineal. [21]
También se ha considerado una variante del problema de la ruta minimax para conjuntos de puntos en el plano euclidiano . Al igual que en el problema del grafo no dirigido, este problema de la ruta minimax euclidiana se puede resolver de manera eficiente encontrando un árbol de expansión mínimo euclidiano : cada ruta en el árbol es una ruta minimax. Sin embargo, el problema se vuelve más complicado cuando se desea una ruta que no solo minimice la longitud del salto sino que también, entre rutas con la misma longitud de salto, minimice o minimice aproximadamente la longitud total de la ruta. La solución se puede aproximar utilizando llaves geométricas . [22]
En teoría de números , el problema no resuelto del foso gaussiano plantea la pregunta de si las trayectorias minimax en los números primos gaussianos tienen una longitud minimax acotada o ilimitada. Es decir, ¿existe una constante B tal que, para cada par de puntos p y q en el conjunto de puntos euclidianos infinitos definido por los primos gaussianos, la trayectoria minimax en los primos gaussianos entre p y q tiene una longitud de arista minimax como máximo B ? [23]
