En los algoritmos de gráficos , el problema de la ruta más amplia es el problema de encontrar una ruta entre dos vértices designados en un gráfico ponderado , maximizando el peso del borde de peso mínimo en la ruta. El problema de la ruta más amplia 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 amplia es el problema de encontrar una ruta de un extremo a otro entre dos nodos que tiene el máximo ancho de banda posible. [2] El peso de borde más pequeño en esta ruta se conoce como capacidad o ancho de banda de la ruta. Además de sus aplicaciones en el enrutamiento de la red, el problema de la ruta más amplia también es un componente importante del método Schulze para decidir el ganador de una elección de múltiples vías, [3] y se ha aplicado a la composición digital , [4] análisis de la ruta metabólica , [ 5] y el cálculo de los caudales máximos . [6]
Un problema estrechamente relacionado, el problema de la ruta minimax o el problema de la ruta más corta del cuello de botella solicita la ruta que minimiza el peso máximo de cualquiera de sus bordes. Tiene aplicaciones que incluyen la planificación del transporte . [7] Cualquier algoritmo para el problema de la ruta más amplia 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 de manera equivalente, reemplazando cada peso de borde por su negación. .
Gráficos no dirigidos
En un gráfico no dirigido , se puede encontrar una ruta más ancha como la ruta entre los dos vértices en el árbol de expansión máxima del gráfico, y una ruta minimax se puede encontrar como la ruta entre los dos vértices en el árbol de expansión mínimo. [8] [9] [10]
En cualquier gráfico, dirigido o no dirigido, existe un algoritmo sencillo para encontrar un camino más ancho una vez que se conoce el peso de su borde de peso mínimo: simplemente elimine todos los bordes más pequeños y busque cualquier camino entre los bordes restantes usando la búsqueda de amplitud o profundidad. primera búsqueda . Según esta prueba, también existe un algoritmo de tiempo lineal para encontrar una ruta s - t más amplia en un gráfico no dirigido, que no utiliza el árbol de expansión máximo. La idea principal del algoritmo es aplicar el algoritmo de búsqueda de ruta de tiempo lineal al peso medio del borde en el gráfico y luego eliminar todos los bordes más pequeños o contraer todos los bordes más grandes según si existe o no un camino. y recurse en el gráfico más pequeño resultante. [9] [11] [12]
Fernández, Garfinkel y Arbiol (1998) utilizan caminos más cortos de cuello de botella sin dirección 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 trayectoria 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. Ponen 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 un cuello de botella en la ruta más corta para estos pesos. El uso de este camino como la costura, en lugar de una ruta más corta más convencional, hace que su sistema encuentre 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 otros lugares. [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 un borde representa la distancia de Fréchet necesaria para pasar de un par de segmentos a otro. [13]
Si todos los pesos de los bordes de un gráfico no dirigido son positivos , entonces las distancias minimax entre pares de puntos (los pesos máximos de los bordes de las trayectorias minimax) forman una ultramétrica ; a la inversa, cada espacio ultramétrico finito proviene de distancias minimax de esta manera. [14] Una estructura de datos construida a partir del árbol de expansión mínimo permite que la distancia minimax entre cualquier par de vértices sea consultada en tiempo constante por consulta, utilizando consultas de ancestros comunes más bajos en un árbol cartesiano . La raíz del árbol cartesiano representa el borde del árbol de expansión mínimo más pesado, y los hijos de la raíz son árboles cartesianos construidos de forma recursiva a partir de los subárboles del árbol de expansión mínimo formado al eliminar el borde más pesado. Las hojas del árbol cartesiano representan los vértices del gráfico de entrada, y la distancia minimax entre dos vértices es igual al peso del nodo del árbol cartesiano que es su antepasado común más bajo. Una vez que se han ordenado los bordes mínimos del árbol de expansión, este árbol cartesiano se puede construir en tiempo lineal. [15]
Gráficos dirigidos
En gráficos dirigidos , no se puede utilizar la solución de árbol de expansión máxima. En cambio, se conocen varios algoritmos diferentes; la elección de qué algoritmo usar depende de si un vértice de inicio o de destino para la ruta es fijo, o si las rutas para muchos vértices de inicio o destino deben encontrarse simultáneamente.
Todos los pares
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 de múltiples vías en las que los votantes clasifican a los candidatos en orden de preferencia . El método de 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 ventaja se dirige del ganador al perdedor de un concurso por parejas entre los dos candidatos que conecta, y se etiqueta con el margen de victoria de ese concurso. Luego, el método calcula los caminos más anchos entre todos los pares de vértices, y el ganador es el candidato cuyo vértice tiene caminos más anchos para cada oponente que viceversa. [3] Los resultados de una elección que usa este método son consistentes con el método Condorcet - un candidato que gana todas las contiendas por parejas gana automáticamente todas las elecciones - pero generalmente permite que se seleccione un ganador, incluso en situaciones en las que el método Concorcet falla. . [16] El método Schulze ha sido utilizado por varias organizaciones, incluida la Fundación Wikimedia . [17]
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 el 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 ) . [18] 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 O ( n 3 ) tiempo. [3] Para gráficos dispersos , puede ser más eficiente aplicar repetidamente un algoritmo de ruta más amplia de fuente única.
Única fuente
Si los bordes se ordenan por sus pesos, entonces una versión modificada del algoritmo de Dijkstra puede calcular los cuellos de botella entre un vértice inicial designado y todos los demás vértices del gráfico, 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 borde; por lo tanto, la cola de prioridad del algoritmo de Dijkstra se puede implementar como una cola de depósito : una matriz indexada por los números de 1 a m (el número de aristas en el gráfico), donde la celda de la matriz i contiene los vértices cuya distancia de cuello de botella es el peso de el borde con la posición i en el orden ordenado. Este método permite resolver el problema de la ruta más amplia tan rápido como la clasificación ; por ejemplo, si los pesos de los bordes se representan como números enteros, entonces los límites de tiempo para ordenar enteros una lista de m enteros se aplicarían también a este problema. [12]
Fuente única y destino único
Berman y Handler (1987) sugieren que los vehículos de servicio y los vehículos de emergencia deben usar caminos minimax cuando regresan de una llamada de servicio a su base. En esta aplicación, el tiempo de devolución es menos importante que el tiempo de respuesta si se produce otra llamada de servicio mientras el vehículo está en proceso de devolución. 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 minimiza el retraso máximo posible entre la recepción de una llamada de servicio y la llegada de un vehículo de respuesta. [7] Ullah, Lee y Hassoun (2009) utilizan rutas de maximin para modelar las cadenas de reacción dominantes en las 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 caminos más amplios surge en el algoritmo de Ford-Fulkerson para el problema de flujo máximo . El aumento repetido de un flujo a lo largo de una ruta de capacidad máxima en la red residual del flujo conduce a un pequeño límite, O ( m log U ) , en el número de aumentos necesarios para encontrar un flujo máximo; aquí, las capacidades de borde se supone que son números enteros que son, como máximo, T . Sin embargo, este análisis no depende de encontrar una ruta 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 trayectoria más corta del algoritmo de Edmonds-Karp conduce a un algoritmo de flujo máximo con tiempo de ejecución O ( mn log U ) . [6]
Es posible encontrar rutas de máxima capacidad y rutas minimax con una sola fuente y un solo destino de manera muy eficiente incluso en modelos de cálculo que solo permiten comparaciones de los pesos de borde del gráfico de entrada y no aritmética en ellos. [12] [19] El algoritmo mantiene un conjunto S de bordes que se sabe que contienen el borde del cuello de botella de la ruta óptima; 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 aproximadamente el mismo tamaño; el número de subconjuntos en esta partición se elige de tal manera que todos los puntos de división entre subconjuntos se puedan 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 de 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. A continuación, sustituye a S por el subconjunto S i que ha determinado para contener el peso cuello de botella, y se inicia la siguiente iteración con esta nueva serie S . El número de subconjuntos en los que se puede dividir S 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 ) . [19] En un modelo de cálculo donde cada peso de borde es un entero de máquina, el uso de bisecciones repetidas en este algoritmo puede ser reemplazado por una técnica de división de listas de Han & Thorup (2002) , permitiendo que S se divida en O ( √ m ) conjuntos más pequeños S i en un solo paso y que conducen a un límite de tiempo general lineal. [20]
Conjuntos de puntos euclidianos
También se ha considerado una variante del problema de trayectoria minimax para conjuntos de puntos en el plano euclidiano . Al igual que en el problema del gráfico no dirigido, este problema de ruta minimax euclidiana se puede resolver de manera eficiente al encontrar 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 . [21]
En teoría de números , el problema del foso gaussiano no resuelto pregunta si las trayectorias minimax en los números primos gaussianos tienen una longitud minimax limitada o ilimitada. Es decir, ¿existe una constante B de tal manera que, para cada par de puntos p y q en el infinito conjunto de puntos euclidiana definido por los números primos de Gauss, el camino minimax en los primos de Gauss entre p y q tiene longitud de borde minimax como máximo B ? [22]
Referencias
- ^ Pollack, Maurice (1960), "La capacidad máxima a través de una red", Investigación de operaciones , 8 (5): 733–736, doi : 10.1287 / opre.8.5.733 , JSTOR 167387
- ^ Shacham, N. (1992), "Enrutamiento de multidifusión de datos jerárquicos", IEEE International Conference on Communications (ICC '92) , 3 , págs. 1217–1221, doi : 10.1109 / ICC.1992.268047 , hdl : 2060/19990017646 , ISBN 978-0-7803-0599-1; Wang, Zheng; Crowcroft, J. (1995), "Algoritmos de enrutamiento basados en retardo de ancho de banda", IEEE Global Telecommunications Conference (GLOBECOM '95) , 3 , págs. 2129-2133, doi : 10.1109 / GLOCOM.1995.502780 , ISBN 978-0-7803-2509-8
- ^ a b c Schulze, Markus (2011), "Un nuevo método de elección de un solo ganador monótono, independiente de clones, simétrico de reversión y consistente con Condorcet", Social Choice and Welfare , 36 (2): 267-303, doi : 10.1007 / s00355- 010-0475-4
- ^ a b Fernández, Elena ; Garfinkel, Robert; Arbiol, Roman (1998), "Mosaico de mapas fotográficos aéreos a través de uniones definidas por caminos más cortos de cuello de botella", Investigación de operaciones , 46 (3): 293–304, doi : 10.1287 / opre.46.3.293 , JSTOR 222823
- ^ a b Ullah, E .; Lee, Kyongbum; Hassoun, S. (2009), "Un algoritmo para identificar vías metabólicas de borde dominante", Conferencia internacional IEEE / ACM sobre diseño asistido por computadora (ICCAD 2009) , págs. 144-150
- ^ a b Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993), "7.3 Algoritmo de escalamiento de capacidad", Flujos de red: teoría, algoritmos y aplicaciones , Prentice Hall, págs. 210-212, ISBN 978-0-13-617549-0
- ^ a b Berman, Oded; Handler, Gabriel Y. (1987), "Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations", Transportation Science , 21 (2): 115-122, doi : 10.1287 / trsc.21.2.115
- ^ Hu, TC (1961), "El problema de la ruta de capacidad máxima", Investigación de operaciones , 9 (6): 898–900, doi : 10.1287 / opre.9.6.898 , JSTOR 167055
- ^ a b Punnen, Abraham P. (1991), "Un algoritmo de tiempo lineal para el problema de la ruta de capacidad máxima", European Journal of Operational Research , 53 (3): 402–404, doi : 10.1016 / 0377-2217 (91) 90073-5
- ^ Malpani, Navneet; Chen, Jianer (2002), "Una nota sobre la construcción práctica de rutas de ancho de banda máximo", Information Processing Letters , 83 (3): 175–180, doi : 10.1016 / S0020-0190 (01) 00323-4 , MR 1904226
- ^ Camerini, PM (1978), "The min-max spanning tree problem and some extensions", Information Processing Letters , 7 (1): 10-14, doi : 10.1016 / 0020-0190 (78) 90030-3
- ^ a b c Kaibel, Volker; Peinhardt, Matthias AF (2006), Sobre el problema del camino más corto del cuello de botella (PDF) , ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin
- ^ Alt, Helmut; Godau, Michael (1995), "Calcular la distancia de Fréchet entre dos curvas poligonales" (PDF) , International Journal of Computational Geometry and Applications , 5 (1–2): 75–91, doi : 10.1142 / S0218195995000064.
- ^ Leclerc, Bruno (1981), "Descripción combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (en francés) (73): 5–37, 127, MR 0623034
- ^ Demaine, Erik D .; Landau, Gad M .; Weimann, Oren (2009), "Sobre árboles cartesianos y consultas de rango mínimo", Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rodas, Grecia, 5 al 12 de julio de 2009 , Lecture Notes in Computer Science, 5555 , págs. . 341–353, doi : 10.1007 / 978-3-642-02927-1_29 , hdl : 1721.1 / 61963 , ISBN 978-3-642-02926-4
- ^ Más específicamente, el único tipo de vínculo que el método Schulze no logra romper es entre dos candidatos que tienen caminos igualmente amplios entre sí.
- ^ Véase Jesse Plamondon-Willard, Elección de la Junta para utilizar el voto preferencial , mayo de 2008; Mark Ryan, resultados de las elecciones de la junta directiva de Wikimedia 2008 , junio de 2008; Elecciones de la Junta de 2008 , junio de 2008; y Elecciones de la Junta Directiva de 2009 , agosto de 2009.
- ^ Duan, Ran; Pettie, Seth (2009), "Algoritmos rápidos para multiplicación de matrices (máx., Mín.) Y rutas más cortas de cuellos de botella", Actas del 20º Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '09) , págs. 384–391. Para ver un algoritmo anterior que también usaba la multiplicación rápida de matrices para acelerar todos los pares de caminos más anchos, consulte Vassilevska, Virginia ; Williams, Ryan ; Yuster, Raphael (2007), "Rutas de cuello de botella de todos los pares para gráficos generales en tiempo verdaderamente subcúbico ", Actas del 39º Simposio Anual de ACM sobre Teoría de la Computación (STOC '07) , Nueva York: ACM, págs. 585– 589, CiteSeerX 10.1.1.164.9808 , doi : 10.1145 / 1250790.1250876 , ISBN 9781595936318, MR 2402484 y el Capítulo 5 de Vassilevska, Virginia (2008), Algoritmos eficientes para problemas de ruta en gráficos ponderados (PDF) , Ph.D. tesis, Informe CMU-CS-08-147, Escuela de Ciencias de la Computación de la Universidad Carnegie Mellon
- ^ a b 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
- ^ Han, Yijie; Thorup, M. (2002), "Clasificación de enteros en O ( n √ log log n ) tiempo esperado y espacio lineal", Proc. 43 ° Simposio anual sobre los fundamentos de la informática (FOCS 2002) , págs. 135-144, doi : 10.1109 / SFCS.2002.1181890 , ISBN 978-0-7695-1822-0.
- ^ Bose, Prosenjit ; Maheshwari, Anil; Narasimhan, Giri; Smid, Michiel; Zeh, Norbert (2004), "Aproximación de caminos más cortos de cuellos de botella geométricos", Geometría Computacional. Teoría y aplicaciones , 29 (3): 233–249, doi : 10.1016 / j.comgeo.2004.04.003 , MR 2095376
- ^ Gethner, Ellen; Wagon, Stan ; Wick, Brian (1998), "Un paseo por los números primos de Gauss", American Mathematical Monthly , 105 (4): 327–337, doi : 10.2307 / 2589708 , JSTOR 2589708 , MR 1614871.