LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

En teoría de gráficos , el problema de la ruta más corta es el problema de encontrar una ruta entre dos vértices (o nodos) en un gráfico de tal manera que se minimice la suma de los pesos de sus bordes constituyentes.

El problema de encontrar la ruta más corta entre dos intersecciones en un mapa de ruta se puede modelar como un caso especial del problema de la ruta más corta en gráficos, donde los vértices corresponden a las intersecciones y los bordes corresponden a segmentos de carretera, cada uno ponderado por la longitud del segmento.

La ruta más corta (A, C, E, D, F) entre los vértices A y F en el gráfico dirigido ponderado

Definición [ editar ]

El problema del camino más corto se puede definir para gráficos si no dirigida , dirigida , o mezclado . Se define aquí para gráficos no dirigidos; para los gráficos dirigidos, la definición de ruta requiere que los vértices consecutivos estén conectados por un borde dirigido apropiado.

Dos vértices son adyacentes cuando ambos inciden en un borde común. Una ruta en un gráfico no dirigido es una secuencia de vértices$${\ displaystyle P = (v_ {1}, v_ {2}, \ ldots, v_ {n}) \ en V \ times V \ times \ cdots \ times V} tal que $${\ displaystyle v_ {i}} es adyacente a $${\ displaystyle v_ {i + 1}} para {\ displaystyle 1 \ leq i . Tal camino$${\ displaystyle P} Se llama camino de longitud. $${\ displaystyle n-1} desde $${\ displaystyle v_ {1}} a $${\ displaystyle v_ {n}}. (Los$${\ displaystyle v_ {i}}son variables; su numeración aquí se relaciona con su posición en la secuencia y no necesita relacionarse con ningún etiquetado canónico de los vértices.)

Dejar $${\ displaystyle e_ {i, j}} ser el incidente de borde a ambos $${\ displaystyle v_ {i}} y $${\ displaystyle v_ {j}}. Dada una función de peso de valor real.$${\ displaystyle f: E \ rightarrow \ mathbb {R}}, y un grafo no dirigido (simple) $${\ displaystyle G}, el camino más corto desde $${\ displaystyle v} a $${\ displaystyle v '} es el camino $${\ displaystyle P = (v_ {1}, v_ {2}, \ ldots, v_ {n})} (dónde $${\ displaystyle v_ {1} = v} y $${\ displaystyle v_ {n} = v '}) que sobre todo posible $${\ displaystyle n} minimiza la suma $${\ displaystyle \ sum _ {i = 1} ^ {n-1} f (e_ {i, i + 1}).} Cuando cada borde en el gráfico tiene un peso unitario o $${\ displaystyle f: E \ rightarrow \ {1 \}}, esto es equivalente a encontrar el camino con menos bordes.

El problema también se denomina a veces el problema de la ruta más corta de un solo par , para distinguirlo de las siguientes variaciones:

• El problema de la ruta más corta de una sola fuente , en el que tenemos que encontrar las rutas más cortas desde un vértice fuente v a todos los otros vértices en el gráfico.
• El problema de la ruta más corta de un solo destino , en el que tenemos que encontrar las rutas más cortas de todos los vértices en el gráfico dirigido a un solo vértice de destino v . Esto se puede reducir al problema de la ruta más corta de una sola fuente invirtiendo los arcos en el gráfico dirigido.
• El problema de la ruta más corta de todos los pares , en el que tenemos que encontrar las rutas más cortas entre cada par de vértices v , v ' en la gráfica.

Estas generalizaciones tienen algoritmos significativamente más eficientes que el enfoque simplista de ejecutar un algoritmo de ruta más corta de un solo par en todos los pares de vértices relevantes.

Algoritmos [ editar ]

Los algoritmos más importantes para resolver este problema son:

• El algoritmo de Dijkstra resuelve el problema de la ruta más corta de una sola fuente con un peso de borde no negativo.
• El algoritmo de Bellman-Ford resuelve el problema de una sola fuente si los pesos de los bordes pueden ser negativos.
• Un algoritmo de búsqueda * resuelve la ruta más corta de un solo par utilizando heurísticas para tratar de acelerar la búsqueda.
• El algoritmo Floyd – Warshall resuelve todos los pares de rutas más cortas.
• El algoritmo de Johnson resuelve todos los pares de rutas más cortas, y puede ser más rápido que Floyd-Warshall en gráficos dispersos .
• El algoritmo de Viterbi resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada nodo.

