Problema de la amplitud

En este gráfico, el camino más ancho de Maldon a Feering tiene un ancho de banda de 29, y pasa a través de Clacton, Tiptree, Harwich, y Blaxill.

En algoritmos gráficos, el problema de la amplitud es el problema de encontrar un camino entre dos vértices designados en un gráfico ponderado, maximizando el peso del borde de menor peso en la ruta. El problema del camino más ancho también se conoce como el cuello de botella, el problema del camino más corto o más bien, el máximo problema de este camino es la capacidad. Es posible adaptar la mayoría de los algoritmos del camino más corto para calcular trayectorias muy amplias mediante la modificación de las mismas para utilizar la distancia del cuello de botella en lugar de la longitud de la trayectoria.[1]​ Sin embargo, en muchos casos incluso los algoritmos más rápidos son posibles.

Por ejemplo, en un gráfico que represente las conexiones entre los routers de la Internet, el peso de una arista representa el ancho de banda de una conexión entre dos routers, el problema del camino más ancho es el problema de encontrar una ruta de extremo a extremo entre dos nodos que tengan el máximo ancho de banda posible.[2]​ El peso más pequeño de la arista en este camino se conoce como la capacidad o ancho de banda de la ruta. Así como sus aplicaciones en el enrutamiento de red, el problema del camino más ancho es también un componente importante del método de 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]​ vía análisis metabólico[5]​ y cálculo de flujos máximos.[6]​

Un problema relacionado, es el problema del camino minimax, el cual supone por el camino que minimiza el peso máximo de cualquiera de sus aristas. Tiene aplicaciones que incluyen la planificación del transporte.[7]​ Cualquier algoritmo para el problema del camino más amplio puede ser transformado en un algoritmo para el problema del camino minimax, o viceversa, mediante la inversión del sentido de todas las comparaciones de peso realizadas por el algoritmo, o de manera equivalente mediante la sustitución de todo peso.

Gráficas indirectas

En una gráfica indirecta, un camino amplio se puede encontrar como el camino entre los dos vértices en el árbol con expansión máxima de la gráfica y un camino minimax se puede encontrar como el camino entre los dos vértices en el árbol con expansión mínima.[8]​[9]​[10]​

En cualquier gráfico, dirigido o no dirigido, hay un sencillo algoritmo para encontrar un camino más ancho una vez que el peso de su arista mínima sea conocido: sólo se tienen que borrar todas las aristas más pequeñas y eliminar cualquier camino entre las aristas restantes mediante la búsqueda en anchura o profundidad de la primera búsqueda. Sobre la base de esta prueba, también existe un algoritmo de tiempo lineal para encontrar un camino s-t más amplio en una gráfica no dirigida, que no utiliza el árbol de máxima expansión. La idea principal del algoritmo consiste en aplicar el algoritmo de ruta de investigación en tiempo lineal con el peso de la arista mediana en el gráfico y a continuación, eliminar todos las aristas más pequeñas o contraer todos las aristas de mayor tamaño en función si un camino no existe y recursarlo en el gráfico más pequeño que resulta.[9]​[11]​[12]​Fernandez, Garfinkel y Arbiol (1998) utilizan los caminos más cortos de cuello de botella no dirigidos con el fin de formar las fotografías aéreas compuestas que combinan varias imágenes de áreas de superposición. En el subproblema al que se aplica el problema del camino más ancho hay dos imágenes que ya se han transformado en un sistema de coordenadas común; la tarea restante es seleccionar una costura, una curva que pasa a través de la región de solapamiento y divide una de las dos imágenes de la otra. Los píxeles en un lado de la costura se pueden copiar de una de las imágenes, y los píxeles en el otro lado de la costura se copiarán desde la otra imagen. A diferencia de otros métodos, aquí se está fotografiando la composición promedio de los píxeles en ambas imágenes, lo que produce una imagen fotográfica válida de todas las partes de la región. Pesan las aristas de un gráfico de la red por un cálculo numérico nos aproxima a cómo visualmente aparece una costura a través de la misma arista y encontraría un camino más corto de cuello de botella para estos pesos. El uso de este camino como la costura, en lugar de un camino más corto y convencional, provoca que su sistema encuentre una costura que es difícil de discernir en todos sus puntos, en lugar de permitir un cambio de mayor visibilidad en una parte de la imagen o menor la visibilidad en otros lugares.[4]​

