Etiquetas

domingo, 16 de mayo de 2010

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



Presentacion
Bibliografia1
Bibliografía2
Bibliografía3

Bibliografia4






11 comentarios:

  1. A mi punto de vista, cumplí con lo que se pedía, creo que hice un muy buen trabajo, pero la palabra de mis compañeros y maestra, es la que en verdad importa, espero que si comprendan el tema, ami me gusto mucho, fue el proyecto que mas disfruté hacer, porque el tema me gusto y me gusto investigar; o talves influyo que es el último del semestre.

    ResponderEliminar
  2. Si le entendi a tu proyecto pero me puedes repetir porque en el ejemplo no tomas en cuenta b y e? porfa :P

    ResponderEliminar
  3. concurdo con mi compañera cynthia telles, muy buen trabajo

    de los mejores que eh visto
    me da gusto saver que hay personas que disfrutan el hacer proyectos (Y)

    ResponderEliminar
  4. Gracias por sus comentarios, en verdad fue el proyecto que más me gustó :)

    Cynthia: en el ejemplo si seleccionamos como una arista los puntos 'b' y 'e', éstos mismos se visitarian mas de una vez, puesto que ya se habia seleccionado (d,e)y (a,b) y una de mas condiciones de éste problema, es NO pasar por un punto msas de una vez; ésta es la razón por la que se descarta :)

    ResponderEliminar
  5. Esta muy bien explicado, pues parece que estas hablando tu.

    Y coincido con Erik, es bueno que al hacer el proyecto se disfrute, por que piesno que asi le dedicas mas tiempo y esfuerzo, y las cosas salen mucho mejor, que cuando las haces de mala gana.

    Con respecto al contenido, yo tenia una idea no muy buena de como se resuelve este problema, pero ya me doy cuenta que para encontrarle una solucion, se deben de tomar "las cosas que se quieren hacer", para que sea correcto y eficaz el resultado.

    ResponderEliminar
  6. daniela

    yo hice ese mismo problema

    a verison jueves. Esta muy entendible la informacion de tu blog.Ambas utilizamos la tecnica heurísticas por medio dle veciono ams ceraco , sin embargo yo tambine lo hice por fuerz bruta para que vieran que por medio de vecino ams cercano no siempre el resultado es optimo.

    El ejemplo que hiciste es algo paresido al ejemplo #3 de los que yo hice.

    bueno felicidades por tu proyecto.

    zaludos

    ResponderEliminar
  7. me falto comentar que con la tecnica heuristica es mucho mas rapido llegar al resultado.

    ResponderEliminar
  8. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  9. daniela

    Hoy di mi clase

    solo para que le corijas proque tu en tu blog pusiste que el analisis asintotico es N^2 y no esta bien , hoi la profe me hizo ver el gran error que hay ahi.

    No puede ser con esa funcion porque es exponencial y al poner N^2 es polinimico y no es polinimico si no exponencial.

    Por consiueinte quedaria
    N!

    Ese fue el gran error que comenti y por el que me quitaron 1 punto , pero valio la pena porque de los erorres se aprenden y pues lo importante esque me quedo claro el proque estaba mal que es lo mas improntante

    dejo mi blog porque la profe dijo que al momento de comentar dejaramos algo que nos reconeociara
    http://doranellygonzalez.blogspot.com/

    ResponderEliminar
  10. Ahora veo el error, en el analisis asintotico si puse que crecia en forma exponencial, y en la presentacion tambien y puse lo de N!, hasta ahorita estoy viendo que puse N^2... pero si ves la presentacion, si dice N! .. Gracias por tu comentario

    ResponderEliminar
  11. Bueno, Dora Nelly ya se adelantó con lo que iba a poner yo ;)

    ResponderEliminar