Se pueden encontrar algoritmos adicionales y evaluaciones asociadas en Cherkassky, Goldberg & Radzik (1996).

Las rutas más cortas de una sola fuente [ editar ]

Gráficos no dirigidos [ editar ]

Pesas	Complejidad del tiempo	Autor
ℝ +	O ( V 2 )	Dijkstra 1959
ℝ +	O (( E  +  V ) log  V )	Johnson 1977 ( montón binario )
ℝ +	O ( E  +  V  log  V )	Fredman y Tarjan 1984 ( montón de Fibonacci )
ℕ	O ( E )	Thorup 1999 (requiere la multiplicación de tiempo constante).

Gráficos no ponderados [ editar ]

Algoritmo	Complejidad del tiempo	Autor
Búsqueda en amplitud	O ( E  +  V )

Gráficos acíclicos dirigidos (DAGs) [ editar ]

Un algoritmo que utiliza ordenamiento topológico puede resolver el problema de la ruta más corta de una sola fuente en tiempo lineal, Θ ( E + V ) , en DAG ponderados.

Gráficos dirigidos con pesos no negativos [ editar ]

La siguiente tabla está tomada de Schrijver (2004) , con algunas correcciones y adiciones. Un fondo verde indica un límite mejor asintóticamente en la tabla; L es la longitud (o peso) máxima entre todos los bordes, asumiendo pesos de bordes enteros.

Algoritmo	Complejidad del tiempo	Autor
	O ( V 2 EL )	Ford 1956
Algoritmo de Bellman-Ford	O ( VE )	Shimbel 1955 , Bellman 1958 , Moore 1959
	O ( V 2  log  V)	Dantzig 1960
Algoritmo de Dijkstra con lista	O ( V 2 )	Leyzorek et al. 1957 , Dijkstra 1959 , Minty (ver Pollack y Wiebenson 1960 ), Whiting y Hillier 1960
Algoritmo de Dijkstra conmontón binario	O (( E  +  V ) log  V )	Johnson 1977
. . .	. . .	. . .
El algoritmo de Dijkstra con elmontón de Fibonacci	O ( E  +  V log  V )	Fredman y Tarjan 1984 , Fredman y Tarjan 1987
	O ( E  log log L )	Johnson 1981 , Karlsson & Poblete 1983
Algoritmo de Gabow	O ( E  log E / V L )	Gabow 1983 , Gabow 1985
	O ( E  +  V √ log L )	Ahuja et al. 1990
Thorup	O ( E  +  V  log log  V )	Thorup 2004

Esta lista está incompleta ; Puedes ayudar expandiéndolo .

Gráficos dirigidos con pesos arbitrarios sin ciclos negativos [ editar ]

Algoritmo	Complejidad del tiempo	Autor
	O ( V 2 EL )	Ford 1956
Algoritmo de Bellman-Ford	O ( VE )	Shimbel 1955 , Bellman 1958 , Moore 1959

Esta lista está incompleta ; Puedes ayudar expandiéndolo .

Gráficos planar dirigidos con pesos arbitrarios [ editar ]

Rutas más cortas de todos los pares [ editar ]

El problema de la ruta más corta de todos los pares encuentra las rutas más cortas entre cada par de vértices v , v ' en la gráfica. Shimbel (1953) introdujo el problema de las rutas más cortas de todos los pares para los gráficos dirigidos no ponderados , quien observó que podría resolverse mediante un número lineal de multiplicaciones de matrices que lleva un tiempo total de O ( V ⁴ ) .

Gráfico no dirigido [ editar ]

