Problema del Agente Viajero.

PROBLEMA DEL AGENTE VIAJERO.

EL problema del agente viajero es quizás el más estudiado de los problemas de optimización combinatoria. Su popularidad se debe a que es fácil de plantear, pero difícil de resolver.

Se trata de un vendedor que tiene una lista de ciudades cada una de la cuales debe visitar solamente una vez; se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma.

Se puede resolver este problema explorando el árbol de todos los caminos posible y eligiendo aquel que tenga la longitud mínima; pero si existe n ciudades, el número de caminos diferentes entre ellas es (n-1)!, esto significa que todo depende de n! para resolver el problema.

Por ejemplo si tenemos 11 ciudades, (11-1)!  =10*9*8*7*6*5*4*3*2*1= 3,628,000 rutas posibles.

              El problema del agente viajero se puede resolver de diferentes maneras:

*Enumeración de todas las soluciones factibles (n-1)!.

*Métodos exactos. También llamados algoritmos óptimos, intentan descartar familias enteras de posibles soluciones, tratando así de acelerar la búsqueda y llegar a una óptima.

*Heurística. Son métodos obtienen buenas soluciones en tiempos de computo muy cortos, aunque sin garantiza la optimización de la solución.

http://www.postgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html

file:///C:/Users/juliO/Downloads/apuntes.pdf