SuscríbeteA-practicando en la ciudad (I)
22/01/2008 
03:17 
Categorías: 
ComentarAndo 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
Tags:
Yo optaría por una solución bastante más sencilla:
Mientras lees este párrafo, resultarás interesado. Sin embargo, has de saber que no vale para nada, que simplemente te estoy haciendo perder el tiempo para que te muerdas las uñas hasta que llegas a la solución más sencilla. ¡¡no miras abajo!! es mejor, más interesante y reconfortante leerlo todo seguido, así que sigue aquí. Punto punto punto. «…». Eiffel es un cagao, y esta práctica sólo puede hacerse en eiffel, porque si la haces en Pascal te puedes morir creando funciones para una clase de la práctica. la idea es más o menos sencilla, pero la solución más fácil es:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
joder, déjala para julio, como haré yo, que entonces el examen valdrá 10/10 y así te ahorras la práctica
De todas formas, ójala hubiese sacado tiempo para hacerla… me gusta esta asignatura. una lástima 🙁
Vamos pat!! dale duro a esas practicas que son un dolor de huevos. Intentaria pensar algun tipo de solucion pero paso que harto tengo con lo mio xDD
Fuerza bruta… se llama backtracking hombre de dios. y no has de generar las n! permutaciones, aplica alguna poda curiosa para no seguir desarrollando el arbol por donde no lo necesitas ya…