• Author / Uploaded
• Alfredo Cobá

Citation preview

El problema del agente viajero (TSP de Travelling Salesman Problem) es un problema de optimización combinatoria estudiado en la ciencia computacional teórica. El problema fue formulado por primera vez como un problema matemático en 1930 y se trata de uno de los problemas más intensamente estudiados en optimización. El problema del agente viajero consiste en encontrar la ruta más corta que debe llevar a cabo un vendedor que, comenzando por una ciudad de origen visite un determinado y preestablecido conjunto de ciudades y vuelva a la ciudad original, con la restricción de que por cada ciudad sólo pase una vez. Complejidad del problema: En el ámbito de la teoría de complejidad computacional, el TSP pertenece a la clase de problemas NP-completos. Por lo tanto, se supone que no hay ningún algoritmo eficiente para la solución de TSP. En otras palabras, el número de posibles soluciones es tan elevado que si pretendemos que el algoritmo encargado de la búsqueda de la solución óptima deba verificar una a una no tendremos tiempo de cálculo para hallarlo: es probable que en el peor de los casos el tiempo de resolución de cualquier algoritmo para TSP aumente exponencialmente con el número de ciudades, por lo que incluso en algunos casos de tan sólo cientos de ciudades se tardarán bastantes años de CPU para resolverlos de manera exacta. Algoritmos: Hay diversos algoritmos para resolver este problema, aunque no todos son exactos (no encuentran la solución óptima), sino que algunos hallan la solución por aproximación. 

Algoritmos exactos:

La solución más directa sería probar todas las combinaciones posibles y ver cual es la más barata (usando búsqueda por fuerza bruta). El tiempo de ejecución para este método ronda un factor polinomial de O(n!), el factorial del número de ciudades, por lo que esta solución es poco práctica incluso para solo veinte ciudades.

Los métodos de ramificación y poda tradicionales son capaces de procesar problemas del viajante de comercio de entre 40 y 60 ciudades. Esté es el método que usaríamos en un

principio ya que vamos a contar con pocas ciudades (puntos en este caso) y queremos calcular la solución óptima. 

Algoritmos heurísticos y de aproximación:

Se han ideado varios algoritmos heurísticos y de aproximación que son capaces de llegar a una buena solución rápidamente. Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) en un tiempo razonable, con una alta posibilidad de que solo se diferencien entre un 2 y 3% de la solución óptima. El problema del viajante de comercio es ya un problema estándar para muchos algoritmos heurísticos del campo de la optimización combinatoria como los algoritmos genéticos, el recocido simulado (SA), la búsqueda tabú, el algoritmo hormiga el método Cross-entropy (entropía cruzada).

Planteamiento del problema:

En nuestro caso vamos a tener a un tortillero que debe vender tortilla en varias casas y como hay mucho sol él quiere tardar lo menos posible en completar su ruta. Referencias http://blog.electricbricks.com/2010/06/travelling-salesman/ http://eio.usc.es/pub/mte/descargas/ProyectosFinMaster/Proyecto_774.pdf http://www.cs.us.es/~fsancho/?e=71

No se que les parezca el problema planteado. Abajo hay una pagina donde se pueden ver ejemplos solucionados http://doranellygonzalez.blogspot.mx/2010/05/proyecto-5-problema-del-viajante-tsp.html