A-practicando en la ciudad (I)

calendario22/01/2008 reloj03:17 calendarioCategorías: Peripecias, Personal, PHP ComentarComentar

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 😛

  1.  
  2. jormaro@duero ~/practica2 $time ./a.out < 5_ciudades.txt
  3. 343.0
  4. ORIGEN-INT1-INT2-EXTREMO-FALLO-ORIGEN
  5.  
  6. real 0m0.079s
  7. user 0m0.060s
  8. sys 0m0.030s
  9.  
  10. jormaro@duero ~/practica2 $time ./a.out < 9_ciudades.txt
  11. 910.5
  12. SOR-BRG-PAL-VAL-LEO-ZAM-SAL-AVI-SEG-SOR
  13.  
  14. real 3m11.552s
  15. user 3m11.500s
  16. sys 0m0.010s
  17.  
  18. real 33m28.323s
  19. user 33m27.470s
  20. sys 0m0.020s
  21.  

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...

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

Comentarios