Problema del agente viajero

En el Problema del Agente Viajero - TSP (Travelling Salesman Problem), el objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta, o el tiempo total del recorrido.

El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.

El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas.

El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).

En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dado un largo “L”, la tarea es decidir cuál grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades.

La cantidad de rutas posibles en una red está determinada por la ecuación:

(n-1)!

Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24, y a medida que el número de nodos aumente la cantidad de rutas posibles crece factorialmente. En el caso de que el problema sea simétrico la cantidad de rutas posibles se reduce a la mitad, es decir:

( (n-1)! ) / 2

Lo cual significa un ahorro significativo en el tiempo de procesamiento de rutas de gran tamaño.

¿QUE NOMBRES TIENE ESTE TIPO DE PROBLRMAS?

problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante

¿CUAL ES ELOBJETIVO DEL PROBLEMA DEL VIAJERO?

encontrar un recorrido completo que conecte todos los nodos de una red.

¿EN QUE AÑO FUE FORMULADO EL PROBLEMA?

1930

¿EN QUE TEMAS FUE IMPORTANTE ESTA  INVETIGACION?

operaciones y en la ciencia de la computación.

¿CUALES SON LAS APLICACIONES QUE TIENE EL TSP?

a planificación, la logística y en la fabricación de circuitos electrónicos.

SI LA CANTIDAD DE RUTAS POSIBLES EN UNA RED ESTA DERTERMINADA COMO ES LA ECUACION?

(n-1)!

EN EL CASO DE QUE EL PROBLEMA SEA SIMETRICO ,LA CANTIDAD DE RUTAS POSIBLES ,¿CUAL SERIA LA ECUACION?

( (n-1)! ) / 2 

¿CUALES SON LAS SIGLAS EN INGLES DEL TSP?

Travelling Salesman Problem

permutaciones

la definición intuitiva de permutación, como reordenamientos de los elementos de un conjunto se formaliza con el uso del lenguaje de funciones matemáticas

Ejemplos:

1. En el caso de dos elementos {1,2} solo hay dos posibles posiciones: ${\displaystyle (1,\,2)}$ y ${\displaystyle (2,\,1)}$.
2. En el caso de tres elementos {1, 2, 3} cada permutación diferente sobre el conjunto {1, 2, 3} equivale a una forma de ordenar los elementos.

${\displaystyle {\begin{matrix}A&{\xrightarrow {Identidad}}&A\\1&\longmapsto &1\\2&\longmapsto &2\\3&\longmapsto &3\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(2,\,1,\,3)}}&A\\1&\longmapsto &2\\2&\longmapsto &1\\3&\longmapsto &3\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(3,\,2,\,1)}}&A\\1&\longmapsto &3\\2&\longmapsto &2\\3&\longmapsto &1\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(1,\,3,\,2)}}&A\\1&\longmapsto &1\\2&\longmapsto &3\\3&\longmapsto &2\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(2,\,3,\,1)}}&A\\1&\longmapsto &2\\2&\longmapsto &3\\3&\longmapsto &1\\\end{matrix}}}$, ${\displaystyle {\begin{matrix}A&{\xrightarrow {(3,\,1,\,2)}}&A\\1&\longmapsto &3\\2&\longmapsto &1\\3&\longmapsto &2\\\end{matrix}}}$

La combinatoria trata del número de diferentes maneras que existen de considerar conjuntos formados a partir de elementos de un conjunto dado, respetando ciertas reglas, como el tamaño, el orden, la repetición, la partición. Así un problema combinatorio consiste usualmente en establecer una regla sobre cómo deben ser las agrupaciones y determinar cuántas existen que cumplan dicha regla. Básicamente, tres asuntos: permutaciones, combinaciones y variaciones.

Un tipo importante de esas agrupaciones son las llamadas permutaciones. Dada una n-tupla ordenada de los elementos de un conjunto, el número de permutaciones es el número de n-tuplas ordenadas posibles.

La primera forma de escribir una permutación ${\displaystyle \sigma }$, aunque no es la más compacta, consiste en escribirla en forma de matriz de dos filas, situando en la primera los elementos ordenados del dominio 1, 2, 3,...,n, y en la segunda fila las imágenes correspondientes a los elementos reordenados ${\displaystyle \sigma (1),\,\sigma (2),\,\sigma (3),\,\dots ,\,\sigma (n).}$

Por ejemplo, dado el conjunto ordenado ${\displaystyle \{1,...,8\}}$ podemos expresar una permutación ${\displaystyle \sigma }$ sobre éste mediante una matriz de correspondencias:

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&4&5&7&6&1&8&2\end{pmatrix}}}$

Existe otra notación más compacta, llamada notación de ciclos. Un ciclo de longitud es una permutación que intercambia cíclicamente elementos y fija los restantes. Esta notación revela mejor la estructura interna de la permutación. Para ello:

1. Empezamos con cualquier elemento. Lo escribimos, a su derecha escribimos su imagen, a la derecha de esta, la imagen de su imagen, y seguimos así hasta que se complete un ciclo.
2. Luego cogemos cualquier elemento no contenido en el primer ciclo, volvemos a escribir su imagen a su derecha, y continuamos hasta completar el segundo ciclo.
3. El proceso continúa hasta que la permutación entera ha quedado descrita como producto de ciclos disjuntos.

Siguiendo con el mismo ejemplo de antes, en notación de ciclos, ${\displaystyle \sigma }$ quedaría expresada como composición de dos ciclos:

${\displaystyle \sigma }$= (1 3 5 6)(2 4 7 8).

Una trasposición es una permutación que intercambia dos elementos y fija los restantes. Dicho de otro modo, es un ciclo de longitud 2. Una propiedad interesante es que cualquier permutación se puede construir como una composición de transposiciones, aunque no de manera única. Dadas dos descomposiciones en transposiciones de una permutación se cumple que ambas usaran un número par o ambas usarán un número impar, eso permite definir de manera unívoca la signatura de una permutación.

Las trasposiciones permiten descomponer una permutación cualquiera de una forma diferente a la descomposición en ciclos. En particular, las trasposiciones que aparezcan no tendrán que ser disjuntas: Por ejemplo, el ciclo (1 2 3 4) = (1 2) (2 3) (3 4). Aquí el orden de aplicación es importante: en primer lugar (3 4) deja el 4 en su sitio definitivo y el 3 descolocado. Después (2 3) deja en su sitio definitivo el 3 y el 2 descolocado, que quedará recolocado definitivamente por (1 2).

Para ver que cualquier permutación se descompone como producto de trasposiciones bastará ver que todo ciclo lo hace. La descomposición no es única. Por ejemplo:

${\displaystyle (a_{1},\ldots ,a_{n})=}$

${\displaystyle (a_{1},a_{2})(a_{2},a_{3})\cdots (a_{n-1},a_{n})=(a_{1},a_{n})(a_{1},a_{n-1})\cdots (a_{1},a_{2}).}$

El número de trasposiciones de la descomposición tampoco es único. Por ejemplo:

${\displaystyle (a_{1},\ldots ,a_{n})=}$

${\displaystyle (a_{n-1},a_{n})(a_{1},a_{n-1})(a_{n-1},a_{n})(a_{1},a_{n-1})(a_{1},a_{n-2})\cdots (a_{1},a_{2}).}$