Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Problema del Agente Viajero (TSP)

No description
by

Daniel Arboleda Betancur

on 26 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Problema del Agente Viajero (TSP)

Dada una lista de ciudades y la distancia entre cada par de ellas ¿Cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?
Un Poco de Historia
El origen del Problema del Agente Viajero no está bien definido, pero hay varias personas que postularon o publicaron éste estudiado y complejo problema.
Como un problema de Grafos
Nuestro problema puede modelarse como un grafo ponderado, no dirigido y completo.
Aplicaciones
Algoritmos Propuestos
Problema del Agente Viajero (TSP)
Problema
Debido a que el TSP puede modelarse como un grafo, nos encontramos en que el grafo puede ser asimétrico o simétrico.
Asimétrico y Simétrico
Grafo Dirigido
Grafo No Dirigido

William Rowan Hamilton
Descripción
Se tiene un número de nodos (ciudades, localidades, tiendas, empresas, etc.) que deben ser visitados por una entidad (persona, agente viajero, automotor, avión, autobús, etc.), sin visitar 2 veces el mismo nodo. Si tenemos 3 nodos (a, b y c) por visitar, entonces tendríamos una función de combinaciones sin repetición c(3,2),
Características
TSP se encuentra clasificado como Problema de optimización Combinatoria, es decir, es un problema donde intervienen cierto número de variables donde cada variable puede tener N diferentes valores y cuyo número de combinaciones es de carácter exponencial
Algoritmo Base
Elegir el nodo inicial i
Hacer
Si el nodo más cercano no se ha visitado
Visitar nodo j
Actualizar lista de nodos visitados
Costo_total = costo_total + costoij
Nodo i = nodo j
Hasta haber visitado todos los nodos

Al ser el Problema del Agente Viajero muy complejo para dar una solución óptima en un tiempo razonable y aceptable, se han empleado algunos algoritmos que puedan dar (No en su totalidad) una buena solución.
Conclusiones
El problema del Agente Viajero (TSP) es un problema cuya solución ha sido estudiada desde los inicios de la Inteligencia Artificial considerando que su aplicación puede ser en cualquier área de estudio cuyos problemas reflejen una situación donde se tienen diferentes puntos a visitar con un costo considerado en el enlace entre dichos puntos (costo: recursos empleados como distancia, tiempo, monto económico, etc.).
Muchas Gracias
Full transcript