miércoles, 3 de marzo de 2010

Proyecto #2

  • Problema del agente vajero 
(Travelling Salesman Problem)
Definición del problema

Un vendedor tiene que visitar n + 1 ciudades, cada una exactamente una vez. La distancia entre cada par de ciudades viene dada por dij (en general dij ≠ dji). El problema es encontrar el recorrido (tour) que comienza y termina en la misma ciudad y minimiza la distancia total recorrida.
Notas: La ciudad de comienzo es irrelevante. Se usa n + 1 por conveniencia notacional.
El problema del agente viajero puede modelarse facilmente mediante un grafo completo dirigido,en donde los vertices del grafo son las ciudades y los arcos son los caminos.Dichos arcos deben tener un peso,y este peso representa la distancia que hay entre dos vertices que estan conectados por medio de dicho arco. 
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.
También se puede plantear este problema con costo de viaje,en vez de el recorrido,pero en éste caso escogi el recorrido para el proyecto.De todas maneras es irrelevante en la teoría si es costo o recorrido,amenos que se desee aplicar en la vida cotidiana.

Ejemplo de Instancia:
Una ejemplo sencillo.
Tomando el inicio desde C1.
La solución óptima seria la serie de caminos con menor distancia total que pasen por todas las ciudades una sola vez y vuelva a la primera,en este caso C1.

Todos los caminos que se pueden tomar son:
Opción 1 (C1,C2,C3,C4,C1), sumando el recorrido total se obtiene 28.
Opción 2 (C1,C2,C4,C3,C1), sumando el recorrido total se obtiene 27.
Opción 3 (C1,C3,C2,C4,C1), sumando el recorrido total se obtiene 29.
Opción 4 (C1,C3,C4,C2,C1), sumando el recorrido total se obtiene 27.
Opción 5 (C1,C4,C2,C3,C1), sumando el recorrido total se obtiene 29.
Opción 6 (C1,C4,C3,C2,C1), sumando el recorrido total se obtiene 28.
Viendo todas los caminos posibles no se tiene uno,sino, dos caminos óptimos de los cuales eligir en los cuales se caminaría menos para pasar por todas las ciudades.
Éstos son la opción 4 y la opción 2,ambas con una distancia total de 27.

Problema de decisión :
Su problema de decisión correspondiente sería:
  • ¿Existe un recorrido (tour) mas corto que L?
El objetvo es determinar si existe un tour que su recorrido sea mas corto que L.
Esta es una simple pregunta de si o no.Si no hay un tour con un recorrido mas corto que L,L sera el tour mas corto.
NP-completo
En teória de la complejidad computacional el problema de decisión del TSP pertenece a la clase de NP-completo.Entonces,se asume que no hay un algoritmo eficiente para resolver TSPs.En otras palabras el peor caso de tiempo seria un algoritmo de TSP que aumenta exponencialmente con el numero de ciudades.
Algoritmo
Algoritmo por método voraz. 
Digamos que el recorrido/distancia que se busca con éste algoritmo será L.
  • Primero se observa desde la ciudad de inicio los caminos disponibles.Si lo hace una persona en la vida real,seria en un mapa.
  • De estos se escoje el que tenga una menor distancia hacia la siguiente ciudad.
  • Se repite el procedimiento en la siguiente ciudad,buscando de nuevo el camino más corto con excepción de que,el recorrido termine sin pasar por todas las ciudades,entonces se tomaria otro camino.
  • Se suman todos los recorridos.
Ejemplo del algoritmo en uso



Se obtiene 22 por el algoritmo voraz. Entonces L=22
Más otra solución podria ser:
Con recorrido o distancia total de 19.
Lo que significa que SI existe un tour que tiene menos recorrido que L.

Complejidad asintótica:
Notación  : O(n22n)
Click aqui para verla ampliada.
Acotaciones:
n22n
La funcion x^x es una cota superior asintótica de n22n
 La funcion e^x es una cota inferior asintótica de la funcion n22n
Por lo tanto la función que mas se asemeja a n22nes e^x,es decir que aumenta exponencialmente,en el caso del TSP con el número de ciudades que se agregan.

NP-duro
Ya que su problema de decisión es NP-Completo su problema de optimización es NP-duro.
Siguiendo los pasos se determina que este problema (TSP) es un problema NP-duro.
Se redujo el problema a un problema de decisión y se determino que dirá si unicamente cuando debe. 
Ahora la reducción fue eficiente ya que el problema de decisión,basado en un recorrido L que ya se tiene,dice si existe o no un camino mas corto que este.


Bibliografía:
Links útiles:
http://www-e.uni-magdeburg.de/mertens/TSP/node3.html
(Página donde se puede ver un pequeño programa que calcula las soluciones del TSP,muy recomendable,está en inglés)
    Nota: La mayoria de las imágenes fueron subidas por mi a photobucket a mi cuenta personal.
        Publicado por en
        Etiquetas: , ,

        2 comentarios:

        Suscribirse a: Enviar comentarios (Atom)