Programa del agente viajero

[JoelGonzalez]

Hola, mi nombre es Joel. Soy estudiante de la carrera de ingeniería en computación y estoy aprendiendo a programar en C. Comparto este programa para que me den retroalimentación como programadores y así pueda mejorar mi algoritmo, mi estilo o lo que sea necesario para poder ser un buen programador.

Sobre lo que hace el programa cabe comentar que trata de dar solución al problema del agente viajero usando el algoritmo del vecino más cercano donde voy visitando la ciudad más cercana a la que estoy actualmente y eliminando las ciudades ya visitadas hasta llegar a la ciudad de origen.

Agradecería mucho sus opiniones y consejos.

Código (C) [Seleccionar] Expandir

/*****************************************************************************
* Programa que busca la ruta mas corta entre 5 y 20 ciudades dadas por el  
* usuario.
*
* Hecho por: Joel Gonzalez
* Fecha de elaboracion: 20 / 05 / 2014
*
*   Modificaciones: - [23 / 05 / 2014]
*                     Uso de estructuras para reducir el numero de argumentos
*                     a pasar en las funciones PedirCaminos, BuscarRutaOptima
*                     y BuscarEnFila (recomendado por eferion).
*                  
*                   - [25 / 05 / 2014]
*                     Cambio en la implementacion de la funcion PedirCaminos
*                     (recomendada por eferion).
*
*                   - [25 / 05 / 2014]
*                     Uso de las directivas de preprocesador #ifdef, #else y #endif
*                     para hacer compatible a la funcion system("cls") de Windows
*                     con Linux y Unix por medio de la funcion system("clear")
*
*                   - [25/ 05 / 2014]
*                     Uso de la cabecera stdbool.h para ocupar los valores booleanos
*                     true y false en vez de usar definiciones de preprocesador
*                     (#define) para crearlas
*
*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#ifdef _WIN32
#define LIMPIAR_PANTALLA system("cls");
#else
#define LIMPIAR_PANTALLA system("clear");
#endif

/*Definiciones de estructuras*/

typedef struct
{
int G[20][20];
int num_ciudades;
} Datos;

/*Prototipos de funciones hechas por mi*/

int  RutaOptima              (void);
void PedirCaminos            (Datos *);
void BuscarRutaOptima        (Datos *,int [20][2]);
int  BuscarEnFila            (Datos *,int, int[20][2]);
void GuardarCiudad           (int [20][2], int);
void GuardarValor            (int [20][2], int);
void QuitarCiudadesVisitadas (Datos *, int [20][2], int, bool);
void ImprimirRutaOptima      (int [20][2], int);
int  SumarTrayectorias       (int [20][2], int);
void RepetirPrograma         (void);
void Flush_in                (void); /*se explica su uso al final del codigo*/

/*Funcion principal*/

int main()
{
RutaOptima();
return 0;
}

/*Funciones hechas por mi*/

int RutaOptima(void)
{
int ruta[20][2]= {0};
Datos datos = {0,0};

do
{
LIMPIAR_PANTALLA
printf("\n\n\n\tTeclee el numero de ciudades a visitar (5 - 20): ");
scanf("%d",&datos.num_ciudades);
Flush_in();

if (datos.num_ciudades < 5 || datos.num_ciudades > 20)
{
printf("\n\n\t\t** El numero de ciudades tiene que estar entre 5 y 20 **");
getchar();
}

} while (datos.num_ciudades < 5 || datos.num_ciudades > 20);

PedirCaminos(&datos);
BuscarRutaOptima(&datos, ruta);
ImprimirRutaOptima(ruta, datos.num_ciudades);
RepetirPrograma();

return 0;
}

void PedirCaminos(Datos *datos)
{
int i, j;

LIMPIAR_PANTALLA
printf("\n\n\tA continuacion escriba la distancia en kilometros de las siguientes\n\ttrayectorias:\n\n");

for (i = 0; i < (datos -> num_ciudades); i++)
{
   datos -> G[i][i] = 0;

   for (j = i + 1; j < (datos -> num_ciudades); j++)
   {
    printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
    scanf("%d",&datos -> G[i][j]);
    Flush_in();

    datos -> G[j][i] = datos -> G[i][j];
   }
   }
}