Pesas	Complejidad del tiempo	Algoritmo
ℝ +	O ( V 3 )	Algoritmo Floyd – Warshall
$${\ displaystyle \ {+ 1, + \ infty \}}	$${\ displaystyle O (V ^ {\ omega} \ log V)}	Algoritmo de Seidel (tiempo de ejecución previsto).
ℕ	$${\ displaystyle O (V ^ {3} / 2 ^ {\ Omega (\ log n) ^ {1/2}})}	Williams 2014
ℝ +	O (  registro de EV α ( E , V ))	Pettie y Ramachandran 2002
ℕ	O ( EV )	Thorup 1999 (requiere la multiplicación de tiempo constante).

Grafica dirigida [ editar ]

Pesas	Complejidad del tiempo	Algoritmo
ℝ (sin ciclos negativos)	O ( V 3 )	Algoritmo Floyd – Warshall
ℕ	$${\ displaystyle O (V ^ {3} / 2 ^ {\ Omega (\ log n) ^ {1/2}})}	Williams 2014
ℝ (sin ciclos negativos)	O ( EV  +  V 2  log  V )	Johnson – Dijkstra
ℝ (sin ciclos negativos)	O ( EV  +  V 2  log log  V )	Pettie 2004
ℕ	O ( EV  +  V 2  log log  V )	Hagerup 2000

Aplicaciones [ editar ]

Los algoritmos de ruta más corta se aplican para buscar automáticamente direcciones entre ubicaciones físicas, como las direcciones de conducción en sitios web de mapas web como MapQuest o Google Maps . Para esta aplicación están disponibles rápidos algoritmos especializados. ^[1]

Si uno representa una máquina abstracta no determinista como un gráfico en el que los vértices describen los estados y los bordes describen las posibles transiciones, los algoritmos de ruta más corta se pueden usar para encontrar una secuencia óptima de opciones para alcanzar un determinado estado objetivo, o para establecer límites más bajos en el tiempo necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un rompecabezas como el Cubo de Rubik y cada borde dirigido corresponde a un solo movimiento o giro, los algoritmos de ruta más corta se pueden usar para encontrar una solución que use el número mínimo posible de movimientos.

En una mentalidad de redes o telecomunicaciones , este problema de ruta más corta a veces se denomina problema de ruta de retardo mínimo y generalmente está relacionado con un problema de ruta más amplia . Por ejemplo, el algoritmo puede buscar la ruta más corta (demora mínima) o la ruta más corta (demora mínima).

Una aplicación más alegre son los juegos de " seis grados de separación " que intentan encontrar el camino más corto en gráficos como estrellas de cine que aparecen en la misma película.

Otras aplicaciones, a menudo estudiadas en la investigación de operaciones , incluyen el diseño de plantas e instalaciones, robótica , transporte y diseño VLSI . ^[2]

Las redes de carreteras [ editar ]

Una red de carreteras puede considerarse como un gráfico con pesos positivos. Los nodos representan uniones de carreteras y cada borde del gráfico está asociado con un segmento de carretera entre dos uniones. El peso de un borde puede corresponder a la longitud del segmento de carretera asociado, el tiempo necesario para atravesar el segmento o el costo de atravesar el segmento. Usando bordes dirigidos también es posible modelar calles de un solo sentido. Tales gráficos son especiales en el sentido de que algunos bordes son más importantes que otros para viajes de larga distancia (por ejemplo, carreteras). Esta propiedad ha sido formalizada utilizando la noción de dimensión de autopista. ^[3] Hay una gran cantidad de algoritmos que explotan esta propiedad y, por lo tanto, pueden calcular la ruta más corta mucho más rápido de lo que sería posible en los gráficos generales.

Todos estos algoritmos funcionan en dos fases. En la primera fase, el gráfico está preprocesado sin conocer el nodo de origen o destino. La segunda fase es la fase de consulta. En esta fase, se conocen la fuente y el nodo de destino. La idea es que la red de carreteras sea estática, por lo que la fase de preprocesamiento se puede realizar una vez y se puede usar para una gran cantidad de consultas en la misma red de carreteras.

El algoritmo con el tiempo de consulta más rápido conocido se llama etiquetado de concentrador y es capaz de calcular la ruta más corta en las redes de carreteras de Europa o los EE. UU. En una fracción de microsegundo. ^[4] Otras técnicas que se han utilizado son:

