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