void BuscarRutaOptima(Datos *datos, int r[20][2])
{
int i, inicio, indice_del_menor;

do
{
LIMPIAR_PANTALLA
printf("\n\n\n\t\tCon cual ciudad desea comenzar su ruta: ");
scanf("%d", &inicio);
Flush_in();

if (inicio < 1 || inicio > (datos -> num_ciudades))
{
printf("\n\t\t** La ciudad debe estar entre 1 y %d **", datos -> num_ciudades);
getchar();
}
}while(inicio < 1 || inicio > (datos -> num_ciudades));

r[0][0] = inicio;

inicio--;

for (i = 0; i < (datos -> num_ciudades); i++)
{
if(i == 0)
{
indice_del_menor = BuscarEnFila(datos, inicio, r);
QuitarCiudadesVisitadas(datos, r, indice_del_menor, false);
}
else
{
if (i == (datos -> num_ciudades) - 2)
{
indice_del_menor = BuscarEnFila(datos, indice_del_menor, r);
QuitarCiudadesVisitadas(datos, r, indice_del_menor, true);
}
else
{
indice_del_menor = BuscarEnFila(datos, indice_del_menor, r);
QuitarCiudadesVisitadas(datos, r, indice_del_menor, false);
}
}
}
}

int BuscarEnFila(Datos *datos, int inicio, int r[20][2])
{
int j, menor = 999999, indice_del_menor;

for (j = 0; j < (datos -> num_ciudades); j++)
{
if ( (datos -> G[inicio][j]) != 0 )
{
if ( (datos -> G[inicio][j]) < menor )
{
menor = datos -> G[inicio][j];
indice_del_menor = j;
}
}
}

GuardarCiudad(r ,indice_del_menor);
GuardarValor(r, menor);

return indice_del_menor;
}

void GuardarCiudad(int r[20][2] , int indice_del_menor)
{
int i, num_ciudades_visitadas;

i= 0;
num_ciudades_visitadas = 0;

while(r[i][0] != 0)
{
i++;
num_ciudades_visitadas++;
}

r[num_ciudades_visitadas][0] = indice_del_menor + 1;
}

void GuardarValor(int r[20][2], int menor)
{
int i, num_ciudades_visitadas;

i=0;
num_ciudades_visitadas = 0;

while(r[i][1] != 0)
{
i++;
num_ciudades_visitadas ++;
}

r[num_ciudades_visitadas][1] = menor;
}

void QuitarCiudadesVisitadas(Datos *datos, int r[20][2], int indice_del_menor, bool penultimo)
{
int i, num_ciudades_visitadas, aux;

i = 0;
num_ciudades_visitadas = 0;

while(r[i][1] != 0)
{
i++;
num_ciudades_visitadas++;
}

if (penultimo == true)
{
for (i = num_ciudades_visitadas; i >= 1; i--)
{
aux = r[i][0];
aux = aux - 1;
datos -> G[indice_del_menor][aux] = 0;
}
}
else
{
for (i = num_ciudades_visitadas; i >= 0; i--)
{
aux = r[i][0];
aux = aux - 1;
datos -> G[indice_del_menor][aux] = 0;
}
}
}

void ImprimirRutaOptima(int ruta[20][2], int n)
{
int i, total;

total = SumarTrayectorias(ruta, n);

printf("\n\n\tUna ruta optima seria: ");

for (i = 0; i < n + 1; i++)
{
if (i == n)

printf(" %d\n", ruta[i][0]);

else

printf(" %d ->", ruta[i][0]);
}

printf("\n\n\tTotal de kilometros recorridos:");

for (i = 0; i < n; i++)
{
if (i == n-1)

printf(" %d = %d\n\n", ruta[i][1],total);

else

printf(" %d +", ruta[i][1]);
}

getchar();
}

int SumarTrayectorias(int r[20][2], int n)
{
int i, total=0;

for (i = 0; i < n; i++)

total += r[i][1];

return total;
}

void RepetirPrograma(void){
int opcion;

do
{
LIMPIAR_PANTALLA
printf("\n\n\t\tDesea repetir de nuevo el programa\n\n\t 1.Si\n\n\t 2.No");
printf("\n\n\n\tElegir opcion: ");
scanf("%d", &opcion);
Flush_in();

switch(opcion)
{
case 1:
RutaOptima();
break;

case 2:
LIMPIAR_PANTALLA
break;

default:
printf("\n\n\tOpcion no valida");
getchar();
break;
}
} while (opcion < 1 || opcion > 2);
}


/* La funcion Flush_in sustituye a la funcion fflush(stdin) ya que aquella
*  no funciona correctamente en linux y lo que hace es limpiar el buffer
*  del teclado. La funcion Flush_in la uso especificamente para limpiar la
*  basura que contiene el buffer del teclado al usar la funciones como scanf
*/

