domingo, 3 de julio de 2011

Tarea Miercoles 6/7/11 (Fundamentos de la complejidad computacional)

PROBLEMA NP-COMPLETO.
TSP: Travelling Salesman Problem (Problema del Vendedor Viajero)
El problema del viajante es uno de los problemas mas estudiados y analisados en el campo de la logica combinatoria. Consiste en encontrar un camino hacia las ciudades empezando y acavando en la misma , pero solo puede pasar una sola ves por cada ciudad y tiene que minimisar el tiempo de viaje.



Para poder resolver el problema tenemos que usar un algoritmo que repita todas las soluciones posibles y solo asi nos daremos cuenta de cual de las opciones due la mas eficiente, viendo cual fue la distancia minima que viajo.

"Ir seleccionando parejas de puntos que seránvisitados de forma consecutiva:
– se seleccionará primero aquella pareja de puntos entre los que la distancia sea mínima;
– a continuación, se selecciona la siguiente pareja separada con una distancia mínima siempre que esta nueva elección no haga que: u se visite un punto dos veces o más (es decir, que el punto aparezca tres o más veces en las parejas de puntos seleccionadas), ou se cierre un recorrido antes de haber visitado todos los puntos.De esta forma, si hay que visitar n puntos (incluido el origen), se selecciona un conjunto de n parejas de puntos (que serán visitados de forma consecutiva) y la solución consiste en reordenar todas esas parejas de forma que constituyan un recorrido"

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.


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

Algoritmo:





Aplicaciones:
Las aplicaciones para este problema varían desde logística hasta turismo, para optimizar la cantidad de dinero usada en viajes comerciales de una empresa en varias ciudades, entre otras.


Analisis Asintotico

Considerando n ciudades (tamaño de la entrada = n), la dimensión del espacio de búsqueda (permutaciones) es: (n-1)!/2.
Para n=10, hay 181.440 permutaciones posibles.
Para n=12 (caso del ejemplo para Alemania) hay 19.958.400 permutaciones posibles.
Para n=20 hay 60.822.550.204.416.000 permutaciones posibles.











Como todo algoritmo de optimisacion, el TSP es fácil de analizar pero difícil de optimizar, para esto hay diferentes métodos:


Método greedy .
Idea: tratar de construir una solución seleccionando iterativa-mente elementos componentes de menor costo.
Para algunos problemas con estructura particular, la solución construida es una solución óptima.


Método Del vecino mas cercano:
Se comienzos eligiendo un vértice inicial (j1). Una ves elegido mediremos las distancias entre este vértice y los demás, después de eso viendo todas las distancias elijemos la mas corta y lo llamamos (j2) y seguimos midiendo distancias pero ahora en base a j2 y a la mas corta la llamamos j3, así repetimos hasta terminar los todos los vértices.

Link hacia la programacion:http://www.probcomp.com/cpp-programs/TSP-11/

Bibliografia:

3 comentarios:

  1. Maestra esta es la tarea de el miercoles.

    ResponderEliminar
  2. Ah, no estaba terminada :) Pues, quito los de extra y te pongo 14 por la tarea. Me hubiera gustado ver un resumen de la reducción de SAT a Ciclo Hamiltoniano y luego de Ciclo Hamiltoniano a TSP o algo así...

    ResponderEliminar