Proyecto 1: #2 Buscar una buena ruta

Objetivo: Buscar una buena ruta de un lugar a otro en un mapa.

Pareja de proyecto: Alan http://twowolvescorp.blogspot.com/

Este es el pseudocodigo:

#include < stdio.h >

main()

{

#define si 1, no 0;

/*Se declaran algunas variables, i, j y k serán índices para evaluar repeticiones.*/

double ndir, i, j, k;

/*Estas son matrices que contienen palabras.*/

char direcciones[ ][ ], caminos[ ];

/*Y acá se encuentran algunos números de precisión.*/

long float distancias[ ][ ], suma, menor, menoralt[ ];

printf(“Este programa calcula la distancia mas corta de uno o varios trayectos \nque se puede recorrer en un mapa, desde una dirección inicial a una final.”);

printf(“Cuantas direcciones son?: ”)

scanf(“%ld”, &ndir);

/*Se define la primera matriz nxn.*/

direcciones[ndir][ndir];

/*Ahora se van llenando los espacios de la primera fila de la matriz.*/

while (i<=ndir)

{

printf(“Direccion %d?: ”, i);

scanf(“%s”, &direcciones[i][1]);

i++;

}

printf(“Asignar la conexión o unión entre las direcciones:”)

/*Se sigue llenando la matriz pero ahora completamente, las conexiones de cada camino se escriben inmediatamente debajo de la fila en cada columna.*/

for (i=1; i<=ndir; i++)

{

printf(“La direccion %s, se conecta con,”, direcciones[i][1]);

for (j=2; j<=ndir; j++)

{

/*Este while crea un lista de las uniones que puedes elegir para cada dirección.*/

while (i<=ndir)

{

printf(“\n%ld. %s”, i, direcciones[i][1]);

i++;

}

i-=i+1;

printf(“la dirección(numero): ”);

scanf(“%ld”, &opcion);

if (opcion=1)

{

/*Seria ir a la misma dirección, carece de sentido.*/

printf(“Opción invalida, elegir otra...”);

}

/*El switch va llenando la matriz según la el numero elegido, en su posición correspondiente.*/

switch (opcion)

{

case 2:

direcciones[i][j]=direcciones[i][1];

break;

case 3:

direcciones[i][j+1]=direcciones[i][1];

break;

continue case ndir:

direcciones[i][j+2]=direcciones[i][1];

break;

}

printf(“Se conecta además con otra dirección?: ”);

scanf(“%s”, &eleccion);

if (eleccion==1)

{

j++

/*Regreso a la linea 53 para seguir llenando la matriz en la siguiente columna.*/

return line 53;

}

/* Esto asegura no repetir las preguntas de uniones de las direcciones.*/

j++;

}

}

printf(“Asignar las distancias entre las direcciones:”);

/*Se define otra matriz nxn para las distancias (numero float).*/

distancias[ndir+1][ndir+1];

for ((i=1; i<=ndir; i++)&&(j=2; j<=ndir; j++))

{

/*Dice que si existe algo definido en la posición [i][j] de la matriz “direcciones”, asignara el numero 1 en la matriz de “distancias” en su posición equivalente.*/

if (exists(direccion[i][j])==1)

{

distancias[i][j]=1;

}

}

for (i=1; i<=ndir; i++)

{

for (j=2; j<=ndir; j++)

{

/*Y luego dice que si existe un 1 en las posiciones de la matriz “distancias”, te pedirá ingresar la distancia.*/

if (exists(direcciones[i][j])==1)

{

printf(“Cual es la distancia %s-%s?: ”, direcciones[i][1],direcciones[i][j])

scanf(“%lf”, distancias[i][j]);

}

/* Esto (j++) es para que no se repitan las preguntas de distancias iguales pero en diferente sentido. Es decir distancia=AB=BA*/

j++

}

}

printf(“Cual es la dirección inicial?: ”)

scanf(“%s”, &inicio);

printf(“Y cual es la dirección final o de llegada?: ”)

scanf(“%s”, &fin);

/*Esta es la parte que es un poco confusa porque todavía no sabemos como hacer diagramas de árbol.*/

generate diagram (caminos[])

/*Aquí solo le decimos que nos genere k-caminos posibles a partir de la matriz de las direcciones y que vaya sumando las distancias.*/

for (k=1; k<=distancias[i][j]; k++)

{

for (j=2; j<=tam(direcciones[i][j]))

{

/*Busca direcciones adyacentes o uniones.*/

search adyacent (direcciones[])

suma= distancias[i][j]+distancias[i][j++]

}

caminos[k]=suma;

suma=0;

}

/*Tomamos el primer numero de los caminos generados y lo comparamos con todos los demás, se le asignara la variable “menor” al menor numero de cada comparación hecha. Se hace esto porque hay veces que resultan 500 caminos diferentes.*/

k=1;

menor= caminos[k];

for (k=2; k<=size(caminos[]); k++)

{

if (menor>caminos[k])

{

menor=caminos[k];

}

else if (menor=caminos[k])

{

/*Menoralt significa menor alternativo, ya que a veces puedes encontrar 2 o mas caminos con la misma distancia.*/

menoralt[i]=caminos[k];

}

}

printf(“El camino mas corto que puede tomar de %s a %s es: %-s con una distancia de: %lf”, inicio, fin, caminos[k], menor);

/*Se comparan los resultados alternativos y se ofrecen en pantalla solo si son iguales al camino mas corto (menor).*/

j= size(menoralt[]);

if (menoralt[j]=menor)

{

for (i<=j; i=1; i- -)

{

while (menor=menoralt[i])

{

printf(“Otra alternativa es: %-s con la misma distancia”, caminos[i]);

}

}

}

getch ();

}