void Flush_in (void)
{
char caracter;

while((caracter = fgetc(stdin)) != EOF && caracter != '\n');
}


[eferion]

Buenas Joel. Bienvenido al foro.

Si te das cuenta, en todas las funciones tienes que pasar tanto la matriz como el número de ciudades, puedes ahorrarte la molestia empaquetando ambas variables en una estructura:

Código (c) [Seleccionar] Expandir


typedef struct
{
  int Grafo[20][20];
  int NumCiudades;
} Datos;

Y algo parecido para el vector de rutas.

De esta forma los dos datos van a viajar siempre juntos y reducirás el número de argumentos de las funciones ( que siempre es de agradecer ). Además también se mejora la legibilidad del programa porque desde un primer momento se sabe que esas dos variables van de la mano.

Código (c) [Seleccionar] Expandir


  for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
      if (i == j)

        G[i][j] = 0;

      if (i < j)
      {

          printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
          scanf("%d",&G[i][j]);
          Flush_in();

        G[j][i] = G[i][j];
      }
    }
  }

Este bucle tiene margen de mejora... si i < j es requisito, puedes evitar la comparación con un par de cambios

Código (c) [Seleccionar] Expandir


  for (i = 0; i < n; i++)
  {
    for (j = 0; j <= i; j++) // Se reduce el rango de j
    {
      if (i == j)
        G[i][j] = 0;
      else // Desaparece el if
      {

          printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
          scanf("%d",&G[i][j]);
          Flush_in();

        G[j][i] = G[i][j];
      }
    }
  }


O incluso...

Código (c) [Seleccionar] Expandir


  for (i = 0; i < n; i++)
  {
    G[i][i] = 0;

    for (j = 0; j < i; j++)
    {
      printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
      scanf("%d",&G[i][j]);
      Flush_in();
      G[j][i] = G[i][j];
    }
  }

Por lo demás, a simple vista no veo nada raro.

Como posibles mejoras yo propondría las siguientes:

* permitir elegir entre diferentes algoritmos de enrutado.
* posibilidad de que las rutas de ida no tengan el mismo valor que las de vuelta.
* rutas de un solo sentido ( va de la mano con la propuesta anterior )

Y no se, si se me ocurre algo más actualizaré el mensaje

Un saludo.

[JoelGonzalez]

Antes que nada muchas gracias por tus consejos.

He reposteando el código con la estructura y no se si he complicado su lectura por las operaciones . y -> que debo de usar para su acceso, aunque aclaro que apenas aprendí a usarlas, por lo que agradecería si me dieras tu opinión sobre el cómo manipule la estructura.

Sobre el cambio en la implementación de la función PedirCaminos tengo algunas inquietudes porque a simple vista hacen lo mismo pero en la ejecución del programa difieren

Por ejemplo, usando la implementación que tengo me pide las trayectorias para 5 ciudades de la siguente manera:

Código [Seleccionar] Expandir


 
 Ciudad 1 -> Ciudad 2:
 Ciudad 1 -> Ciudad 3:
 Ciudad 1 -> Ciudad 4:
 Ciudad 1 -> Ciudad 5:
 Ciudad 2 -> Ciudad 3:
 Ciudad 2 -> Ciudad 4:
 Ciudad 2 -> Ciudad 5:
 Ciudad 3 -> Ciudad 4:
 Ciudad 3 -> Ciudad 5:
 Ciudad 4 -> Ciudad 5:



Mientras que usando la implemententación recomendada:

Código [Seleccionar] Expandir


 
 Ciudad 2 -> Ciudad 1:
 Ciudad 3 -> Ciudad 1:
 Ciudad 3 -> Ciudad 2:
 Ciudad 4 -> Ciudad 1:
 Ciudad 4 -> Ciudad 2:
 Ciudad 4 -> Ciudad 3:
 Ciudad 5 -> Ciudad 1:
 Ciudad 5 -> Ciudad 2:
 Ciudad 5 -> Ciudad 3:
 Ciudad 5 -> Ciudad 4:



Desde mi punto de vista es más cómodo meter los datos en primera forma aunque en el código tenga que usar un if de más. Pero muchas gracias por mostrarme otra forma de implemetar esa función.

Con respecto a dar opciones para diferentes algoritmos de erutado lamento decir que este es el único que pude entender e implementar (no soy muy bueno en esto) aunque espero entender e implementar otros más adelante e incluirlos.

Y sobre lo demás no entiendo muy bien aquello de que haya posibilidad de que las rutas no tengan el mismo valor de ida que de vuelta y tampoco sobre que las rutas tengan un mismo sentido aunque tengo la sensación de que son muy interesante esas propuestas.

