Algoritmia básica (30229) - Grado en Ingeniería Informática
Escuela de Ingeniería y Arquitectura - Universidad de Zaragoza
El objetivo de la práctica es implementar y comparar la eficiencia en tiempo de distintos esquemas algorítmicos para la resolución del problema del viajante de comercio (TSP, Travelling Salesman Problem).
Tareas a realizar:
1- Implementar los siguientes esquemas algorítmicos vistos en clase para el problema del viajante de comercio:
- Fuerza bruta (enumeración de todos los posibles recorridos)
- Algoritmo voraz
- Programación dinámica
- Ramificación y poda
2- Calcular y comparar los tiempos de ejecución para distintos datos de entrada.
Para compilar el codigo basta con ejecutar el script
compilar.sh
Para lanzar una unica ejecucion basta con lanzar el script tsp:
./tsp -opt <nombre de fichero>
Lanza la bateria de pruebas utilizada para calcular los tiempos
./tests.sh