Rafa me ha recordado la opción -boost al compilar, y la verdad, que los tiempos han mejorado increíblemente (sin tocar nada más del programa). Aquí los resultados:

 
jormaro@duero ~/practica2 $time ./a.out < 9_ciudades.txt ; time ./a.out < 10_ciudades.txt;time ./a.out < 11_ciudades.txt ; time ./a.out < 12_ciudades.txt
910.5
SOR-BRG-PAL-VAL-LEO-ZAM-SAL-AVI-SEG-SOR
 
real    0m1.169s
user    0m1.140s
sys     0m0.020s
974.7
SOR-ARN-SEG-SAL-ZAM-LEO-VAL-PAL-BRG-MIR-SOR
 
real    0m11.956s
user    0m11.930s
sys     0m0.020s
985.7
SOR-ARN-SEG-AVI-SAL-ZAM-LEO-VAL-PAL-BRG-MIR-SOR
 
real    2m5.911s
user    2m5.820s
sys     0m0.000s
1110.9
SOR-ARN-SEG-AVI-SAL-ZAM-PNF-LEO-VAL-PAL-BRG-MIR-SOR
 
real    24m45.139s
user    24m44.500s
sys     0m0.010s
 

Ahora toca ponerse con la programación dinámica. A ver que sale

Ando terminando una práctica de Estructura de Datos, y en lo que termina de ejecutarse la prueba con 12 ciudades (lleva ya un buen rato), os dejo los resultados hasta ahora. El programa tiene un concepto sencillo, se trata del problema del viajante, que tiene que pasar por n ciudades de la forma más eficiente posible, y pudiendo cambiar la dirección tan solo en el extremo más al oeste (va de este a oeste y luego vuelve al origen de oeste a este). Sencillo, ¿no? Pues mirad los resultados de mi algoritmo de fuerza bruta

 
jormaro@duero ~/practica2 $time ./a.out < 5_ciudades.txt
343.0
ORIGEN-INT1-INT2-EXTREMO-FALLO-ORIGEN
 
real    0m0.079s
user    0m0.060s
sys     0m0.030s
 
jormaro@duero ~/practica2 $time ./a.out < 9_ciudades.txt
910.5
SOR-BRG-PAL-VAL-LEO-ZAM-SAL-AVI-SEG-SOR
 
real    3m11.552s
user    3m11.500s
sys     0m0.010s
 
real    33m28.323s
user    33m27.470s
sys     0m0.020s
 

Decir que básicamente lo que hago es generar las n! posibles permutaciones de todas las ciudades, y escoger entre ellas la de mejor distancia. Es el peor algoritmo que hay, pero es el más fácil de implementar, y por algo hay que empezar. A ver si mañana consigo aplicar alguna estructura de datos propiamente dicha. Se admiten sugerencias

EDITO: seguimos viendo la maravillosa eficiencia de un algoritmo de fuerza bruta...

 
jormaro@duero ~/practica2 $time ./a.out  < 10_ciudades.txt
974.7
SOR-ARN-SEG-SAL-ZAM-LEO-VAL-PAL-BRG-MIR-SOR