• ALT (búsqueda A *, puntos de referencia y desigualdad de triángulos )
• Banderas de arco
• Jerarquías de contracción
• Enrutamiento de nodo de tránsito
• Poda basada en el alcance
• Etiquetado
• Etiquetas de hub

Problemas relacionados [ editar ]

Para los problemas de la ruta más corta en la geometría computacional , consulte la ruta más corta euclidiana .

El problema de los vendedores ambulantes es el problema de encontrar la ruta más corta que recorre cada vértice exactamente una vez y vuelve al principio. A diferencia del problema de la ruta más corta, que se puede resolver en tiempo polinomial en gráficos sin ciclos negativos, el problema del vendedor ambulante es NP-completo y, como tal, se cree que no se puede resolver de manera eficiente para grandes conjuntos de datos (ver P = problema NP) ). El problema de encontrar la ruta más larga en un gráfico también es NP-completo.

El problema del viajero canadiense y el problema del camino más corto estocástico son generalizaciones en las que el motor no conoce completamente la gráfica, los cambios en el tiempo o donde las acciones (travesías) son probabilísticas.

La ruta de desconexión múltiple más corta ^[5] es una representación de la red de ruta primitiva dentro del marco de la teoría de la Reptación .

El problema de la ruta más amplia busca una ruta para que la etiqueta mínima de cualquier borde sea lo más grande posible.

