(2 resultados encontrados. Mostrando del 1 al 2)

22

Ene

2008

1

A-practicando en la ciudad (II)

reloj20:55 calendarioCategorías: General, Personal, PHP, Programas, Universidad

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:

  1.  
  2. 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
  3. 910.5
  4. SOR-BRG-PAL-VAL-LEO-ZAM-SAL-AVI-SEG-SOR
  5.  
  6. real 0m1.169s
  7. user 0m1.140s
  8. sys 0m0.020s
  9. 974.7
  10. SOR-ARN-SEG-SAL-ZAM-LEO-VAL-PAL-BRG-MIR-SOR
  11.  
  12. real 0m11.956s
  13. user 0m11.930s
  14. sys 0m0.020s
  15. 985.7
  16. SOR-ARN-SEG-AVI-SAL-ZAM-LEO-VAL-PAL-BRG-MIR-SOR
  17.  
  18. real 2m5.911s
  19. user 2m5.820s
  20. sys 0m0.000s
  21. 1110.9
  22. SOR-ARN-SEG-AVI-SAL-ZAM-PNF-LEO-VAL-PAL-BRG-MIR-SOR
  23.  
  24. real 24m45.139s
  25. user 24m44.500s
  26. sys 0m0.010s
  27.  

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

22

Ene

2008

3

A-practicando en la ciudad (I)

reloj03:17 calendarioCategorías: Peripecias, Personal, PHP

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.