El algoritmo de Johnson es una manera de encontrar las rutas más cortas entre todos los pares de vértices en un borde ponderados , grafo dirigido . Permite que algunos de los pesos de borde sean números negativos , pero no pueden existir ciclos depeso negativo . Funciona utilizando el algoritmo de Bellman-Fordpara calcular una transformación del gráfico de entrada que elimina todos los pesos negativos, permitiendo que el algoritmo de Dijkstra se utilice en el gráfico transformado. [1] [2] Lleva el nombre de Donald B. Johnson , quien publicó la técnica por primera vez en 1977. [3]
Una técnica de reponderación similar también se usa en el algoritmo de Suurballe para encontrar dos caminos separados de la longitud total mínima entre los mismos dos vértices en un gráfico con pesos de bordes no negativos.
Descripción del algoritmo [ editar ]
- Primero, se agrega un nuevo nodo q al gráfico, conectado por bordes de peso cero a cada uno de los otros nodos.
- En segundo lugar, se utiliza el algoritmo de Bellman-Ford , a partir del nuevo vértice q , para encontrar para cada vértice v el peso mínimo h ( v ) de una ruta de q a v . Si este paso detecta un ciclo negativo, el algoritmo se termina.
- A continuación, los bordes del gráfico original se vuelven a ponderar utilizando los valores calculados por el algoritmo de Bellman-Ford: un borde de u a v , que tiene una longitud, se le da la nueva longitud w ( u , v ) + h ( u ) - h ( v ) .
- Finalmente, q se elimina, y el algoritmo de Dijkstra se utiliza para encontrar las rutas más cortas desde cada nodo s a cada otro vértice en el gráfico reponderadas.
Ejemplo [ editar ]
Las primeras tres etapas del algoritmo de Johnson se muestran en la siguiente ilustración.
El gráfico a la izquierda de la ilustración tiene dos bordes negativos, pero no tiene ciclos negativos. En el centro se muestra el nuevo vértice q , el árbol de ruta más corto calculado por el algoritmo de Bellman-Ford con q como vértice inicial, y los valores h ( v ) calculados en cada otro nodo como la longitud de la ruta más corta de q a ese nodo Tenga en cuenta que todos estos valores no son positivos, porque q tiene un borde de longitud cero en cada vértice y la ruta más corta no puede ser más larga que ese borde. A la derecha se muestra el gráfico ponderado, formado por el reemplazo de cada borde de pesopor w ( u , v ) + h ( u ) - h ( v ) . En este gráfico ponderado, todos los pesos de los bordes no son negativos, pero la ruta más corta entre dos nodos cualquiera utiliza la misma secuencia de bordes que la ruta más corta entre los mismos dos nodos en la gráfica original. El algoritmo concluye aplicando el algoritmo de Dijkstra a cada uno de los cuatro nodos iniciales en el gráfico ponderado.
Corrección [ editar ]
En el gráfico reponderadas, todas las rutas entre un par s y t de nodos tienen la misma cantidad h ( s ) - h ( t )añadido a ellos. La declaración anterior se puede demostrar de la siguiente manera: Let p sea unacamino. Su peso W en el gráfico ponderado viene dado por la siguiente expresión:
Cada es cancelado por en la anterior expresión entre corchetes; por lo tanto, nos queda la siguiente expresión para W :
La expresión entre corchetes es el peso de p en la ponderación original.
Dado que la reponderación agrega la misma cantidad al peso de cada ruta, una ruta es la ruta más corta en la ponderación original si y solo si es la ruta más corta después de volver a ponderar. El peso de los bordes que pertenecen a una ruta más corta de q a cualquier nodo es cero, y por lo tanto, las longitudes de las rutas más cortas de q a cada nodo se vuelven cero en el gráfico ponderado; Sin embargo, siguen siendo caminos más cortos. Por lo tanto, no puede haber bordes negativos: si borde uv tenía un peso negativo después de la ponderación, la ruta de longitud cero de q a u junto con este borde formaría un camino de longitud negativa de qpara v , contradiciendo el hecho de que todos los vértices tienen cero distancia de q. La no existencia de bordes negativos garantiza la optimalidad de las rutas encontradas por el algoritmo de Dijkstra. Las distancias en el gráfico original pueden calcularse a partir de las distancias calculadas por el algoritmo de Dijkstra en el gráfico ponderado invirtiendo la transformación de ponderación. [1]
Análisis [ editar ]
La complejidad del tiempo de este algoritmo, utilizando los montones de Fibonacci en la implementación del algoritmo de Dijkstra, es: utiliza el algoritmo tiempo para la etapa de Bellman-Ford del algoritmo, y para cada uno de los Las instancias del algoritmo de Dijkstra. Por lo tanto, cuando el gráfico es escaso , el tiempo total puede ser más rápido que el algoritmo Floyd-Warshall , que resuelve el mismo problema en el tiempo.
(Redirigido desde el problema del vendedor viajero )
El problema del vendedor ambulante ( TSP ) hace la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad y regresa a la ciudad de origen?" Es un problema de NP-difícil en la optimización combinatoria , importante en la investigación de operaciones y en la informática teórica .
El problema del comprador que viaja y el problema de enrutamiento del vehículo son generalizaciones de TSP.
En la teoría de la complejidad computacional , la versión de decisión del TSP (donde, dada una longitud L , la tarea es decidir si la gráfica tiene un recorrido más corto que L ) pertenece a la clase de problemas de NP-completa . Por lo tanto, es posible que el tiempo de ejecución en el peor de los casos para cualquier algoritmo para el TSP aumente superpolinomialmente (pero no más que exponencialmente ) con el número de ciudades.
El problema se formuló por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Se utiliza como punto de referencia para muchos métodos de optimización. A pesar de que el problema es computacionalmente difícil, se conoce una gran cantidad de heurísticas y algoritmos exactos , de modo que algunos casos con decenas de miles de ciudades pueden resolverse por completo e incluso los problemas con millones de ciudades pueden aproximarse en una pequeña fracción del 1%. . [1]
El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación , la logística y la fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN . En estas aplicaciones, la ciudad de concepto representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y la distancia de concepto representa tiempos o costos de viaje, o una medida de similitudentre los fragmentos de ADN. El TSP también aparece en astronomía, ya que los astrónomos que observan muchas fuentes querrán minimizar el tiempo dedicado a mover el telescopio entre las fuentes. En muchas aplicaciones, se pueden imponer restricciones adicionales, como recursos limitados o ventanas de tiempo.
Historia [ editar ]
Los orígenes del problema del vendedor ambulante no están claros. Un manual para vendedores ambulantes de 1832 menciona el problema e incluye recorridos de ejemplo a través de Alemania y Suiza , pero no contiene tratamiento matemático. [2]
El problema del vendedor ambulante fue formulado matemáticamente en la década de 1800 por el matemático irlandés WR Hamilton y por el matemático británico Thomas Kirkman . El juego Icosian de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano . [3] La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, en particular por Karl Menger , quien define el problema, considera el obvio algoritmo de fuerza bruta y observa la no optimalidad. del vecino más cercano heurístico:
Primero fue considerado matemáticamente en la década de 1930 por Merrill M. Flood, quien buscaba resolver un problema de enrutamiento de un autobús escolar. [5] Hassler Whitney en la Universidad de Princeton presentó el problema de vendedor ambulante poco después. [6]
En las décadas de 1950 y 1960, el problema se hizo cada vez más popular en los círculos científicos de Europa y los EE. UU. Después de que RAND Corporation en Santa Mónica ofreciera premios por los pasos para resolver el problema. [5] George Dantzig , Delbert Ray Fulkerson y Selmer M. Johnson hicieron notables contribuciones de RAND Corporation, quienes expresaron el problema como un programa lineal de enteros y desarrollaron el plano de corte.Método para su solución. Escribieron lo que se considera el artículo seminal sobre el tema en el que, con estos nuevos métodos, resolvieron una instancia con 49 ciudades de manera óptima al construir un recorrido y demostrar que ningún otro recorrido podría ser más corto. Dantzig, Fulkerson y Johnson, sin embargo, especularon que, dada una solución casi óptima, podríamos encontrar la optimalidad o probarla agregando una pequeña cantidad de desigualdades adicionales (recortes). Usaron esta idea para resolver su problema inicial de 49 ciudades usando un modelo de cuerda. Descubrieron que solo necesitaban 26 cortes para llegar a una solución para su problema de 49 ciudades. Si bien este documento no proporcionó un enfoque algorítmico a los problemas de TSP, las ideas que contenían eran indispensables para crear métodos de solución exactos para el TSP,[5] Además de los métodos de corte de planos, Dantzig, Fulkerson y Johnson usaronalgoritmos deramificación y límite quizás por primera vez. [5]
En las décadas siguientes, el problema fue estudiado por muchos investigadores de matemáticas , informática , química , física y otras ciencias. En la década de 1960, sin embargo, se creó un nuevo enfoque, que en lugar de buscar soluciones óptimas, se produciría una solución cuya longitud esté probablemente demarcada por un múltiplo de la longitud óptima, y al hacerlo se creen límites más bajos para el problema; Estos pueden ser utilizados con aproximaciones de rama y límite. Un método para hacer esto fue crear un árbol de expansión mínimo de la gráfica y luego duplicar todos sus bordes, lo que produce el límite de que la longitud de un recorrido óptimo es como máximo el doble del peso de un árbol de expansión mínimo. [5]
Christofides hizo un gran avance en este enfoque de dar un enfoque para el que conocemos el peor escenario. El algoritmo de Christofides dado en 1976, en el peor de los casos es 1.5 veces más largo que la solución óptima. Como el algoritmo era tan simple y rápido, muchos esperaban que diera paso a un método de solución casi óptimo. Este sigue siendo el método con el mejor de los peores escenarios. Sin embargo, en un caso especial bastante general del problema, fue superado por un pequeño margen en 2011. [7]
Richard M. Karp demostró en 1972 que el problema del ciclo hamiltoniano era NP-completo , lo que implica la dureza NP de la TSP. Esto proporcionó una explicación matemática para la aparente dificultad computacional de encontrar recorridos óptimos.
Se lograron grandes avances a fines de los años 70 y 1980, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver exactamente los casos con hasta 2,392 ciudades, usando planos de corte, ramas y atados .
En la década de 1990, Applegate , Bixby , Chvátal y Cook desarrollaron el programa Concorde que se ha utilizado en muchas soluciones de discos recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de casos de referencia de diferentes dificultades, que ha sido utilizado por muchos grupos de investigación para comparar resultados. En 2006, Cook y otros calcularon un recorrido óptimo a través de una instancia de 85,900 ciudades dada por un problema de diseño de microchip, que actualmente es la mayor instancia de TSPLIB resuelta. Para muchos otros casos con millones de ciudades, se pueden encontrar soluciones que garanticen estar dentro del 2-3% de un recorrido óptimo. [8]
Descripción [ editar ]
Como un problema gráfico [ editar ]
El TSP se puede modelar como un gráfico ponderado no dirigido , de manera que las ciudades son los vértices del gráfico , las trayectorias son los bordes del gráfico y la distancia de una ruta es el peso del borde. Es un problema de minimización que comienza y finaliza en un vérticeespecífico después de haber visitado cada vértice exactamente una vez. A menudo, el modelo es un gráfico completo ( es decir, cada par de vértices está conectado por un borde). Si no existe una ruta entre dos ciudades, agregar un borde arbitrariamente largo completará el gráfico sin afectar el recorrido óptimo.
Asimétrica y simétrica [ editar ]
En el TSP simétrico , la distancia entre dos ciudades es la misma en cada dirección opuesta, formando un gráfico no dirigido . Esta simetría reduce a la mitad el número de posibles soluciones. En el TSP asimétrico , las rutas pueden no existir en ambas direcciones o las distancias pueden ser diferentes, formando un gráfico dirigido . Las colisiones de tráfico , las calles de un solo sentido y las tarifas aéreas para ciudades con tarifas de salida y llegada diferentes son ejemplos de cómo esta simetría podría romperse.
Problemas relacionados [ editar ]
- Una formulación equivalente en términos de la teoría de gráficos es: dado un gráfico ponderado completo(donde los vértices representarían las ciudades, los bordes representarían las carreteras y los pesos serían el costo o la distancia de esa carretera), encuentre un ciclo de Hamilton con el menor peso.
- El requisito de regresar a la ciudad de inicio no cambia la complejidad computacional del problema, vea el problema de la ruta hamiltoniana .
- Otro problema relacionado es el problema del vendedor ambulante de cuellos de botella (TSP de cuellos de botella): encuentre un ciclo hamiltoniano en un gráfico ponderado con el peso mínimo del borde más pesado . Por ejemplo, evitando calles estrechas con grandes autobuses. [9] El problema tiene una importancia práctica considerable, aparte de las áreas evidentes de transporte y logística. Un ejemplo clásico es en circuito impreso de fabricación: programación de una ruta de la perforación de la máquina para perforar agujeros en una PCB. En las aplicaciones de taladrado o mecanizado robótico, las "ciudades" son partes a máquina o agujeros (de diferentes tamaños) a perforar, y el "costo de viaje" incluye el tiempo para volver a diseñar el robot (problema de secuencia de trabajo de una sola máquina).[10]
- El problema generalizado de los vendedores ambulantes , también conocido como el "problema de los políticos que viajan", trata sobre "estados" que tienen (una o más) "ciudades" y el vendedor tiene que visitar exactamente una "ciudad" de cada "estado". Se encuentra una aplicación para ordenar una solución al problema del stock de corte para minimizar los cambios de cuchillas. Otro se refiere a la perforación en lafabricación de semiconductores , véase, por ejemplo, la Patente de Estados Unidos 7.054.798 . Noon and Bean demostró que el problema generalizado del vendedor ambulante se puede transformar en un problema estándar del vendedor ambulante con el mismo número de ciudades, pero con una matriz de distanciamodificada .
- El problema del orden secuencial trata con el problema de visitar un conjunto de ciudades donde existen relaciones de precedencia entre las ciudades.
- Una pregunta de entrevista común en Google es cómo enrutar datos entre nodos de procesamiento de datos; Las rutas varían según el tiempo para transferir los datos, pero los nodos también se diferencian por su capacidad de computación y almacenamiento, lo que agrava el problema de dónde enviar los datos.
- El problema del comprador que viaja trata con un comprador que se encarga de comprar un conjunto de productos. Puede comprar estos productos en varias ciudades, pero a diferentes precios y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades, que minimice el costo total (costo de viaje + costo de compra) y que permita la compra de todos los productos requeridos.
Formulaciones integrales de programación lineal [ editar ]
El TSP se puede formular como un programa lineal entero . [11] [12] [13] Se conocen varias formulaciones. Dos formulaciones notables son la formulación de Miller-Tucker-Zemlin (MTZ) y la formulación de Dantzig-Fulkerson-Johnson (DFJ). La formulación de DFJ es más fuerte, aunque la formulación de MTZ sigue siendo útil en ciertos entornos. [14] [15]
Formulación de Miller-Tucker-Zemlin [ editar ]
Etiqueta las ciudades con los números 1,…, n y define:
Para i = 1, ..., n , vamos ser una variable ficticia, y finalmente tomar para ser la distancia de la ciudad i a la ciudad j . Entonces TSP puede escribirse como el siguiente problema de programación lineal de enteros:
El primer conjunto de igualdades requiere que se llegue a cada ciudad desde exactamente otra ciudad, y el segundo conjunto de igualdades requiere que desde cada ciudad haya una salida a exactamente otra ciudad. Las últimas restricciones hacen que haya un solo recorrido que cubra todas las ciudades, y no dos o más recorridos inconexos que solo cubran colectivamente todas las ciudades. Para probar esto, se muestra a continuación (1) que cada solución factible contiene solo una secuencia cerrada de ciudades, y (2) que para cada recorrido único que cubre todas las ciudades, hay valores para las variables ficticias Que satisfacen las restricciones.
Para probar que cada solución factible contiene solo una secuencia cerrada de ciudades, basta con mostrar que cada contorno en una solución factible pasa a través de la ciudad 1 (observando que las ecualizaciones aseguran que solo puede haber uno de esos recorridos). Porque si sumamos todas las desigualdades correspondientes aPara cualquier subtour de k pasos que no pasen por la ciudad 1, obtenemos:
Lo que es una contradicción.
Ahora se debe mostrar que para cada recorrido que cubre todas las ciudades, hay valores para las variables ficticias Que satisfacen las restricciones.
Sin pérdida de generalidad, defina el recorrido como originario (y finalizando) en la ciudad 1. Elija si la ciudad i se visita en el paso t ( i , t = 1, 2, ..., n). Entonces
ya que puede ser no mayor que n yNo puede ser inferior a 1; De ahí que se cumplan las restricciones siempre que por , tenemos:
satisfaciendo la restricción.
No hay comentarios:
Publicar un comentario