PROYECTO 5 - Problema del Viajante

~PROBLEMA DEL VIAJANTE~

~TPS~

Éste problema consiste en encontrar un recorrido de longitud mínima para un viajante que tiene que visitar varias ciudades y volver al punto de partida, conocida la distancia entre las ciudades.

Éste problema, también conocido como el Problema del viajante de comercio, es uno de los problemas de optimización más famosos en el campo computacional; aparentemente su solución es muy sencilla, pero es desde el punto de vista práctico, desde el punto de vista teórico, las técnicas empleadas para su solucion, son solo aproximaciones, tal es el caso que muchos algoritmos clásicos no son capaces de resolver el problema, debido a todas combinaciones posibles para su solucion.
Por ello se han aplicado distintas técnicas computacionales como : heuríticas evolutivas y redes de Hopfield, solo por mencionar algunas.


*Planteamiento del problema



Sean N ciudades de un territorio, el objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta y que pase una sola vez por una de las ciudades y minimice la distancia recorrida por el viajante.
La distancia entre cada ciudad viene dada por la matriz D: N*N, donde d[x,y], representa la distancia que hay entre la ciudad x y la ciudad y.


*Complejidad Computacional

El problema TSP, está entre los problemas de complejidad Np-Completos, esto es los problemas que no se pueden resolver en tiempo polinomial en funcion del tamaño de la entrada, en éste caso N es el numero de ciudades a visitar por el viajante.

*Pseudocódigo del algoritmo

//Problema del viajante usando heurística voraz
método viajanteVoraz(Grafo g)
Lista ciudades por visitar=g.listadeNodos()
c=ciudadesporVisitar.extraePrimera()
Lista= itinerario = {c}
mientras ciudades por visitar no esté vacía
hacer cprox= ciudad más próxima a c en ciudadesporVisitar
//elimina la más próxima de la lista a visitar
// y la añade al itinerario
ciudadesporVisitar.extrae(cprox)
itinerario.añadeAlFinal(cprox)
c=cprox //cprox pasa a ser la ciudad actual
fhacer
//vuelve al comienzo
itinerario.añadeAlFinal(itinerario.primera())
fmétodo

*Análisis Asintótico

Para encontrar la solucion mas óptima, éste algoritmo crece de forma exponencial con la entrada del problema, que en éste caso, sería el numero de nodos o vértices, que son las ciudades a visitar.
Por lo tanto, cuanto mayor sea el numero de nodos, mayor va a ser el numero de rutas posibles y por consiguiente mayor será el esfuerzo requerido todas ellas.
* Así que el análsis asintótico es N^2


*Estructuras de datos utilizadas




Para este algoritmo la estructura utilizada es el de 'GRÁFO'

Un grafo es un conjunto de objetos llamados vértices o nodos, unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias, entre elementos de un conjunto.







*EJEMPLO

~Compañia de teléfono~

Elegir una ruta que deben seguir los recolectores de dinero de cabinas públicas instaladas en una ciudad.


Cinco cabinas de teléfonos b,c,d,e,f, para las que se conocen sus coordenadas relativas a la central teléfonica 'a' desde la que reparten los recolectores y a donde deben regresar al terminar, y se supone que la distancia entre cada dos puntos viene dado por una línea recta.






Éste ejemplo lo solucioné por el método de Heurística Voraz


Consiste en ir seleccionando parejas de puntos que serán visitados de forma consecutiva:

*Se seleccionará primero aquella pareja entre los que la distancia sea minima

*Se seleccionará la siguiente pareja separada con una distancia minima, siempre y cuando ...
1. No se visite un punto dos veces o más
2. No se cierre el recorrido, antes de visitar todos los puntos

En este ejemplo, las parejas ordenadas son ...

Y los pasos a seguir son ...




Y al terminar éstos pasos, el resultado es ...






Éste recorrido no es el más óptimo, pues su longitud es de 50 unidades, es el cuarto mejor recorrido de entre los sesenta posibles y es más costoso que el óptimo en un 3.3%






*Aplicaciones




El problema tiene considerables aplicaciones prácticas, aparte de las de lógista de logística de transporte, que cualquier negocio de reparto, grande o chico, conoce. Por ejemplo en robótica, permite resolver problemas de fabricacion para minimizar el numero de desplazamientos al realizar una serie de perforaciones en una plancha o en un circuito impreso. Tambien puede ser usado en el control optimizado de semáforos.





*Presetación

Problema del viajante

View more presentations from danielaaguilar.

Presentacion
Bibliografia1
Bibliografía2
Bibliografía3
Bibliografia4