Un ejemplo:

Este es un ejemplo del algoritmo con un mapa simple:

1. Tomemos un mapa cualquiera, en este caso será el estado de Arizona, EU.

Fuente: http://i459.photobucket.com/albums/qq317/pauljorg31/arizona/cities-map-arizona-free.gif

2. Supongamos que deseas ir de Holbrook a Blythe, solo por los caminos resaltados en azul y las ciudades subrayadas con rojo.

3. El programa comienza pidiéndote la cantidad de ciudades o direcciones que existen: 11

Blythe, Needles, Kingman, Williams, Flagstaff, Sedona, Prescott, Wickenburg, Phoenix, Globe y Holbrook.

4. Entonces se define una matriz de 11x11.

5. Llena los espacios de la primera fila como van ingresando los datos.

6. Te pregunta cuales son las conexiones o uniones de la primera dirección (Blythe), en el mapa podemos observar que son Needles, Wickenburg y Phoenix. Y el programa las inserta justo debajo de la primera ciudad:

	i=1	i=2	i=3	i=4	i=5
j=1	Blythe	Needles	Kingman	Williams	…
j=2	Needles	Blythe	…	…	…
j=3	Wickenburg	…	…	…	…
j=4	Phoenix	…	…	…	…

7. Y hace lo mismo con las demás ciudades sin repetir las preguntas.

8. Se define una matriz para las distancias pero es 1 número más grande que la cantidad total de direcciones. Es decir de 12x12.

9. Si existe algún valor sea numérico o alfabético en la matriz de direcciones, se le asigna un 1 a su homologo en la matriz de distancias. Es decir distancias[i+1][j+1].

	Blythe	Needles	Kingman	Williams
Bythe
Needles	1
Kingman		…
Phoenix	1	…	…

10. Después, si existe un 1 en la matriz anterior, se pedirá la distancia de [i][1] a [i][j].

11. Se piden la dirección inicial y la dirección final: Holbrook y Blythe.

12. Comienza a hacer el diagrama de árbol a partir de ambas matrices y asignando los resultados en un arreglo llamado caminos[k].

Aquí se puede apreciar la complejidad del mapa con todos sus caminos posibles.

13. Mas tarde de haber generado todos los caminos[k], compara las distancias obtenidas, es decir cada una de las ramas del diagrama de árbol que terminan en Blythe, nuestro objetivo.

14. Casi por ultimo se determina cual fue el menor de todas las distancias y se ofrece como resultado final. Para fines prácticos nosotros supondremos que el camino mas corto es el que tiene menos direcciones de por medio. Se puede ver en el diagrama que esos caminos son:

Holbrook > Globe > Phoenix > Blythe.

15. Ya por ultimo se ofrecen algunas alternativas:

Otra opción puede ser:

Holbrook > Flagstaff > Williams > Prescott > Wickenburg > Bythe.

La complejidad del programa es aproximadamente NP ya que el diagrama de arbol aumenta exponencialmente conforme los caminos o conecciones entre ciudades aumentan.