elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el Twitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Programa del agente viajero
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Programa del agente viajero  (Leído 15,360 veces)
JoelGonzalez

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Programa del agente viajero
« en: 23 Mayo 2014, 11:24 am »

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
  1. /*****************************************************************************
  2. * Programa que busca la ruta mas corta entre 5 y 20 ciudades dadas por el  
  3. * usuario.
  4. *
  5. * Hecho por: Joel Gonzalez
  6. * Fecha de elaboracion: 20 / 05 / 2014
  7. *
  8. *   Modificaciones: - [23 / 05 / 2014]
  9. *                     Uso de estructuras para reducir el numero de argumentos
  10. *                     a pasar en las funciones PedirCaminos, BuscarRutaOptima
  11. *                     y BuscarEnFila (recomendado por eferion).
  12. *                  
  13. *                   - [25 / 05 / 2014]
  14. *                     Cambio en la implementacion de la funcion PedirCaminos
  15. *                     (recomendada por eferion).
  16. *
  17. *                   - [25 / 05 / 2014]
  18. *                     Uso de las directivas de preprocesador #ifdef, #else y #endif
  19. *                     para hacer compatible a la funcion system("cls") de Windows
  20. *                     con Linux y Unix por medio de la funcion system("clear")
  21. *
  22. *                   - [25/ 05 / 2014]
  23. *                     Uso de la cabecera stdbool.h para ocupar los valores booleanos
  24. *                     true y false en vez de usar definiciones de preprocesador
  25. *                     (#define) para crearlas
  26. *
  27. *****************************************************************************/
  28.  
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <stdbool.h>
  32.  
  33. #ifdef _WIN32
  34. #define LIMPIAR_PANTALLA system("cls");
  35. #else
  36. #define LIMPIAR_PANTALLA system("clear");
  37. #endif
  38.  
  39. /*Definiciones de estructuras*/
  40.  
  41. typedef struct
  42. {
  43. int G[20][20];
  44. int num_ciudades;
  45. } Datos;
  46.  
  47. /*Prototipos de funciones hechas por mi*/
  48.  
  49. int  RutaOptima              (void);
  50. void PedirCaminos            (Datos *);
  51. void BuscarRutaOptima        (Datos *,int [20][2]);
  52. int  BuscarEnFila            (Datos *,int, int[20][2]);
  53. void GuardarCiudad           (int [20][2], int);
  54. void GuardarValor            (int [20][2], int);
  55. void QuitarCiudadesVisitadas (Datos *, int [20][2], int, bool);
  56. void ImprimirRutaOptima      (int [20][2], int);
  57. int  SumarTrayectorias       (int [20][2], int);
  58. void RepetirPrograma         (void);
  59. void Flush_in                (void); /*se explica su uso al final del codigo*/
  60.  
  61. /*Funcion principal*/
  62.  
  63. int main()
  64. {
  65. RutaOptima();
  66. return 0;
  67. }
  68.  
  69. /*Funciones hechas por mi*/
  70.  
  71. int RutaOptima(void)
  72. {
  73. int ruta[20][2]= {0};
  74. Datos datos = {0,0};
  75.  
  76. do
  77. {
  78. LIMPIAR_PANTALLA
  79. printf("\n\n\n\tTeclee el numero de ciudades a visitar (5 - 20): ");
  80. scanf("%d",&datos.num_ciudades);
  81. Flush_in();
  82.  
  83. if (datos.num_ciudades < 5 || datos.num_ciudades > 20)
  84. {
  85. printf("\n\n\t\t** El numero de ciudades tiene que estar entre 5 y 20 **");
  86. }
  87.  
  88. } while (datos.num_ciudades < 5 || datos.num_ciudades > 20);
  89.  
  90. PedirCaminos(&datos);
  91. BuscarRutaOptima(&datos, ruta);
  92. ImprimirRutaOptima(ruta, datos.num_ciudades);
  93. RepetirPrograma();
  94.  
  95. return 0;
  96. }
  97.  
  98. void PedirCaminos(Datos *datos)
  99. {
  100. int i, j;
  101.  
  102. LIMPIAR_PANTALLA
  103. printf("\n\n\tA continuacion escriba la distancia en kilometros de las siguientes\n\ttrayectorias:\n\n");
  104.  
  105. for (i = 0; i < (datos -> num_ciudades); i++)
  106. {
  107.    datos -> G[i][i] = 0;
  108.  
  109.    for (j = i + 1; j < (datos -> num_ciudades); j++)
  110.    {
  111.     printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
  112.     scanf("%d",&datos -> G[i][j]);
  113.     Flush_in();
  114.  
  115.     datos -> G[j][i] = datos -> G[i][j];
  116.    }
  117.    }
  118. }
  119.  
  120. void BuscarRutaOptima(Datos *datos, int r[20][2])
  121. {
  122. int i, inicio, indice_del_menor;
  123.  
  124. do
  125. {
  126. LIMPIAR_PANTALLA
  127. printf("\n\n\n\t\tCon cual ciudad desea comenzar su ruta: ");
  128. scanf("%d", &inicio);
  129. Flush_in();
  130.  
  131. if (inicio < 1 || inicio > (datos -> num_ciudades))
  132. {
  133. printf("\n\t\t** La ciudad debe estar entre 1 y %d **", datos -> num_ciudades);
  134. }
  135. }while(inicio < 1 || inicio > (datos -> num_ciudades));
  136.  
  137. r[0][0] = inicio;
  138.  
  139. inicio--;
  140.  
  141. for (i = 0; i < (datos -> num_ciudades); i++)
  142. {
  143. if(i == 0)
  144. {
  145. indice_del_menor = BuscarEnFila(datos, inicio, r);
  146. QuitarCiudadesVisitadas(datos, r, indice_del_menor, false);
  147. }
  148. else
  149. {
  150. if (i == (datos -> num_ciudades) - 2)
  151. {
  152. indice_del_menor = BuscarEnFila(datos, indice_del_menor, r);
  153. QuitarCiudadesVisitadas(datos, r, indice_del_menor, true);
  154. }
  155. else
  156. {
  157. indice_del_menor = BuscarEnFila(datos, indice_del_menor, r);
  158. QuitarCiudadesVisitadas(datos, r, indice_del_menor, false);
  159. }
  160. }
  161. }
  162. }
  163.  
  164. int BuscarEnFila(Datos *datos, int inicio, int r[20][2])
  165. {
  166. int j, menor = 999999, indice_del_menor;
  167.  
  168. for (j = 0; j < (datos -> num_ciudades); j++)
  169. {
  170. if ( (datos -> G[inicio][j]) != 0 )
  171. {
  172. if ( (datos -> G[inicio][j]) < menor )
  173. {
  174. menor = datos -> G[inicio][j];
  175. indice_del_menor = j;
  176. }
  177. }
  178. }
  179.  
  180. GuardarCiudad(r ,indice_del_menor);
  181. GuardarValor(r, menor);
  182.  
  183. return indice_del_menor;
  184. }
  185.  
  186. void GuardarCiudad(int r[20][2] , int indice_del_menor)
  187. {
  188. int i, num_ciudades_visitadas;
  189.  
  190. i= 0;
  191. num_ciudades_visitadas = 0;
  192.  
  193. while(r[i][0] != 0)
  194. {
  195. i++;
  196. num_ciudades_visitadas++;
  197. }
  198.  
  199. r[num_ciudades_visitadas][0] = indice_del_menor + 1;
  200. }
  201.  
  202. void GuardarValor(int r[20][2], int menor)
  203. {
  204. int i, num_ciudades_visitadas;
  205.  
  206. i=0;
  207. num_ciudades_visitadas = 0;
  208.  
  209. while(r[i][1] != 0)
  210. {
  211. i++;
  212. num_ciudades_visitadas ++;
  213. }
  214.  
  215. r[num_ciudades_visitadas][1] = menor;
  216. }
  217.  
  218. void QuitarCiudadesVisitadas(Datos *datos, int r[20][2], int indice_del_menor, bool penultimo)
  219. {
  220. int i, num_ciudades_visitadas, aux;
  221.  
  222. i = 0;
  223. num_ciudades_visitadas = 0;
  224.  
  225. while(r[i][1] != 0)
  226. {
  227. i++;
  228. num_ciudades_visitadas++;
  229. }
  230.  
  231. if (penultimo == true)
  232. {
  233. for (i = num_ciudades_visitadas; i >= 1; i--)
  234. {
  235. aux = r[i][0];
  236. aux = aux - 1;
  237. datos -> G[indice_del_menor][aux] = 0;
  238. }
  239. }
  240. else
  241. {
  242. for (i = num_ciudades_visitadas; i >= 0; i--)
  243. {
  244. aux = r[i][0];
  245. aux = aux - 1;
  246. datos -> G[indice_del_menor][aux] = 0;
  247. }
  248. }
  249. }
  250.  
  251. void ImprimirRutaOptima(int ruta[20][2], int n)
  252. {
  253. int i, total;
  254.  
  255. total = SumarTrayectorias(ruta, n);
  256.  
  257. printf("\n\n\tUna ruta optima seria: ");
  258.  
  259. for (i = 0; i < n + 1; i++)
  260. {
  261. if (i == n)
  262.  
  263. printf(" %d\n", ruta[i][0]);
  264.  
  265. else
  266.  
  267. printf(" %d ->", ruta[i][0]);
  268. }
  269.  
  270. printf("\n\n\tTotal de kilometros recorridos:");
  271.  
  272. for (i = 0; i < n; i++)
  273. {
  274. if (i == n-1)
  275.  
  276. printf(" %d = %d\n\n", ruta[i][1],total);
  277.  
  278. else
  279.  
  280. printf(" %d +", ruta[i][1]);
  281. }
  282.  
  283. }
  284.  
  285. int SumarTrayectorias(int r[20][2], int n)
  286. {
  287. int i, total=0;
  288.  
  289. for (i = 0; i < n; i++)
  290.  
  291. total += r[i][1];
  292.  
  293. return total;
  294. }
  295.  
  296. void RepetirPrograma(void){
  297. int opcion;
  298.  
  299. do
  300. {
  301. LIMPIAR_PANTALLA
  302. printf("\n\n\t\tDesea repetir de nuevo el programa\n\n\t 1.Si\n\n\t 2.No");
  303. printf("\n\n\n\tElegir opcion: ");
  304. scanf("%d", &opcion);
  305. Flush_in();
  306.  
  307. switch(opcion)
  308. {
  309. case 1:
  310. RutaOptima();
  311. break;
  312.  
  313. case 2:
  314. LIMPIAR_PANTALLA
  315. break;
  316.  
  317. default:
  318. printf("\n\n\tOpcion no valida");
  319. break;
  320. }
  321. } while (opcion < 1 || opcion > 2);
  322. }
  323.  
  324.  
  325. /* La funcion Flush_in sustituye a la funcion fflush(stdin) ya que aquella
  326.  *  no funciona correctamente en linux y lo que hace es limpiar el buffer
  327.  *  del teclado. La funcion Flush_in la uso especificamente para limpiar la
  328.  *  basura que contiene el buffer del teclado al usar la funciones como scanf
  329.  */
  330.  
  331. void Flush_in (void)
  332. {
  333. char caracter;
  334.  
  335. while((caracter = fgetc(stdin)) != EOF && caracter != '\n');
  336. }
  337.  