Caminos más cortos estratégicos [ editar ]

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material sin fuente puede ser cuestionado y eliminado . ( Diciembre de 2015 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

A veces, los bordes de una gráfica tienen personalidades: cada borde tiene su propio interés egoísta. Un ejemplo es una red de comunicación, en la que cada borde es una computadora que posiblemente pertenece a una persona diferente. Las diferentes computadoras tienen diferentes velocidades de transmisión, por lo que cada borde de la red tiene un peso numérico igual al número de milisegundos que se tarda en transmitir un mensaje. Nuestro objetivo es enviar un mensaje entre dos puntos de la red en el menor tiempo posible. Si conocemos el tiempo de transmisión de cada computadora (el peso de cada borde), entonces podemos usar un algoritmo estándar de las rutas más cortas. Si no conocemos los tiempos de transmisión, tenemos que pedir a cada computadora que nos indique su tiempo de transmisión. Pero, las computadoras pueden ser egoístas: una computadora podría decirnos que su tiempo de transmisión es muy largo, Para que no lo molestemos con nuestros mensajes. Una posible solución a este problema es utilizaruna variante del mecanismo VCG , que da a las computadoras un incentivo para revelar sus verdaderos pesos.

Formulación de programación lineal [ editar ]

Existe una formulación de programación lineal natural para el problema del camino más corto, que se presenta a continuación. Es muy simple en comparación con la mayoría de los otros usos de los programas lineales en la optimización discreta , sin embargo, ilustra las conexiones a otros conceptos.

Dado un grafo dirigido ( V , A ) con el nodo fuente s , objetivo nodo t , y el costo w _ij para cada borde ( i , j ) en A , considerar el programa con variables x _ij

minimizar $${\ displaystyle \ sum _ {ij \ en A} w_ {ij} x_ {ij}} sujeto a $${\ displaystyle x \ geq 0}y para todos yo ,{\ displaystyle \ sum _ {j} x_ {ij} - \ sum _ {j} x_ {ji} = {\ begin {cases} 1, & {\ text {if}} i = s; \\ - 1, & {\ text {if}} i = t; \\ 0, & {\ text {de lo contrario.}} \ end {cases}}}

La intuición detrás de esto es que $${\ displaystyle x_ {ij}}es una variable indicadora de si el borde ( i , j ) es parte de la ruta más corta: 1 cuando lo es, y 0 si no lo es. Deseamos seleccionar el conjunto de bordes con un peso mínimo, sujeto a la restricción de que este conjunto forma un camino de s a t (representado por la restricción de igualdad: para todos los vértices excepto s y t el número de bordes entrantes y salientes que forman parte La ruta debe ser la misma (es decir, debe ser una ruta desde s hasta t).

Este LP tiene la propiedad especial de que es integral; más específicamente, cada solución óptima básica(cuando existe una) tiene todas las variables iguales a 0 o 1, y el conjunto de bordes cuyas variables son iguales a 1 forman un dipath s - t . Ver Ahuja et al. ^[6] por una prueba, aunque el origen de este enfoque se remonta a mediados del siglo XX.

El dual para este programa lineal es

maximizar y _t - y _s sujeto a todos ij , y _j - y _i ≤ w _ij

y los duales factibles corresponden al concepto de una heurística consistente para el algoritmo A * para las rutas más cortas. Por cualquier doble factible y los costes reducidos. $${\ displaystyle w '_ {ij} = w_ {ij} -y_ {j} + y_ {i}}son no negativos y A *esencialmente ejecuta el algoritmo de Dijkstra en estos costos reducidos.

Marco algebraico general sobre semirings: el problema de la ruta algebraica [ editar ]

Esta sección necesita expansión. Puedes ayudar añadiéndolo . ( Agosto 2014 )

Muchos problemas se pueden encuadrar como una forma del camino más corto para algunas nociones de adición adecuadamente sustituidas a lo largo de un camino y tomando el mínimo. El enfoque general de estos es considerar que las dos operaciones son las de un semiringuito . La multiplicación semiringuosa se realiza a lo largo del camino, y la suma es entre los caminos. Este marco general se conoce como el problema de la ruta algebraica . ^{[7] [8] [9]}

La mayoría de los algoritmos clásicos de ruta más corta (y los nuevos) se pueden formular para resolver sistemas lineales sobre tales estructuras algebraicas. ^[10]

Más recientemente, se ha desarrollado un marco aún más general para resolver estos (y problemas mucho menos obviamente relacionados) bajo la bandera de álgebras de valoración . ^[11]

Ruta más corta en redes estocásticas dependientes del tiempo [ editar ]

En situaciones de la vida real, la red de transporte suele ser estocástica y depende del tiempo. De hecho, un viajero que atraviesa un enlace diariamente puede experimentar diferentes tiempos de viaje en ese enlace debido no solo a las fluctuaciones en la demanda de viajes (matriz de origen-destino) sino también a incidentes tales como zonas de trabajo, condiciones climáticas adversas, accidentes y averías de vehículos. . Como resultado, una red estocástica dependiente del tiempo (STD) es una representación más realista de una red de carreteras real en comparación con la determinista. ^[12] [13]

A pesar de un progreso considerable durante el transcurso de la última década, sigue siendo una cuestión controvertida cómo se debe definir e identificar un camino óptimo en las redes de carreteras estocásticas. En otras palabras, no hay una definición única de una ruta óptima bajo incertidumbre. Una respuesta posible y común a esta pregunta es encontrar un camino con el tiempo de viaje mínimo esperado. La principal ventaja de usar este enfoque es que los algoritmos de ruta más cortos y eficientes introducidos para las redes deterministas se pueden emplear fácilmente para identificar la ruta con el tiempo de viaje mínimo esperado en una red estocástica. Sin embargo, la ruta óptima resultante identificada por este enfoque puede no ser confiable, ya que este enfoque no aborda la variabilidad del tiempo de viaje.Programación dinámica y algoritmo de Dijkstra . ^[14]Estos métodos utilizan la optimización estocástica , específicamente la programación dinámica estocástica para encontrar el camino más corto en redes con longitud de arco probabilística. ^[15] El concepto de confiabilidad del tiempo de viaje se usa de manera intercambiable con la variabilidad del tiempo de viaje en la literatura de investigación de transporte, de modo que, en general, se puede decir que cuanto mayor sea la variabilidad en el tiempo de viaje, menor será la confiabilidad y viceversa .

Para tener en cuenta la confiabilidad del tiempo de viaje de manera más precisa, se han sugerido dos definiciones alternativas comunes para una ruta óptima en condiciones de incertidumbre. Algunos han introducido el concepto de la ruta más confiable, con el objetivo de maximizar la probabilidad de llegar a tiempo o antes de un presupuesto de tiempo de viaje determinado. Otros, alternativamente, han presentado el concepto de una ruta α-confiable basada en la cual intentaron minimizar el presupuesto de tiempo de viaje requerido para garantizar una probabilidad de llegada a tiempo preespecificada.