4.3.6. Otros problemas con grafos.
Problema del viajante (agente viajero)
Dado un grafo no dirigido, completo y ponderado G = (V, A), encontrar un ciclo simple de costo mínimo.
- Ejemplos: Un repartidor de determinadas mercancías tiene encargos en varias ciudades. ¿Qué ruta debe seguir para que el costo de desplazamiento sea mínimo?
- El problema del viajante es un problema NP-completo, con un orden de complejidad exponencial. No existe una solución polinómica.
- Podemos aplicar heurísticas, obteniendo soluciones aproximadas, no necesariamente óptimas.