Definición del problema:
El problema del Vendedor Viajero, también conocido como Problema del Viajante, es un problema que a primera vista parece sencillo de resolver, pero en la práctica es un problema matemático en el cual su solución representa un gran problema. Esto ocurre dado que en teoría se conoce la forma de resolverlo, pero en la práctica aquella solución no es aplicable debido al gran tiempo computacional que demanda, inclusive para conjuntos pequeños de ciudades.
Para su solución se han aplicado distintas técnicas computacionales, entre ellas heurísticas, redes de Hopfield, algoritmos genéticos, etc.
En qué consiste el problema:
Consiste en un agente de ventas que tiene “n” ciudades por visitar, comenzando y terminando en la misma cuidad, visitando solamente una vez cada cuidad, y haciendo que el recorrido sea el costo mínimo, este costo puede estar expresado en términos de tiempo o distancia, es decir recorre el mínimo de kilómetros o lleva a cabo un torn en el menor tiempo posible.
El problema consiste en encontrar una ruta que, empezando y terminando en la misma ciudad, recorra sólo una vez las ciudades restantes y que a la vez esta ruta sea la mínima posible.
Los costos son simétricos en el sentido de que viajar desde la ciudad X a la ciudad Y tiene el mismo costo que viajar desde la ciudad Y a la ciudad X. La condición de visitar todas las ciudades implica que el problema se reduce a decidir en qué orden las ciudades van a ser visitadas.
Complejidad computacional:
El problema del Vendedor Viajero es un problema NP
Completo en un orden de complejidad exponencial.
No existe una solución polinómica.
Podemos aplicar técnicas heurísticas ,obteniendo
Soluciones aproximadas en un 97% ,no necesariamente
optimas.
Pseudocódigo:
| Algoritmo 2-Òptimo |
| El algoritmo trabaja con una variable, en este caso x = 1. Mientras este valor sea uno, se marcan todos los vértices como no visitados y a x se le asigna el valor 0, x = 0. Bajo estas dos nuevas condiciones, mientras queden vértices a ser explorados, se selecciona un vértice i y se examinan todos los movimientos 2-opt que incluyan la arista del vértice i al siguiente vértice de la ruta. Si con alguno de los movimientos hechos se reduce el la longitud de la ruta, se realiza el mejor movimiento y se actualiza el valor de x a x = 1, en caso contrario se asigna el vértice i como visitado y se sigue con el ciclo. |
| begin
|
Análisis asintótico del algoritmo:
Todos los algoritmos requeridos para resolverlos requieren
tiempo exponencial en el peor caso. Es decir, son sumamente
difíciles de resolver.
— El análisis asintótico seria: N!
Estructuras de datos utilizadas:
Fue mediante arboles.
El problema lo represente mediante grafos
El problema se puede moldear fácilmente mediante un grafo completo dirigido, en donde los vértices son las ciudades y los arcos son los caminos, dichos arcos deben de tener un peso, y este representa la distancia que hay entre dos vértices que están conectados por medio de dicho arcos.
Ejemplos:
Ejemplo # 1
Un estudiante tiene que visitar 4 bibliotecas las cuales se representan A-B-C-D.
Y su punto de partida es la cuidad o nodo A.
¿Qué ruta debe seguir para que el costo sea mínimo?
La distancia entre los puntos es:
A-B=7 B-C=10
A-C=9 B-D=4
A-D= 8 C-D=15
Se representa mediante el grafo siguiente:
Solución por medio de fuerza bruta:
Esta solución se trata de checar todos los caminos posibles.
En este ejemplo nos dice que el punto de partida es de la cuidad A .
Ya que tenemos todos los caminos posibles eliminamos los inversos, ya que es lo mismo y es perdida de tiempo también andar checándolos.
Ahora de los 3 caminos inversos, sustituimos por los valores que representa cada distancia de un nodo a otro.
Y lo calculamos, el camino que sea menor, eses es la trayectoria que andamos buscando
En esta imagen la represento en color rojo
Ahora también lo podemos hacer por la técnica de heurística – mediante el vecino más cercano
Si nos damos cuenta analizamos del nodo A es menos distancia digiriese hacia el nodo B y del nodo B es menos distancia dirigirnos hacia el nodo C y de ahí hacia el nodo D y por ultimo regresar hacia el nodo A.
La solución nos salió igual que la que calculamos por fuerza bruta, la gran diferencia es que por fuerza bruta nos tardamos mucho más tiempo que utilizado la técnica del vecino más cercano. , pero también como lo mencione arriba no siempre se llega a la solución optima por medio del vecino más cercano solo son aproximaciones.
En este caso si nos dio igual.
Ejemplo #2
Un repartidor de mercancías tiene encargos en varias ciudades, las cuales se representan A-B-C-D-E, y debe iniciar en la cuidad A
¿Qué ruta debe seguir para que el costo sea mínimo?
Las distancias son:
A-B=7 A-E=20 B-E=11 D-E=17
A-C=9 B-C=10 C-D=15
A-D=8 B-D=4 C-E=5
El problema se puede solucionar por fuerza bruta o utilizado heurística entre otras.
Representación del grafo:
Solución por fuerza bruta:
*Checamos los caminos posibles:
Ahora vamos a eliminar lo inversos, así ahorramos tiempo.
Estos son los caminos que nos quedaron después de eliminar los inversos y sustituyendo los valores de las distancias dadas.
A-B-D-C-E-A=7+4+15+5+20=51
A-B-D-E-C-A=7+4+17+5+9=42
A-B-C-D-E-A=7+10+15+17+20=69
A-B-E-D-C-A= 7+11+17+15+9=59
A-D-C-B-E-A=8+15+10+11+20=64
A-D-C-E-B-A=8+15+5+11+7=46
A-D-E-B-C-A=8+17+11+10+9=55
A-D-E-C-B-A=8+17+5+10+7=47
A-D-B-C-E-A=8+4+10+5+20=47
A-D-B-E-C-A=8+4+11+5+9=37
A-C-D-B-E-A=9+15+4+11+20=59
A-C-B-D-E-A=9+10+4+17+20=60
Representacion del grafo por solucion bruta
Como nos podemos dar cuenta el más optimo es el de 37 kilómetros de distancia.
Ahora lo hacemos por medio del vecino más cercano.
De la cuidad A es más corto digerirse hacia la cuidad B y de la cuidad B dirigirse hacia la cuidad D y de la D a la C y de la C hacia la E y de la E regresarse hacia la cuidad .
Checando la solución de fuerza bruta y el resultado que nos dio ahora nos damos cuenta que no es lo mas optimo, sin embrago con la heurística es muchísimo mas rápido de solucionar el problema.
Ejemplo #3
Ejemplo 3
Hay que encontrar la ruta que tiene que recorrer el vendedor para que sea la mínima posible.
Las ciudades están representadas como O-1-2-3-4-5
Y las distancias e dichas ciudades están representadas en esta tablita, lo hice con una tablita por que el grafo contiene muchas rutas y pues se visualiza mejor por medio de la tablita así no nos confundimos.
Y las distancias e dichas ciudades están representadas en esta tablita, lo hice con una tablita por que el grafo contiene muchas rutas y pues se visualiza mejor por medio de la tablita así no nos confundimos.
Las distancias de la cuidad :
0-1 =10
O-2=6
O-3=8
0-4=7
0-5=15
Les dije esas distancia de la cuidad 0 para que vieran como se interpreta la tablita así puedan saber cuáles son las demás distancias y donde aparece una rayita son las inversas.
Con la tablita nos damos cuenta que la distancia mínima que pose al nodo 0 la posee la cuidad 2.
Por lo que es la primera cuidad incluida en la ruta.
La ruta es 0-2-0
Ahora hay que checar cual es la cuidad mas cerca a la ruta anterior, con la tablita nos damos cuenta que la distancia mínima la pose la cuidad 2 con una distancia de 5 kilómetroshacia la cuidad 1 , y como solo hay dos ciudades más solo la agregamos a la ruta.
Ahora la ruta nos quedaría
0-1-2-0
En la segunda iteración, Ahora volvemos a checar cual es la cuidad más cerca de la ruta que anterior, y con la tablita nos damos cuenta que la posee la cuidad 4 con una distancia de 7 km a la cuidad 2
Pero necesitamos saber entre que ciudades se incorporara la cuidad 4
Para eso hacemos el cálculo del costo marginal, es decir
cuando pongo (4,0) ahi queire decir la la distancia que hay entre esa cuidad hacia la que se indica en cada caso eso es lo refrente a buscar la distancia menor , pero si tien dudas me dicen ojala que me hayga podido explicar o mas facil cuando ven un punto lo checan en la tablita y lo sustituyen por la distancia .
(0,4)+(4,1)-(0,1)= 7+15-10=12
(0,4)+(4,2)-(0,2)=7+7-6=8 <<< menor ruta
(1,4)+(4,2)-(1,2)=16+7-10=18
Como nos podemos dar cuenta la cuidad 4 la vamos a incorporar entre la cuidad 0 y 3
La ruta nos quedaría:
0-1-2-4-0
Tercera intercesión .Ahora con ruta anterior volvemos a checar cual es la ciudad más corta, y con la tablita nos damos cuenta que la posee la cuidad 3 a 4 kilómetros de la cuidad 4.
Ahora necesitamos saber entre ciudades se incorporara la cuidad 3
Para eso hacemos el cálculo del costo marginal, decir entré que ciudades el coto es le mínimo
(0,3)+(3,1)-(0,1)=8+20-10=18
(0,3)+(3,4)-(0,4)=8+4-7=5 <<
(2,3)+(3,4)-(2,4)=14+4-7=11
(2,3)+(3,4)-(2,1))=14+20-5=29
Ahora la ruta nos queda
0-1-2-4-3-0
Finnalmente la ultima cuidad que se agregara a la ruta sera la cuidad 5
Ahora necesitamos saber entre ciudades se incorporara la cuidad 5
Para eso hacemos el cálculo del costo marginal, decir entré que ciudades el coto es el mínimo
(0,5)+(5,1)-(0,1)=15+16-10=21
(0,5)+ (5,3)-(0,3)=15+8-8=15
(3,5)+ (5,4)-(3,4)=12+6-4=14
(2,5)+(5,4)-(2,4)=8+6-7=7 <<<
(1,5)+(5,2)-(1,2)16+8-5=19
Finalmente la ruta nos queda:
0-1-2-5-4-3-0= 10+5+8+6+4+8=41
Robótica
Una aplicación del Problema del Vendedor Viajero tiene que ver con la resolución de problemas de fabricación de máquinas que realizan trabajos repetitivos y de alta precisión. Por ejemplo, minimizar la cantidad de desplazamientos que la máquina debe realizar para perforar una plancha o en una tarjeta de circuito integrado. Cada desplazamiento posee un costo, por lo que se busca que la máquina realice el menor número de desplazamientos posibles.
Una de las aplicaciones del Problema del Vendedor Viajero es en logística de transporte. En diversos tipos de situaciones interesa saber la ruta mínima desde un punto de origen, pasando por puntos conocidos una vez y que finalice en el origen.
Por ejemplo un sistema de despacho, donde la planificación de la ruta de los vehículos de la empresa busca minimizar el consumo de combustible y que el tiempo de reparto de sus productos se produzca lo antes posible.
Otro ejemplo se da en la recolección de basura, donde la planificación de la ruta tiene relación con el problema. Otra aplicación en transporte está relacionada con la definición de recorridos en un sistema de transporte público, en que se definen ciertos criterios para crear recorridos de distancia mínima entre diversos puntos o bien recorridos que posean un tiempo mínimo entre diversos puntos.
Juego o Dinámica :
en este aplicacion de apples se hace mediante el algoritmo genetico.
http://lear.inforg.uniovi.es/ia/Genetico-TSP/TSP.htm
Comprendi bien el problema , trate de explicarme lo mejor posible. sin embargo si hay dudas me dichen .
ResponderEliminarse me hizo divertido hacer los grafos , estar checando cada camino ,lo unico que tengo duda esque al ejemplo 3 se le entienda , ya que no es lo mismo subiendo la explicacion a darla , sin embargo decidi dar de clase el ejemplo dos porque esta mas sencillo y lo primero que se deve hacer comprender el concepo ya entendiendolo es mucho mas facil, resover problemas mas complejos.
Me senti traquila ,me tome mi tiempo sufciente , me organize bien .
Ahora solo a esperar resultados.
Me senti muy agusto al hacer este proyecto , fue divertido , hacer cada grafo, estar analizando los caminos.
ResponderEliminarMe supe organizar bien para que estuviera a tiempo, trate de explicarme lo mejro posible, sin embargo siento que se peude confucnir un poco con el ejemplo 3 pero si no le entienden me dicen con gusto les tratare de explicar de la mejor manera posbile, solo tomen en cuenta que los valores estan en al tablita si le ponia los valores como en lso otrras dos ejempos en el grafo ivaa ser mas confuso ,y tambien en lo que se pueden confundir es al momento de analizar la cuidad mas corta , para acomodar entre que puntos es menor solo tomen en cuenta los puntos que aparecen por ejemplo (0,1)con la tablita se basan es solo para saber la disctancia . Bueno espero que si le entiendan cualquir duda me la hacne saber .
Que onda dora, pues a mi em parecio muy completo tu proyecto, hay bastantes y variados ejemplos para comprenderlo y los explicas muy bien yo si les entendi, en lo de la complejida computacional, es muy bueno saber el porcentaje que se tiene para optimizar con este algoritmo, de echo este algoritmo tambien se asocia con el Algoritmo de Dijkstra, que tambien trata de caminos minimos, tambien me intereso lo de las aplicaciones en especial el de robotica.
ResponderEliminarEn fin me parece muy completo y buena info nos vemos saludos cdt bye.
hola, soy joel de clase de jueves me parecio muy buena tu explicación de este tema y pues si lo entendi muy bien porque esta relacionado a mi proyecto que es el ciclo de hamilton este problema es una aplicacion de las mas conocidas sobre el ciclo de hamilton, esta super completo tu analisis del proyecto.
ResponderEliminarnos vemos adios.
holaaaa ya se son cosas que pasan yo opino que diste una buena exposicion :D
ResponderEliminarbueno respondiendo a tu pregunta
en la clase solo explique en si el ejemplo de fibonacci que ya nos habia explicado la maestra tania y la maestra elisa que al final puso que como hacer una tabla la cual no pude hacer asi al momento en el que me dijo pero ya cuando la habia comenzado supe de que hablaba esa tabla me la acaban de enseñar en matematicas discretas yo opino bueno en lo que yo comprendi por ejemplo si nos encargaran un proyecto o pongamos de ejemplo este que acabamos de hacer de la maestra elisa que tiene ciertos requisitos con los que debe contar yo comprendi que es bueno de ese problema grande que tienes dividirlo en partes pequeñas podria ser buscar parte por parte a fondo y asi podemos llegar a crear el proyecto :D es algo que a mi se me quedo mas que nada de este tema :D
Este comentario ha sido eliminado por el autor.
ResponderEliminarmuchísimas gracias por responder mi pregunta
ResponderEliminaraa con respecto a lo que me paso en clase si son cosas que pasan , pero sabes aprendemos de los errores , bueno si no me hubiera corregido hubiese pensado que estaba bien ,varios compañeros cometimos el mismo error
note que a los compañeros que les toco el ciclo de Hamilton las dos versiones cometieron el mismo error
recuerdo bien que la maestra le dijo a la chava que cometió el mismo error que dora Nelly y al entrar a los blogs de mis compañeros para comentar me doy cuenta de que ellos también lo habían cometido , a diferencia de que ellos eso no lo expusieron en su clase.
pero fue bueno así lo corregimos y nunca se me olvidara eso de análisis , como la profe me explico un ejemplo de n=4 vi cual era la diferencia de ponerle el análisis n^2 ya n! gracias a eso entendí ya bien mi gran error.
bueno saludos a todos .me encantarían que comentaran , alguna duda sobre todo si tienen en el ejemplo 3 que es el que se les puede dificultar un poco mas nadamos me lo hacen saber , pienso que se pueden confundir un poco más porque los primeros dos estaba bien fáciles y el 3 esta fácil solo que hay que estar checando la tablita de las distancias
Hola dora nelly, a mi me gusto mucho la forma en que expusiste tu presentacion en la clase. Logre comprender muy bien el algoritmo lo unico que me confundio fue eso del analisis pero ya observando tu blog pude entenderlo.
ResponderEliminarEn cuanto a lo de mi problema podras darte cuenta que es parecido a la actividad que la profesora nos habia puesto la clase pasada bueno lo que hize fue dibujar el grafo (cubo) y desde esa perspectiva podemos darnos cuenta que las aristas se intersecaban y resultaba que no era plano. Pero si dibujabamos ese mismo grafo pero desde otra perspectiva (pudiste darte cuenta en el juego,que muchos grafos simplemente no pueden ser planos)observabamos que habia una manera en que ese grafo fuera plano ya que tenia los mismos vertices(8) y las mismas aristas(12) pero visto desde otra perspectiva.
Para analizar esto puedes usar el teorema de euler tal como el ejemplo de mi blog.
Cualquier cosa me dejas un comentario.
Gracias!
Saludos!
Hola Doris, yo creo que la Dra. si deberia darte los puntos de asesorias, ya que me consta que si te informaste del tema y estuviste al pediente de cada detalle para que saliera lo mejor posible. En fin yo estoy a favor de ke t los den esos puntos.
ResponderEliminarMuy bien todo.
ResponderEliminarMuy bien hecho tu proyecto y muy padre el problema del TSP, es uno de mis favoritos, he leído que hay algoritmos de aproximación a través de los arboles de expansión mínima o parecidos y mediante algoritmos probabilistas.
ResponderEliminarHola, si quisieras modificar la tabla para que no vuelva al origen y se quede en la última ciudad. ¿Cómo lo harías?
ResponderEliminarGracias por el trabajo.
Bueno ya se que es un blog de hace 2 años, pero observando el ejemplo numero 2, se puede ver a simple vista en la figura, que la distancia entre B-E, es mucho mayor que D-E.
ResponderEliminarEntonces pregunto que es lo incorrecto el gráfico, o las mediciones del mismo?
Sin ánimos de ofender, pero si observan nuevamente el ejemplo numero 2, se darán cuenta de lo que digo.
Saludos
Oye, muy bueno todo pero la suma de los recorridos en los ejemplos estan mala, creo que el primero....
ResponderEliminarEste comentario ha sido eliminado por el autor.
ResponderEliminarEste comentario ha sido eliminado por el autor.
ResponderEliminarHola que tal tu blog me a servidor de mucha ayuda, es un gran post pero en el ejemplo 3 creo que hay un error.
ResponderEliminarPuesto que asumimos que es lo mismo ir de (1;4) que de (4;1) y al momento del calculo de costo marginal los consideraste como (4;1)=15 y (1;4)=16 (creo que lo tomaste el caso(1;4) como el (1;5)=16 en la tablita). Por lo que el calculo corrector, seria en tal caso:
(0,4)+(4,1)-(0,1)= 7+15-10=12
(0,4)+(4,2)-(0,2)=7+7-6=8 <<< menor ruta
(1,4)+(4,2)-(1,2)=15+7-10=17
Buenas,
ResponderEliminarLa solución del primer ejemplo es errónea. El camino A-B-D-C-A no suma 25 sino 35. Por lo que la solución sería A-D-B-C-A que suma 31.
Espero que sirva de ayuda.
Saludos