Si todos los pesos de las aristas de un gráfico no dirigido son positivos, entonces las distancias minimax entre pares de puntos (los pesos máximos de las aristas de caminos minimax) forman un ultramétrico; por el contrario cada espacio ultramétrico finito viene de distancias minimax de esta manera.[13]​ Una estructura de datos construida a partir del árbol de expansión mínimo permite que la distancia Minimax entre cualquier par de las vértices que se debe consultar,. sea mediante la consultas de ancestro común más bajo en un árbol cartesiano. La raíz del árbol cartesiano representa el mínimo peso que atraviesa la arista del árbol, y las sub-ramas de la raíz son árboles cartesianos de forma recursiva construidos a partir de los subárboles de expansión mínima formada por la eliminación de la arista más pesada. Las hojas del árbol cartesiano representan los vértices del gráfico de entrada, y la distancia entre dos vértices minimax es igual al peso del nodo del árbol cartesiano que a su vez es su ancestro común más bajo. Una vez que los bordes árbol de expansión mínimo se han ordenado, el árbol cartesiano se puede construir en el tiempo lineal.[14]​

Gráficas directas

En los gráficos dirigidos, la solución máxima de árbol de expansión no se puede utilizar. En lugar de ello, se conocen varios algoritmos diferentes; La elección de qué algoritmo para usar depende en si de un vértice de inicio o destino de una ruta que es fija, o si se usan rutas de acceso para muchos vértices de inicio los destinos deben encontrarse al mismo tiempo.

Para todo par

El problema del camino para todos los pares más anchos tiene aplicaciones en el método de Schulze que elige un ganador en las elecciones de múltiples vías en las que los electores ordenan a los candidatos en orden de preferencia. El método Schulze construye un gráfico dirigido completo en el que los vértices representan los candidatos y cada dos vértices están conectados por un borde. Cada borde es dirigido desde el ganador al perdedor de un combate por parejas entre los dos candidatos que se conecta, y se etiqueta con el margen de la victoria de ese concurso. A continuación, el método calcula trayectorias más amplias entre todos los pares de vértices, y el ganador es el candidato cuyo vértice tiene caminos más anchos a cada oponente que a la inversa. Los resultados de una elección que utilizan este método son consistentes con el método Condorcet . El candidato que gana todos los concursos por parejas gana automáticamente toda la elección - pero por lo general permite un ganador para ser seleccionados, incluso en situaciones en las que el método Concorcet falla. El método Schulze ha sido utilizado por varias organizaciones, entre ellas la Fundación Wikimedia.[15]​

Para calcular las anchuras de ruta más amplias para todos los pares de nodos de un grafo dirigido denso, tales como los que surgen en la aplicación de votación, el enfoque asintóticamente más rápido conocido toma tiempo O (n (3 + ω) / 2) donde ω es la exponente de la multiplicación de matrices rápido. El uso de los algoritmos más conocidos para la multiplicación de matrices, esta vez con destino se convierte en O (n2.688).[16]​ En cambio, la implementación de referencia para el método de Schulze utiliza una versión modificada del algoritmo más simple Floyd-Warshall, lo que lleva tiempo O (n3).[3]​ Para grafos dispersos, que puede ser más eficiente para aplicar repetidamente un algoritmo de ruta más amplia de una sola fuente.

Única fuente

Si los bordes están ordenados por sus pesos, a continuación, una versión modificada del algoritmo de Dijkstra puede calcular los cuellos de botella entre un vértice de inicio designado y cada otro vértice en el gráfico en tiempo lineal. La idea clave detrás del aumento de velocidad sobre una versión convencional del algoritmo de Dijkstra es que la secuencia de cuello de botella se distancia de 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 las aristas; Por lo tanto, la cola de prioridad del algoritmo de Dijkstra puede ser reemplazado por una matriz indexada por los números de 1 a m (el número de aristas en el gráfico), donde célula de agrupación i contiene los vértices cuya distancia cuello de botella es el peso del borde con la posición i en el orden de clasificación. Este método permite que el problema del camino más ancho a ser resuelto tan rápidamente como clasificación; por ejemplo, si los pesos de las aristas se representan como números enteros, entonces el tiempo de los límites para un número entero orden una lista de números enteros, m se aplicaría también a este problema.[12]​

Una sola fuente y destino único

