4.4.1. El problema del viajante.
Heurística voraz 2)
- Una solución será un conjunto de aristas (a1, a2, ..., an) que formen un ciclo hamiltoniano, sin importar el orden.
- Empezar con un grafo sin aristas.
- Selección: seleccionar la arista candidata de menor coste.
- Factible: una arista se puede añadir a la solución actual si no se forma un ciclo (excepto para la última arista añadida) y si los nodos unidos no tienen grado mayor que 2.
Solución: ((2, 3), (4, 5), (3, 4), (1, 2), (1, 5))
Coste = 10+15+20+45+50 = 140
Conclusiones:
- Ninguno de los dos algoritmos garantiza la solución óptima. Sin embargo, normalmente ambos dan soluciones buenas, próximas a la óptima.
- Posibles mejoras: buscar heurísticas mejores; repetir la heurística 1 con varios orígenes; ó bien, a partir de la solución del algoritmo intentar hacer modificaciones locales para mejorar esa solución.