« Última modificación: 26 Mayo 2014, 00:55 am por JoelGonzalez » En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Programa del agente viajero
« Respuesta #1 en: 23 Mayo 2014, 11:46 am »

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
  1. typedef struct
  2. {
  3.  int Grafo[20][20];
  4.  int NumCiudades;
  5. } 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
  1.  for (i = 0; i < n; i++)
  2.  {
  3.    for (j = 0; j < n; j++)
  4.    {
  5.      if (i == j)
  6.  
  7.        G[i][j] = 0;
  8.  
  9.      if (i < j)
  10.      {
  11.  
  12.          printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
  13.          scanf("%d",&G[i][j]);
  14.          Flush_in();
  15.  
  16.        G[j][i] = G[i][j];
  17.      }
  18.    }
  19.  }

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

Código
  1.  for (i = 0; i < n; i++)
  2.  {
  3.    for (j = 0; j <= i; j++) // Se reduce el rango de j
  4.    {
  5.      if (i == j)
  6.        G[i][j] = 0;
  7.      else // Desaparece el if
  8.      {
  9.  
  10.          printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
  11.          scanf("%d",&G[i][j]);
  12.          Flush_in();
  13.  
  14.        G[j][i] = G[i][j];
  15.      }
  16.    }
  17.  }
  18.  