Berman y Handler (1987) sugieren que los vehículos de servicio y vehículos de emergencia deben utilizar rutas minimax, al regresar de una visita de servicio a su base. En esta aplicación, el tiempo para volver es menos importante que el tiempo de respuesta si otra llamada de servicio se produce mientras el vehículo está en el proceso de retorno. Mediante el uso de un camino Minimax, donde el peso de una ventaja es el tiempo máximo de viaje desde un punto en el borde de la más lejana llamada de servicio posible, se puede planificar una ruta que minimice el retardo máximo posible entre la recepción de una llamada de servicio y la llegada de un vehículo para responder.[7]​Ullah, Lee y Hassoun (2009) utilizan caminos maxmin para modelar las cadenas de reacciones 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 los caminos más anchos surge en el algoritmo de Ford-Fulkerson para el problema de flujo máximo. Repetidamente aumentar un flujo a lo largo de una ruta de capacidad máxima en la red residual del flujo conduce a un pequeño salto, 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 en la mayoría de U. Sin embargo, este análisis no depende de encontrar un camino que tiene el máximo exacto de la capacidad; cualquier camino cuya capacidad está dentro de un factor constante de los máximos basta. La combinación de esta idea de aproximación con el método de aumento del camino más corto del algoritmo Edmonds-Karp conduce a un algoritmo de flujo máximo con el tiempo O (mn log T) que se ejecuta.[6]​

Es posible encontrar caminos de máxima capacidad y caminos minimax con una sola fuente y un solo destino muy eficiente, incluso en modelos de computación que sólo permiten comparaciones de los pesos de las aristas del grafo de entrada y no aritmética sobre ellos.[12]​[17]​ El algoritmo mantiene un conjunto S de aristas que se sabe que contienen el borde del cuello de botella de la ruta óptima; Inicialmente, S es el conjunto de todos los bordes m de la gráfica. En cada iteración del algoritmo, se divide S en una secuencia ordenada de subconjuntos S1, S2, ... 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 los subconjuntos se pueden encontrar por repetido mediana-hallazgo en tiempo O (m). El algoritmo luego reweights cada borde de la gráfica por el índice del subconjunto que contiene el borde, y utiliza el algoritmo de Dijkstra modificado en las gráficas reponderadas; sobre la base de los resultados de este cálculo, se puede determinar en tiempo lineal que de los subconjuntos contiene el peso borde cuello de botella. A continuación, sustituyendo S por el subconjunto del mismo que ha determinado para contener el peso cuello de botella y se inicia la siguiente iteración con este nuevo conjunto S. El número de subconjuntos en el que S se puede dividir aumenta exponencialmente con cada paso, por lo que el número de iteraciones es proporcional a la función de logaritmo iterado, O (Plantilla: Log-starn), y el tiempo total es O (m Plantilla: Log-starn).[17]​ En un modelo de cálculo, en el cada peso de borde es un número entero de la máquina, el uso de bisección repetido en este algoritmo puede ser sustituida por una técnica de división de lista de Han y Thorup (2002), permitiendo que S se divida en O (√m) conjuntos más pequeños de Si en un solo paso y que conducen a un tiempo global lineal unido.[18]​

Los conjuntos de puntos euclidianas

La banda azul oscuro separa los pares de números primos de Gauss cuya longitud de camino Minimax es 2 o más.

Una variante de problemas en el teorema del camino minimax también se han considerado, principalmente para conjuntos de puntos en el plano euclidiano. Al igual que en el problema grafo no dirigido, este problema del camino Minimax euclidiana se puede resolver de manera eficiente mediante la búsqueda de un árbol de expansión mínimo euclidiano: cada camino en el árbol es un camino Minimax. Sin embargo, el problema se vuelve más complicado cuando se desea un camino que no sólo reduce al mínimo la longitud de salto, sino también, entre las trayectorias con la misma longitud hop, minimiza o aproximadamente minimiza la longitud total de la ruta. La solución se puede aproximar utilizando llaves geométricas.[19]​

En teoría de números, el problema no resuelto de Gauss foso pregunta si la existencia de caminos minimax en los números primos de Gauss han delimitado la longitud Minimax sin límites. Es decir, ¿existe una constante B tal que, para cada par de puntos P y Q en el infinito conjunto de puntos euclidiana definida por los números primos de Gauss, el camino Minimax en el Gauss ceba entre P y Q tiene longitud de borde Minimax en la mayoría B?[20]​

Referencias

1. Pollack, Maurice (1960), «The maximum capacity through a network», Operations Research 8 (5): 733-736, JSTOR 167387, doi:10.1287/opre.8.5.733 .
2. Shacham, N. (1992), «Multicast routing of hierarchical data», IEEE International Conference on Communications (ICC '92) 3, pp. 1217-1221, doi:10.1109/ICC.1992.268047 .; Wang, Zheng; Crowcroft, J. (1995), «Bandwidth-delay based routing algorithms», IEEE Global Telecommunications Conference (GLOBECOM '95) 3, pp. 2129-2133, doi:10.1109/GLOCOM.1995.502780 .
3. Schulze, Markus (2011), «A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method», Social Choice and Welfare 36 (2): 267-303, doi:10.1007/s00355-010-0475-4 .
4. Fernandez, Elena; Garfinkel, Robert; Arbiol, Roman (1998), «Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths», Operations Research 46 (3): 293-304, JSTOR 222823, doi:10.1287/opre.46.3.293 .
5. Ullah, E.; Lee, Kyongbum; Hassoun, S. (2009), «An algorithm for identifying dominant-edge metabolic pathways», IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), pp. 144-150 .
6. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), «7.3 Capacity Scaling Algorithm», Network Flows: Theory, Algorithms and Applications, Prentice Hall, pp. 210-212, ISBN 0-13-617549-X .
7. 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 .
8. Hu, T. C. (1961), «The maximum capacity route problem», Operations Research 9 (6): 898-900, JSTOR 167055, doi:10.1287/opre.9.6.898 .
9. Punnen, Abraham P. (1991), «A linear time algorithm for the maximum capacity path problem», European Journal of Operational Research 53 (3): 402-404, doi:10.1016/0377-2217(91)90073-5 .
10. Malpani, Navneet; Chen, Jianer (2002), «A note on practical construction of maximum bandwidth paths», Information Processing Letters 83 (3): 175-180, MR 1904226, doi:10.1016/S0020-0190(01)00323-4 .
11. Camerini, P. M. (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 .
12. Kaibel, Volker; Peinhardt, Matthias A. F. (2006), On the bottleneck shortest path problem, ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin, archivado desde el original el 7 de agosto de 2011 .
13. Leclerc, Bruno (1981), «Description 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 623034 .
14. Demaine, Erik D.; Landau, Gad M.; Weimann, Oren (2009), «On Cartesian trees and range minimum queries», Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Lecture Notes in Computer Science 5555, pp. 341-353, doi:10.1007/978-3-642-02927-1_29 .
15. See Jesse Plamondon-Willard, Board election to use preference voting, May 2008; Mark Ryan, 2008 Wikimedia Board Election results, June 2008; 2008 Board Elections, June 2008; and 2009 Board Elections, August 2009.
16. Duan, Ran; Pettie, Seth (2009), «Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths», Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 384-391 .. For an earlier algorithm that also used fast matrix multiplication to speed up all pairs widest paths, see Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael (2007), «All-pairs bottleneck paths for general graphs in truly sub-cubic time», Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC '07), New York: ACM, pp. 585-589, MR 2402484, doi:10.1145/1250790.1250876 . and Chapter 5 of Vassilevska, Virginia (2008), Efficient Algorithms for Path Problems in Weighted Graphs, Ph.D. thesis, Report CMU-CS-08-147, Carnegie Mellon University School of Computer Science .
17. Gabow, Harold N.; Tarjan, Robert E. (1988), «Algorithms for two bottleneck optimization problems», Journal of Algorithms 9 (3): 411-417, MR 955149, doi:10.1016/0196-6774(88)90031-4 .
18. Han, Yijie; Thorup, M. (2002), «Integer sorting in O(n√log log n) expected time and linear space», Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), pp. 135-144, doi:10.1109/SFCS.2002.1181890 ..
19. Bose, Prosenjit; Maheshwari, Anil; Narasimhan, Giri; Smid, Michiel; Zeh, Norbert (2004), «Approximating geometric bottleneck shortest paths», Computational Geometry. Theory and Applications 29 (3): 233-249, MR 2095376, doi:10.1016/j.comgeo.2004.04.003 .
20. Gethner, Ellen; Wagon, Stan; Wick, Brian (1998), «A stroll through the Gaussian primes», American Mathematical Monthly 105 (4): 327-337, MR 1614871, doi:10.2307/2589708 ..

• Datos: Q7998708