Tsp Vfr
Páginas: 6 (1294 palabras)
Publicado: 22 de mayo de 2012
TSPEl problema del vendedor viajero Algoritmo del mejor vecino
El problema del vendedor viajero
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
El algoritmo del mejor vecino
Seleccionar el nodo inical Para todo nodo sin visitar
Visitar el nodo con menor distancia desde el nodo actual
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao PabloBuenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
EjemploNew York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Extensión del algoritmo del mejor vecino
Para cada uno de los nodos
Ejecutar el algoritmo del mejor vecino Guardar el Mejor tour encontrado
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos AiresSantiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Tour Obtenidos
Santiago – Buenos Aires – París – New York – Sao Pablo - Santiago Con una distancia de2+1+9+7+9 = 28 Sao Pablo – Buenos Aires – París – New York – Santiago – Sao Pablo Con una distancia de 4+1+9+11+1 = 26 New York – Buenos Aires – París – Santiago – Sao Pablo – New York Con una distancia de 6+1+12+9+7 = 35
Click to add title
El problema del vendedor viajero Algoritmo del mejor vecino
1
El problema del vendedor viajero EL algoritmo del mejor vecino
El problema del vendedorviajero
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
2
El problema consiste en visitar todos los nodos de un grafo iniciando desde un modo y terminando en el mismo. Es decir, consiste en buscar un tour que recorra todas las ciudades una sola vez con el minimo costo, menor distancia, menor tiempo, etc. A este camino que recorre todos los nodos y termina en elmismo nodo que comienza se le conoce como “circuito Hamiltoniano”
El algoritmo del mejor vecino
Seleccionar el nodo inical Para todo nodo sin visitar
Visitar el nodo con menor distancia desde el nodo actual
3
El algoritmo consiste en tomar la ciudad inicial, luego ir añadiendo ciudades al tour con el criterio de la menor distancia. Asi en cada paso se va visitando la ciudad mascercana a la actual. Este algoritmo nos entrega una buena solución, pero no necesariamente la mejor de todas las solución
Ejemplo
●
Click to add an outline
París 9 20 9 12 11 1 2 6 7
New York
Sao Pablo
4
Buenos Aires Santiago
4
Se desea que un vendedor inicie su recorrido en santiago y visite a cada uno de sus clientes ubicado en Buenos Aires, Sao Pablo, New York y Paris. Alfinal del día debe retornar a su casa en santiago.
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
5
Desde Santiago, la ciudad mas cercana es Buenos Aires con una distancia de 2 unidades.
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
6
Desde Buenos Aires la ciudad mas cercana es Paris, con 1 unidad dedistancia
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
7
Desde Paris la ciudad mas cercana es New York, con 9 unidad de distancia
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
8
Desde New York la ciudad mas cercana es Sao Pablo, con 7 unidad de distancia No se puede tomar Buenos Aires que esta a 6...
El problema del vendedor viajero
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
El algoritmo del mejor vecino
Seleccionar el nodo inical Para todo nodo sin visitar
Visitar el nodo con menor distancia desde el nodo actual
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao PabloBuenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
EjemploNew York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Extensión del algoritmo del mejor vecino
Para cada uno de los nodos
Ejecutar el algoritmo del mejor vecino Guardar el Mejor tour encontrado
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos AiresSantiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
Tour Obtenidos
Santiago – Buenos Aires – París – New York – Sao Pablo - Santiago Con una distancia de2+1+9+7+9 = 28 Sao Pablo – Buenos Aires – París – New York – Santiago – Sao Pablo Con una distancia de 4+1+9+11+1 = 26 New York – Buenos Aires – París – Santiago – Sao Pablo – New York Con una distancia de 6+1+12+9+7 = 35
Click to add title
El problema del vendedor viajero Algoritmo del mejor vecino
1
El problema del vendedor viajero EL algoritmo del mejor vecino
El problema del vendedorviajero
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
2
El problema consiste en visitar todos los nodos de un grafo iniciando desde un modo y terminando en el mismo. Es decir, consiste en buscar un tour que recorra todas las ciudades una sola vez con el minimo costo, menor distancia, menor tiempo, etc. A este camino que recorre todos los nodos y termina en elmismo nodo que comienza se le conoce como “circuito Hamiltoniano”
El algoritmo del mejor vecino
Seleccionar el nodo inical Para todo nodo sin visitar
Visitar el nodo con menor distancia desde el nodo actual
3
El algoritmo consiste en tomar la ciudad inicial, luego ir añadiendo ciudades al tour con el criterio de la menor distancia. Asi en cada paso se va visitando la ciudad mascercana a la actual. Este algoritmo nos entrega una buena solución, pero no necesariamente la mejor de todas las solución
Ejemplo
●
Click to add an outline
París 9 20 9 12 11 1 2 6 7
New York
Sao Pablo
4
Buenos Aires Santiago
4
Se desea que un vendedor inicie su recorrido en santiago y visite a cada uno de sus clientes ubicado en Buenos Aires, Sao Pablo, New York y Paris. Alfinal del día debe retornar a su casa en santiago.
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
5
Desde Santiago, la ciudad mas cercana es Buenos Aires con una distancia de 2 unidades.
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
6
Desde Buenos Aires la ciudad mas cercana es Paris, con 1 unidad dedistancia
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
7
Desde Paris la ciudad mas cercana es New York, con 9 unidad de distancia
Ejemplo
New York
París 9 20 9 12 11 1 2 4 6 7
Sao Pablo
Buenos Aires Santiago
8
Desde New York la ciudad mas cercana es Sao Pablo, con 7 unidad de distancia No se puede tomar Buenos Aires que esta a 6...
Leer documento completo
Regístrate para leer el documento completo.