« »

A-practicando en la ciudad (I)

calendario22/01/2008reloj03:17calendarioCategorí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 :P

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

TagsTags: , , ,

3 comentarios

  1. WhisKiTo — 22 enero 2008 03:30

    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 :(

  2. Cabañes — 22 enero 2008 09:56

    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

  3. Ayoze — 23 enero 2008 17:33

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

Los comentarios están cerrados.