O incluso...

Código
  1.  for (i = 0; i < n; i++)
  2.  {
  3.    G[i][i] = 0;
  4.  
  5.    for (j = 0; j < i; j++)
  6.    {
  7.      printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
  8.      scanf("%d",&G[i][j]);
  9.      Flush_in();
  10.      G[j][i] = G[i][j];
  11.    }
  12.  }

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.


En línea

JoelGonzalez

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Programa del agente viajero
« Respuesta #2 en: 24 Mayo 2014, 04:36 am »

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:
  
  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:
  
  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.
« Última modificación: 24 Mayo 2014, 05:19 am por JoelGonzalez » En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Programa del agente viajero
« Respuesta #3 en: 24 Mayo 2014, 09:58 am »

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
  1. typedef struct
  2. {
  3.  int a;
  4.  float b;
  5. } datos;
  6.  
  7. int main( )
  8. {
  9.  datos grupo1, grupo2;
  10.  
  11.  grupo1.a = 25;
  12.  grupo1.b = 84.59;
  13.  
  14.  grupo2 = grupo1;
  15.  
  16.  printf( "%d %f\n", grupo2.a, grupo2.b );
  17. }

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
  1. for (i = 0; i < n; i++)
  2. {
  3.  G[i][i] = 0;
  4.  
  5.  for (j = i+1; j < n; j++)
  6.  {
  7.    printf("\n\tCiudad %d --> Ciudad %d : ", i+1, j+1);
  8.    scanf("%d",&G[i][j]);
  9.    Flush_in();
  10.    G[j][i] = G[i][j];
  11.  }
  12. }

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
  1. for (i = 0; i < (datos -> num_ciudades); i++ )
  2. {
  3.  for (j = 0; j < (datos -> num_ciudades); j++)
  4.  {
  5.    // ...
  6.   datos -> G[j][i] = datos -> G[i][j];
  7.  }
  8. }

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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Intel explica el síndrome del viajero tecnológico
Noticias
wolfbcn 0 1,460 Último mensaje 2 Agosto 2012, 18:30 pm
por wolfbcn
El increíble caso de John Titor - viajero en el tiempo
Foro Libre
Graphixx 9 3,561 Último mensaje 21 Mayo 2014, 21:24 pm
por engel lex
Reconstruirán robot viajero que fue vandalizado en EEUU
Noticias
wolfbcn 0 1,286 Último mensaje 3 Agosto 2015, 21:40 pm
por wolfbcn
agente viajero python itertols
Scripting
asdexiva 1 3,689 Último mensaje 12 Octubre 2015, 07:20 am
por tincopasan
10 aplicaciones para un viajero sin wifi
Noticias
wolfbcn 0 1,614 Último mensaje 29 Junio 2016, 15:00 pm
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines