El problema del camino más ancho

El problema del camino más ancho  es el problema de encontrar un camino entre dos vértices seleccionados en un gráfico ponderado que maximiza el peso del borde menos ponderado del gráfico (si consideramos el peso del borde como el ancho del camino, entonces el problema es elegir el camino más ancho que conecta dos vértices). El problema de la ruta más ancha también se conoce como el problema del cuello de botella o el problema de la capacidad máxima . Es posible adaptar los algoritmos de la ruta más corta para calcular el rendimiento mediante el uso de algún valor especial en lugar de la longitud de la ruta [1] . Sin embargo, en muchos casos son posibles algoritmos más rápidos.

Por ejemplo, en un gráfico que representa conexiones entre enrutadores en Internet , en el que el peso de un borde representa el ancho de banda de una conexión entre dos enrutadores, el problema de encontrar la ruta más ancha corresponde al problema de encontrar un extremo a extremo. ruta final entre dos nodos de Internet que tiene el mayor ancho de banda posible [2] [3 ] . El peso de borde más pequeño en este camino se conoce como la capacidad o el ancho del camino. Junto con las aplicaciones en el enrutamiento de redes, el problema de la ruta más amplia también es un componente importante del método de Schulze para determinar el ganador en elecciones multidireccionales [4] , se ha utilizado en alineación de imágenes digitales [5] , análisis de flujo metabólico [6] y para calcular caudales máximos [7] .

El problema de la ruta minimax, estrechamente relacionado, solicita una ruta que minimice el peso máximo de cualquiera de los bordes (se puede interpretar como encontrar la carretera más suave con ángulos mínimos de subida y bajada). Este problema encuentra aplicación en la planificación del tráfico [8] . Cualquier algoritmo para el problema de la ruta más ancha se puede convertir en un algoritmo de ruta minimax y viceversa invirtiendo el significado de todas las comparaciones de peso realizadas en el algoritmo, o de manera equivalente cambiando los pesos a valores negativos.

Grafos no dirigidos

En un gráfico no dirigido , la ruta más ancha se puede encontrar como una ruta entre dos vértices en el árbol de expansión máxima del gráfico , y la ruta minimax se puede encontrar como una ruta entre dos vértices en el árbol de expansión mínima [9] [10] [11 ] .

En cualquier gráfico, dirigido o no, existe un algoritmo simple para encontrar el camino más ancho si se conoce el peso del borde con el valor mínimo: simplemente elimine todos los bordes con un valor más pequeño y busque un camino entre los bordes restantes utilizando ancho -primera busqueda o profundidad -primera busqueda . Existe un algoritmo de tiempo lineal basado en esta prueba para encontrar la ruta s - t más ancha en un gráfico no dirigido que no utiliza un árbol de expansión máximo. La idea básica del algoritmo es aplicar un algoritmo de tiempo lineal para encontrar un camino hacia la mediana de los pesos de los bordes del gráfico y luego eliminar todos los bordes más pequeños o reducir todos los bordes más grandes según si el camino existe o no, y luego procesa recursivamente el gráfico más pequeño resultante [10] [12] [13] .

Fernández, Garfinkel y Arbiol [14] utilizaron el problema del cuello de botella en gráficos no dirigidos para obtener aliasing de imágenes aéreas digitales , que combina múltiples imágenes de áreas superpuestas. En el subproblema al que se aplica el problema de la ruta más ancha, las dos imágenes ya se han convertido al mismo sistema de coordenadas . Todo lo que queda es seleccionar una costura , una curva que pasa por la superposición y separa una imagen de otra. Los píxeles de un lado de la costura se copian de una imagen y los píxeles del otro lado de la costura se copian de otra imagen. A diferencia de otros métodos de alineación de imágenes, en los que se promedian los píxeles de ambas imágenes, este método toma una imagen fotográfica real de cada parte del área fotografiada. En el método, se asignan pesos a los bordes de la red con valores que estiman cuánto aparecerá visualmente la costura en el borde y encuentran el camino más ancho para estos pesos. El uso de esta ruta como una costura, en lugar de la ruta más corta más tradicional, da como resultado que su sistema encuentre una costura que es difícil de ver, en lugar de aumentar la calidad de una parte de la imagen a expensas de otra [5] .

Resolviendo el problema minimax entre dos esquinas de una celosía La celosía se puede utilizar para encontrar la distancia débil de Fréchet entre dos líneas quebradas . Aquí, cada vértice de la red representa un par de segmentos, uno de cada cadena, y el peso del borde representa la distancia de Fréchet necesaria para pasar de un par de segmentos a otro [15] .

Si todos los pesos de los bordes de un gráfico no dirigido son positivos , entonces las distancias minimax entre pares de puntos (pesos máximos de los bordes de las rutas minimax) forman un espacio ultramétrico . Por el contrario, cada espacio ultramétrico finito se forma a partir de distancias minimax de esta manera [16] . Una estructura de datos construida a partir de un árbol de mínima expansión permite consultar la distancia minimax entre cualquier par de vértices en tiempo constante utilizando consultas de antecesores mínimos comunes en un árbol cartesiano . La raíz de un árbol cartesiano representa la arista más pesada del árbol de menor expansión, y los hijos de la raíz son árboles cartesianos construidos recursivamente a partir de subárboles de los árboles de menor expansión formados al eliminar la arista más pesada. 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 ancestro menos común. Una vez ordenados los bordes del árbol de menor expansión, este árbol cartesiano se puede construir en tiempo lineal [17] .

Grafos dirigidos

En gráficos dirigidos , no se puede utilizar la solución de árbol de expansión máximo. En cambio, se conocen algunos algoritmos diferentes. La cuestión de qué algoritmo elegir depende de si los vértices inicial y final del camino son fijos, o si es necesario encontrar caminos desde varios vértices iniciales y finales al mismo tiempo.

Todas las parejas

El problema de la ruta más amplia para todos los pares tiene aplicaciones en el método de Schulze para determinar el ganador en elecciones de múltiples vías , en las que los votantes evalúan a los candidatos en un voto preferencial . El método de Schulze construye un gráfico dirigido completo , donde los vértices representan candidatos y dos vértices cualesquiera están conectados por una arista. Cada ventaja se dirige del ganador al perdedor en duelos entre dos candidatos y está marcada por la ventaja del ganador en la competencia. Luego, el método calcula el camino más ancho entre todos los pares de vértices y el ganador es el candidato que tiene los caminos más anchos con cada uno de los oponentes [4] . Los resultados de las elecciones que usan este método son consistentes con el método Condorcet  : el candidato que gana todas las peleas se convierte automáticamente en el ganador de la elección, pero el método le permite elegir al ganador cuando el método Condorcet no funciona [18] . El método Schulze ha sido utilizado por varias organizaciones, incluida la Fundación Wikimedia [19] .

Para calcular la ruta más amplia para todos los pares de nodos en gráficos dirigidos densos , como en aplicaciones de votación, el enfoque asintóticamente más rápido se ejecuta en el tiempo , donde es una métrica para algoritmos rápidos de multiplicación de matrices . Cuando se utilizan los algoritmos de multiplicación de matrices más conocidos, estos límites de tiempo se convierten en [20] . Para conocer los primeros algoritmos que también usaban la multiplicación rápida de matrices para acelerar la búsqueda de las rutas más amplias para todos los pares, consulte Wassilewska, Williams y Yuster [21] y el Capítulo 5 de Wassilewska [22] . La implementación de referencia del método Schulze utiliza una versión modificada del algoritmo Floyd-Warshall más simple que se ejecuta en el tiempo [4] . Para gráficos dispersos , la aplicación múltiple del algoritmo de búsqueda de ruta más amplia para una sola fuente se puede usar de manera más eficiente.

Una fuente

Si los bordes se ordenan por sus pesos, una versión modificada del algoritmo de Dijkstra puede calcular los cuellos de botella entre el vértice inicial asignado y todos los demás vértices del gráfico en tiempo lineal. La idea clave detrás de acelerar con la versión habitual del algoritmo de Dijkstra es que la secuencia de cuellos de botella hasta cada vértice en el orden en que aparecen esos vértices en el algoritmo es una subsecuencia monótona ordenada por pesos de la secuencia de borde. Por lo tanto, la cola de prioridad del algoritmo de Dijkstra se puede implementar como una cola contenedora , un arreglo numerado del 1 al m (número de aristas en el gráfico), donde la celda del arreglo i contiene vértices cuyos "cuellos de botella" son iguales al peso del borde con la posición i en orden ordenado. Este método resuelve el problema de la ruta más ancha a la misma velocidad que la clasificación . Por ejemplo, si los pesos de los bordes son enteros, entonces el límite de tiempo para la ordenación de enteros de una lista de m enteros también será una estimación para este problema [13] .

Fuente única y destino único

Berman y Handler [23] sugirieron que los vehículos de emergencia y las ambulancias deberían usar la ruta minimax al regresar del punto de llamada a la base. En estos casos, el tiempo de retorno es menos importante que el tiempo de respuesta si se produce otra llamada mientras la máquina está en proceso de retorno. Cuando se utiliza una ruta minimax, en la que el peso es el tiempo máximo de viaje desde el borde hasta el punto más alejado de una posible llamada, es posible planificar la ruta de modo que se produzca el máximo retraso posible entre la recepción de una llamada y la llegada del automóvil. es mínimo [8] . Ulla, Lee y Hassoon [24] utilizaron rutas máximas para modelar la cadena 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 [6] .

Otra aplicación de los caminos más anchos surge en el algoritmo de Ford-Fulkerson para el problema de flujo máximo . El aumento gradual del flujo a lo largo de una ruta con capacidad máxima en la red de flujo residual da como resultado un pequeño límite en el número de incrementos necesarios para encontrar el flujo máximo. Aquí se supone que las capacidades de borde son números enteros que no exceden U . Sin embargo, este análisis no depende de encontrar la capacitancia máxima exacta. Cualquier camino con una capacidad que difiera del máximo por un factor constante es adecuado. La combinación de estas ideas de aproximación con el método de incremento de ruta más corta del algoritmo de Edmonds-Karp da como resultado un algoritmo de flujo máximo con tiempo de ejecución [7] .

Es posible encontrar caminos de máxima capacidad y caminos minimax con una sola fuente y un solo destino de manera muy eficiente incluso en modelos computacionales que solo permiten comparar los pesos de los bordes del gráfico de entrada, y no aritmética con ellos [13] [25] . El algoritmo opera en un conjunto S de aristas que se sabe que contienen la arista de cuello de botella de la ruta óptima. Inicialmente , S consta de todas las m aristas del gráfico. En cada iteración del algoritmo, S se divide en una secuencia ordenada de subconjuntos de aproximadamente el mismo tamaño. El número de subconjuntos en esta partición se elige de modo que todos los puntos de partición entre subconjuntos se puedan encontrar al encontrar medianas varias veces en tiempo O ( m ) . Luego, el algoritmo vuelve a calcular los pesos de todos los bordes del gráfico por el índice del subconjunto que contiene el borde y utiliza el algoritmo de Dijkstra modificado en el gráfico con los pesos actualizados. Con base en los resultados de estos cálculos, es posible calcular en tiempo lineal cuál de los subconjuntos contiene el peso del borde del cuello de botella. Luego, el algoritmo reemplaza S con un subconjunto Si que contiene el peso del cuello de botella y comienza una nueva iteración con este conjunto S. El número de subconjuntos en los que se puede dividir S puede aumentar exponencialmente con cada paso, de modo que el número de iteraciones sea proporcional al logaritmo iterado de , y el tiempo total de ejecución será [25] . En un modelo de cálculo en el que el peso de cada arista es un número entero de máquina, el uso de logaritmos iterativos en este algoritmo puede sustituirse por la técnica de partición de listas de Hahn y Thorup [26] , que permite dividir S en partes más pequeñas s Si en un solo paso, lo que da como resultado un límite común lineal en el tiempo [27] .

Conjuntos de puntos euclidianos

Se consideró una variante del problema del camino minimax para un conjunto de puntos en el plano euclidiano . Al igual que en el problema del gráfico no dirigido, este problema de la ruta euclidiana minimax se puede resolver de manera eficiente al encontrar un árbol de expansión mínimo euclidiano  : cualquier ruta en el árbol es una ruta minimax. Sin embargo, el problema se vuelve más complicado si uno quiere que la ruta no solo minimice la longitud superior, sino también, entre rutas con la misma longitud superior, para minimizar o minimizar aproximadamente la longitud total de la ruta. La solución se puede aproximar utilizando el árbol de expansión geométrico [28] .

En teoría de números, el problema del foso gaussiano no resuelto pregunta si la longitud minimax de las rutas minimax en números primos gaussianos está acotada . Es decir, ¿existe una constante B tal que para cualquier par p y q en un conjunto infinito de puntos euclidianos definidos por números primos gaussianos, la ruta minimax en números primos gaussianos entre p y q tenga una longitud de arista como máximo B ? [29] .

Notas

  1. ↑ Pollack, 1960 , pág. 733–736.
  2. ↑ Shacham, 1992 , pág. 1217-1221.
  3. ↑ Wang, Crowcroft, 1995 , pág. 2129–2133.
  4. ↑ 1 2 3 Schulze, 2011 , pág. 267–303.
  5. ↑ 1 2 Fernández, Garfinkel, Arbiol, 1998 , p. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , pág. 144–150.
  7. ↑ 1 2 Ahuja, Magnanti y Orlin, 1993 , p. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987 , pág. 115–122.
  9. ↑ Hu, 1961 , pág. 898–900.
  10. ↑ 12 Punnen , 1991 , pág. 402–404.
  11. ↑ Malpani, Chen, 2002 , pág. 175–180.
  12. ↑ Camerini, 1978 , pág. 10–14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernández, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , pág. 75–91.
  16. ↑ Leclerc, 1981 , pág. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , pág. 341–353.
  18. ↑ Más precisamente, la única posibilidad en la que falla el método de Schulze es cuando dos candidatos tienen caminos de igual ancho entre sí.
  19. ↑ Véase Jesse Plamondon-Willard, Elección de la Junta para utilizar la votación preferencial , mayo de 2008; Mark Ryan, resultados de las elecciones de la Junta de Wikimedia de 2008 , junio de 2008; Elecciones de la Junta de 2008 , junio de 2008; y Elecciones de la Junta de 2009 , agosto de 2009.
  20. ↑ Duan, Pettie, 2009 , pág. 384–391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , p. 585–589.
  22. ↑ Vassilevska, 2008 .
  23. ↑ Berman, Manejador, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , p. 411–417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , pág. 135–144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , pág. 233–249.
  29. ↑ Gethner, Vagón, Wick, 1998 , pág. 327–337.

Literatura