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}).}$

Mapa de Karnaugh

Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell.

Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones muy inmensas.

El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. Puesto que la tabla de verdad de una función de N variables posee 2^N filas, el mapa K correspondiente debe poseer también 2^N cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden fácilmente realizar a mano con funciones de hasta 6 variables, para funciones de mayor cantidad de variables es más eficiente el uso de software especializado

#	${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C}$	${\displaystyle D}$	${\displaystyle f(A,B,C,D)}$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

diagrama de arbol

Un diagrama de árbol o árbol de probabilidad es una herramienta que se utiliza para determinar si en realidad en el cálculo de muchas opciones se requiere conocer el número de objetos que forman parte del espacio muestral, estos se pueden determinar con la construcción de un diagrama de árbol.

El diagrama de árbol es una representación gráfica de los posibles resultados del experimento, el cual consta de una serie de pasos, donde cada uno de estos tiene un número infinito de maneras de ser llevado a cabo. Se utiliza en los problemas de conteo y probabilidad.

Para la construcción de un diagrama en árbol se partirá poniendo una rama para cada una de las posibilidades, acompañada de su probabilidad. Cada una de estas ramas se conoce como rama de primera generación.

En el final de cada rama de primera generación se constituye, un nudo del cual parten nuevas ramas conocidas como ramas de segunda generación, según las posibilidades del siguiente paso, salvo si el nudo representa un posible final del experimento (nudo final).

Hay que tener en cuenta que la construcción de un árbol no depende de tener el mismo número de ramas de segunda generación que salen de cada rama de primera generación y que la suma de probabilidades de las ramas de cada nudo ha de dar 1.

Existe un principio sencillo de los diagramas de árbol que hace que éstos sean mucho más útiles para los cálculos rápidos de probabilidad: multiplicamos las probabilidades si se trata de ramas adyacentes (contiguas), el ejemplo de alumna de la primera facultad, o bien las sumamos si se trata de ramas separadas que emergen de un mismo punto, el ejemplo de encontrar un alumno.

Ejemplos

Una universidad está formada por tres facultades:

• La 1ª con el 50% de estudiantes.
• La 2ª con el 25% de estudiantes.
• La 3ª con el 25% de estudiantes.

Las mujeres están repartidas uniformemente, siendo un 60% del total en cada facultad.

¿Probabilidad de encontrar una alumna de la primera facultad?

${\displaystyle P(alumna\ de\ la\ 1^{a}\ facultad)=0,5\cdot 0,6=0,3}$

¿Probabilidad de encontrar un alumno varón?

TORRES HANOI

Ahora hablaremos de las torres hanoi

¿que son las torres hanoi?

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.¹​ Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas.

¿Como se resuelven?

El juego consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples reglas:

1. Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes.
2. Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo.
3. Solo se puede desplazar el disco que se encuentre arriba en cada poste.

Una curiosa generalización del objetivo original del rompecabezas es comenzar desde una configuración dada de los discos, donde todos los discos no están necesariamente en el mismo poste, y llegar en un número mínimo de movimientos a otra configuración determinada. En general, puede ser bastante difícil calcular una secuencia más corta de movimientos para resolver este problema. Andreas Hinz propuso una solución y se basa en la observación de que, en la secuencia más corta de movimientos, se debe mover el disco más grande (obviamente, pueden ignorarse todos los discos más grandes que ocuparán el mismo poste tanto en la configuraciones inicial como en la final) se moverá exactamente una vez o exactamente dos veces.

Las matemáticas relacionadas con este problema generalizado se vuelven aún más interesantes cuando se considera el número promedio de movimientos en la secuencia más corta de movimientos entre dos configuraciones de disco iniciales y finales que se eligen al azar. Hinz y Chan Hat-Tung descubrieron de forma independiente⁶​⁷​ (véase también ⁸​^{:Chapter 1, p. 14}) que la cantidad promedio de movimientos en una torre de n discos viene dada por la siguiente fórmula exacta:

${\displaystyle {\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{59}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{59}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.}$

Tenga en cuenta que para n lo suficientemente grande, solo el primer y el segundo término no convergen a cero, por lo que obtenemos un expresión asintótica:${\displaystyle 466/885\cdot 2^{n}-1/3+o(1)}$, cuando ${\displaystyle n\to \infty }$. Así, intuitivamente, se podría interpretar que la fracción de ${\displaystyle 466/885\approx 52.6\%}$ representa la relación del trabajo que se debe realizar al pasar de una configuración elegida al azar a otra configuración elegida al azar, en relación con la dificultad de tener que cruzar la ruta de longitud "más difícil" ${\displaystyle 2^{n}-1}$ que implica mover todos los discos de un poste a otro. Una explicación alternativa para la aparición de la constante 466/885, así como un algoritmo nuevo y algo mejorado para calcular la ruta más corta, fue dada por Romik.⁹​

¿ES UN PROBLEMA DE PERMUTACION O DE COMBINACION?

Serie fibonassi

Aqui les hablaremos sobre la serie fibonacci

¿quien creo la serie fibonacci ?

Mucho antes de ser conocida en occidente, la sucesión de Fibonacci ya estaba descrita en la matemática en la India, en conexión con la prosodia sánscrita.

Susantha Goonatilake hace notar que el desarrollo de la secuencia de Fibonacci «es atribuido en parte a Pingala (año 200), posteriormente asociado con Virahanka(hacia el año 700), Gopāla (hacia 1135), y Hemachandra (hacia 1150).​ Parmanand Singh cita a Pingala (hacia 450) como precursor en el descubrimiento de la secuencia.⁶​

La sucesión fue descrita y dada a conocer en occidente por Fibonacci como la solución a un problema de la cría de conejos: «Cierto hombre tenía una pareja de conejos en un lugar cerrado y deseaba saber cuántos se podrían reproducir en un año a partir de la pareja inicial, teniendo en cuenta que de forma natural tienen una pareja en un mes, y que a partir del segundo se empiezan a reproducir

¿como es la serie fibonacci?

Gráfica de la sucesión de Fibonacci hasta ${\displaystyle f_{7}}$

En matemáticas, la sucesión o serie de Fibonacci es la siguiente sucesión infinita de números naturales:

${\displaystyle 0,1,1,2,3,5,8,13,21,34,55,}$ ${\displaystyle 89,}$ ${\displaystyle 144,}$ ${\displaystyle 233,}$ ${\displaystyle 377,}$ ${\displaystyle 610,}$ ${\displaystyle 987,}$ ${\displaystyle 1597\ldots \,}$

La sucesión comienza con los números 0 y 1,²​ y a partir de estos, «cada término es la suma de los dos anteriores», es la relación de recurrencia que la define

Triangulo de pascal

Aqui desmotraremos lo mas fundamental sobre un triangulo de pascal.

¿En primer lugar que es un triangulo de pascal?

El triángulo de Pascal es un triángulo de números enteros, infinito y simétrico Se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima. 

¿como se construye?

se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima.

¿cuales son sus aplicaiones?

Una forma de evitar tener que calcular uno a uno todos los coeficientes es utilizar el Triángulo de Pascal, ya que los coeficientes de la potencia n aparecen en la fila n+1 de dicho triángulo. Un ejemplo: aplicando la fórmula y la definición de número combinatorio tendríamos: (a + b)³ = 1·a³ + 3·a²b + 3·ab² + 1·b³.

¿para que sirve?

Este triángulo fue ideado para desarrollar las potencias de binomios. ... Esta expresión se denomina binomio de Newton. Esta fórmula del binomio de Newton desarrolla los coeficientes de cada fila en el triángulo de Pascal. Es por esto que existe una estrecha relación entre el triángulo de Pascal y los binomios de Newton.