3er proyecto AYDA PGCOMP 2012

tercer proyecto práctico para de Análisis y Diseño de Algoritmos
Postgrado de Computación de la Universidad de Los Andes

Contents

• 1  El trabajo
  • 1.1  El grafo
  • 1.2  Línea de comandos
  • 1.3  Archivo de entrada
• 2  Condiciones
  • 2.1  Evaluación
  • 2.2  Cooperación
  • 2.3  Fecha de entrega
• 3  Recomendaciones

1  El trabajo

El fin de este proyecto es entender el algoritmo de Dijkstra para la determinación del camino mínimo entre un par de puntos. Para tal efecto, se plantea como objetivo el desarrollar una versión del algoritmo de Dijkstra que sobre grafos cuyos nodos representan puntos en el plano determine el camino más corto entre un par de puntos.

1.1  El grafo

Como ya se dijo, los nodos del grafo son puntos (x,y) en un plano. Los valores de x e y son números enteros positivos.

Los pesos de los arcos son enteros positivos, cuyos valores son mayores o iguales que la distancia euclidiana entre los puntos que conectan.

1.2  Línea de comandos

El programa debe llamarse min, cuya sintaxis es la siguiente:

./min archivo origen-1 destino-2 [origen-2 destino-2 ...]
  

Los nodos se especifican mediante números entre [0,V) según el orden de aparición en el archivo de entrada. Por ejemplo, la línea

./min g1000 2 4 56 10 
  

Especifica que el archivo contentivo del grafo se llama g1000 y que se desean calcular los caminos mínimos entre los pares de nodos 2-4 y 56-10. Note que 2, por ejemplo, significa el punto que aparece de tercero en el archivo de entrada.

Pueden solicitarse tanto caminos como se requiera en una sola línea de comandos.

La salida debe ser una lista de líneas contentivas de los caminos mínimos junto con la distancia total. Por ejemplo, para el comando anterior, una hipotética salida sería: -1

(1,1281)-1790-(1443,1341)-1659-(1761,1053)-1726-(1765,2612)-1191-(1467,2360) = 6366
(5741,6139)-2418-(4686,4397)-1369-(4191,3132) = 3787

1.3  Archivo de entrada

La primera línea del archivo contiene el número de nodos.

La segunda línea el número de arcos.

Luego, las siguientes |V| líneas con pares de enteros correspondientes a los puntos en el plano que componen el grafo.

Finalmente, las |E| líneas finales consisten en tríos que describen los arcos y cuales consisten: número nodo origen - número nodo destino - peso.

He aquí un ejemplo:

10
22
208 498
360 466
0 64
151 499
73 118
46 198
93 193
172 334
198 467
269 423
4 9 658
7 9 352
0 1 639
3 9 510
1 2 683
0 3 370
1 3 831
3 6 473
5 8 327
4 3 765
6 5 521
2 4 736
8 2 744
0 5 663
6 9 683
4 5 388
4 1 550
9 1 763
7 8 275
8 3 606
0 6 891
8 0 538 

Son 10 nodos y 22 arcos. El primer punto, enumerado 0, es (208,498) y el último punto, enumerado 9, es (93,193). El peso entre el punto (151,499) y el punto (269,423) es de 510.

En los siguientes enlaces se encuentran archivos de prueba

• https://www.dropbox.com/s/inh9e7zbuv7ko8j/g10.bz2
• https://www.dropbox.com/s/vuc1y05orhkswp6/g100.bz2
• https://www.dropbox.com/s/3hudye2znqxgzjp/g1000.bz2
• https://www.dropbox.com/s/1acliaghqpk9a22/g10000.bz2
• https://www.dropbox.com/s/6cbafh4jxca4hvm/g50000.bz2
• https://www.dropbox.com/s/v40b0fe8xilzdol/g1000000.bz2

Estos grafos de prueba, generados aleatoriamente, son del mismo estilo de los que usarán en la evaluación.

2  Condiciones

El lenguaje de programación debe ser C ⁺⁺, a ejecutarse sobre linux.

Puede usar ℵ_ω, el cual contiene una implementación, con una interfaz algo dificultosa, del algoritmo de Dijkstra, así como también permite emplear la heurística A^*. Sin embargo, esta vez usted es libre de diseñar su propio algoritmo y sus estructuras de datos. Tenga presente, sin embargo, que competirá contra la implementación de la biblioteca ℵ_ω.

La entrega debe ser un archivo tar contentivo de los fuentes y el makefile.

2.1  Evaluación

Velocidad	Precisión	Estilo
50%	30 %	20 %

  La velocidad se contabilizará en promedio y normalizada a la mayor velocidad registrada entre los participantes. La precisión es el porcentaje de cercanía respecto a la solución exacta hasta un máximo de 150 %, al partir del cual será negativo. Por ejemplo, si el valor del camino mínimo es 100 pero el calculado suyo es 120, entonces su nota para la precisión será el 80 %, o sea 16 ptos. En contraste, atención, si su solución es 170, entonces la precisión se tomaría como -30 % y su nota sería -6 ptos. Por tanto, si ud se anima a acelerar los cálculos mediante la técnica A^*, entonces estudie muy bien los grafos de prueba. Efectúe pruebas de contraste de A^* respecto a Dijkstra completo que le permitan corroborar:

1. Que la solución es buena, circunscrita al 150% de error, o mejor: que la solución es exacta.
2. Que se calcule más rápido que Dijkstra puro.

2.2  Cooperación

El código debe ser de su autoría individual.

  Se conmina a utilizar la lista para intercambiar ideas y compartir resultados de ejecuciones u otros archivos de prueba. No está permitido compartir código.

Si desea alguna conocer alguna solución para algunos de los archivos de entrada, entonces solicítela a través de la lista.

2.3  Fecha de entrega

Hasta las 12 pm del lunes 24 de septiembre. La entrega se debe hacer por email a la dirección leandro.r.leon@gmail.com con el subject AYDA: proyecto 3. Por favor, no olvide especificar este subject porque si no arriesga que no se localice el trabajo al momento de la corrección.

3  Recomendaciones

1. Cuenta habida de la escala y de que habrán varias solicitudes de cálculos de caminos mínimos, asegúrese de manejar adecuada y correctamente la memoria. Consecuentemente, puesto que los grafos de prueba serán de alta escala, una fuga de memoria (memory leak) puede ser bastante grave, pues restringe la memoria disponible para los cálculos de los caminos siguientes.
2. Considere diseñar un tipo de grafo que ocupe menos espacio que el actual de ℵ_ω. Hay una versión experimental basada en listas simplemente enlazadas, solicítela si desea considerarla.

   También considere diseñar un tipo grafo basado en arreglos y no en listas. Sin embargo, en caso de que opte por esta vía, tome en consideración que el tiempo de carga del grafo desde memoria secundaria a primaria se contabiliza en la prueba. Este comentario se hace porque probablemente una implementación de grafos con arreglos que ocupe menos memoria que con listas deberá hacer más de una pasada en el archivo. Una para conocer cargar los nodos y contar los arcos de cada nodo. Luego, en la segunda pasada, es que se cargarían los arcos.

---

This document was translated from L^AT_EX by H^EV^EA.