4.4. Técnicas heurísticas.
Problema: Dado un grafo no dirigido, completo y ponderado G = (V, A), encontrar un ciclo simple de costo mínimo que pase por todos los nodos.
4.4.1. El problema del viajante.
- Es un problema NP, pero necesitamos una solución eficiente.
- Problema de optimización, donde la solución está formada por un grupo de elementos en cierto orden: podemos aplicar el esquema voraz.
- Posibilidades:
1) Los nodos son los candidatos. Empezar en un nodo cualquiera. En cada paso moverse al nodo no visitado más próximo al último nodo seleccionado.
2) Las aristas son los candidatos. Hacer igual que en el algoritmo de Kruskal, pero garantizando que se forme un ciclo.