[eferion]

He reposteando el código con la estructura y no se si he complicado su lectura por las operaciones . y -> que debo de usar para su acceso, aunque aclaro que apenas aprendí a usarlas, por lo que agradecería si me dieras tu opinión sobre el cómo manipule la estructura.

Las estructuras solo admiten dos tipos de accesos:

* por valor, usando el operador '.'
* por referencia, mediante el operador '->'

El operador por referencia se usa cuando accedes a la estructura a través de un puntero, si no hay puntero se usa el operador por valor.

La ventaja de usar estructuras es que permite agrupar variables que son dependientes, lo cual simplifica las llamadas a funciones y el diseño general de la aplicación. La pega es que, al estar las variables metidas en paquetes, es necesario añadir el acceso a la estructura a cada uso que hagamos de una de sus variables.

Una ventaja que también tienen las estructuras es que pueden copiarse unas a otras usando el operador igual '=', cosa que no sucede con los punteros, por ejemplo:

Código (c) [Seleccionar] Expandir


typedef struct
{
  int a;
  float b;
} datos;

int main( )
{
  datos grupo1, grupo2;

  grupo1.a = 25;
  grupo1.b = 84.59;

  grupo2 = grupo1;

  printf( "%d %f\n", grupo2.a, grupo2.b );
}

Para copiar el contenido de los punteros tendrás que hacerlo a mano... los punteros son punteros... es lo que tiene usar un lenguaje que te da tanto control sobre la memoria.

Sobre el cambio en la implementación de la función PedirCaminos tengo algunas inquietudes porque a simple vista hacen lo mismo pero en la ejecución del programa difieren

La forma de crear la matriz de nodos es irrelevante en este caso.

Puedes crearlas en el orden que tu dices simplemente cambiando un poco los bucles:

Código (cpp) [Seleccionar] Expandir


for (i = 0; i < n; i++)
{
  G[i][i] = 0;

  for (j = i+1; j < n; j++)
  {
    printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
    scanf("%d",&G[i][j]);
    Flush_in();
    G[j][i] = G[i][j];
  }
}

Y sobre lo demás no entiendo muy bien aquello de que haya posibilidad de que las rutas no tengan el mismo valor de ida que de vuelta

Cuando te mueves en coche, te habrás dado cuenta de que hay situaciones en las que los dos sentidos de circulación de una misma carretera dejan de ir paralelos el uno al otro ( accidentes geográficos, otras estructuras anteriores, ... ). Esto hace que, en la vida real, la distancia A-B no sea la misma que la distancia B-A... y en ocasiones la diferencia no es despreciable.

En tu algoritmo, en la entrada de datos estás haciendo:

Código (c) [Seleccionar] Expandir


for (i = 0; i < (datos -> num_ciudades); i++ )
{
  for (j = 0; j < (datos -> num_ciudades); j++)
  {
    // ...
   datos -> G[j][i] = datos -> G[i][j];
  }
}

Es decir, estás asumiendo que la distancia A-B es igual a la distancia B-A. Si permites que estos valores sean diferentes podrás adaptar tu código a situaciones reales ( carreteras, internet, ... )

y tampoco sobre que las rutas tengan un mismo sentido aunque tengo la sensación de que son muy interesante esas propuestas.

¿No te has encontrado nunca una carretera de sentido único? ¿Y si esa carretera resulta que une dos ciudades? en ese caso, existirá la conexión A-B pero no la conexión B-A, lo mismo para ir de B a A tienes que hacer B-C-A eso es algo que te puedes encontrar estudiando casos reales.

Y para terminar, una propuesta más, da la posibilidad de guardar las rutas en un fichero y leerlo después, claro... los casos reales suelen tener más de 20 ciudades y puede ser un auténtico tormento tener que introducir a mano una matriz de, por ejemplo 1000 x 1000 elementos jejejeje

Una vez tengas esto terminado, bien diseñado y estructurado te puedes plantear añadir nuevas variables a tu sistema, como por ejemplo la velocidad máxima de cada enlace o el consumo medio de combustible necesario para recorrer esa ruta. El caso es que así puedes establecer diferentes criterios a la hora de buscar la ruta óptima:

* Quiero ver la ruta más rápida (menor tiempo total para hacer el camino A-B )
* Quiero ver la ruta más corta  (menor distancia)
* Quiero ver la ruta más económica (menor consumo)
...

Si te das cuenta, los GPS funcionan más o menos así.

Un saludo.