Problema del viajante


Problema del viajante

Problema del viajante

Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida?

Contenido

Base del problema

El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado (Para una mayor profundidad en el tema ver el artículo NP-completos).

El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos.

Enunciado

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c0,c2,...,cn − 1} tal que d_P=\sum_{i=0}^{N-1}{d[c_i,c_{i+1mod(N)}]} sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.

Por ejemplo las rutas posibles entre 12 ciudades son 479.001.600 combinaciones y los caminos individuales entre ciudades son el sumatorio de las 12-1 ciudades es decir 66.

Se puede demostrar que el requerimiento de volver a la ciudad de partida no cambia la complejidad computacional del problema.

Situación actual respecto de su resolución

Desde el punto de vista práctico, el problema no está resuelto y desde el punto de vista teórico, las técnicas empleadas son sólo aproximaciones. No suponen una resolución real del TSP y sólo ofrecen soluciones aproximadas suficientemente aceptables.

Los algoritmos clásicos no son capaces de resolver el problema general, debido a la explosión combinatoria de las posibles soluciones. Por ello, a su solución se han aplicado distintas técnicas computacionales: heurísticas evolutivas, redes de Hopfield, etc.

Casuística

Hay algoritmos que se basan en una configuración concreta del problema. Por ejemplo, algunos algoritmos de ramificación y consolidación se pueden utilizar para resolver problemas de entre 40 a 60 ciudades.
Otros han mejorado a éstos con técnicas reminiscentes de la programación lineal que permiten resolver el TSP para valores de N entre 120 y 200 ciudades.
En el año 2001 se utilizó una red de 110 ordenadores para resolver el TSP para las 15.112 poblaciones de Alemania y utilizando el equivalente computacional a 22,5 años de un PC.
En mayo del 2004 se aplicaron algunas de estas técnicas para la resolución del problema aplicado a las 24.978 poblaciones suecas en un ciclo de unos 72.500 km (probándose además que no se podía encontrar un ciclo más corto).

Los algoritmos genéticos, basados en heurísticas no encuentran soluciones exactas, pero permiten encontrar aproximaciones suficientemente buenas (un 97% de optimización) y se pueden aplicar a conjuntos de ciudades muy grandes (redes con millones de nodos) con tiempos de ejecución razonables en un superordenador (semanas o meses).

Convergencia del problema

Una formulación equivalente en términos de la teoría de grafos es la de encontrar en un grafo completamente conexo y con arcos ponderados el ciclo hamiltoniano de menor coste. En esta formulación cada vértice del grafo representa una ciudad, cada arco representa una carretera y el peso asociado a cada arco representa la longitud de la carretera.

El TSP está entre los problemas denominados NP-completos, esto es, los problemas que no se pueden resolver en tiempo polinomial en función del tamaño de la entrada (en este caso el número N de ciudades que el viajante debe recorrer). Sin embargo, algunos casos concretos del problema sí han sido resueltos hasta su optimización, lo que le convierte en un excelente banco de pruebas para algoritmos de optimización que pertenezcan a la misma familia (lo que en jerga matemática se denominan problemas isomorfos).

Aplicaciones

El problema tiene considerables aplicaciones prácticas, aparte de las más evidentes en áreas de logística de transporte, que cualquier negocio de reparto , pequeño o grande, conoce. Por ejemplo, en robótica, permite resolver problemas de fabricación para minimizar el número de desplazamientos al realizar una serie de perforaciones en una plancha o en un circuito impreso. También puede ser utilizado en control y operativa optimizada de semáforos, etc.

Véase también

Obtenido de "Problema del viajante"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Problema del viajante — El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A… …   Enciclopedia Universal

  • Problema abstracto — Saltar a navegación, búsqueda En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la… …   Wikipedia Español

  • Problema de rutas de vehículos — «VRP» redirige aquí. Para otras acepciones, véase VRP (desambiguación). Esquema básico de un VRP. Los problemas de rutas de vehículos (Vehicle Routing Problem VRP) en realidad son un amplio conjunto de variantes y personalizaciones de problemas.… …   Wikipedia Español

  • Problema de los caminos más cortos — Saltar a navegación, búsqueda Ejemplo de Grafo Ponderado En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las… …   Wikipedia Español

  • Algoritmo del vecino mas próximo — El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no …   Wikipedia Español

  • Paradoja del lingote de plata — Saltar a navegación, búsqueda La paradoja del lingote de plata, o también creación a partir de la nada es una paradoja ideada en 1985 (más tarde ampliamente descrita en el cuento corto ¡Es imposible, es imposible! ) que, en teoría, podría… …   Wikipedia Español

  • Búsqueda tabú — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de …   Wikipedia Español

  • Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

  • Ramificación y poda — Saltar a navegación, búsqueda El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica… …   Wikipedia Español

  • Joseph Kruskal — Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010)[1] fue un matemático y estadístico estadounidense. Contenido 1 Biografía 2 …   Wikipedia Español


Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.