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

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


  Mostrar Mensajes
Páginas: [1]
1  Programación / Programación C/C++ / Re: Viajante comercio en: 13 Noviembre 2016, 18:30 pm
Hola, publique el algoritmo del viajante de comercio en c en mi blog. Puedo afirmar que funciona para matrices simétricas puesto que resuelve un problema del viajante de comercio simétrico donde el coste entre A y B es igual que el de entre B y A.

Por favor, cuando copiéis código de un blog, quitarle por lo menos el copyright o el autor quedará mal si lo habéis modificado... para intentarlo hacer no simétrico.
Saludos, comunidad informática.

Código
  1. /* SOLUCIÓN OPTIMA VIAJANTE DE COMERCIO SIMÉTRICO */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define N 8 // Numero de ciudades
  6. #define MIN 1 // Distancia minima
  7. #define MAX 9 // Distancia maxima
  8. #define CIUDAD_ORIGEN 0 // Ciudad origen = A
  9. #define SEMILLA 1024 // Semilla para repetir el experimento
  10.  
  11. #define TRUE (1 == 1)
  12. #define FALSE (1 != 1)
  13.  
  14. char ciudades[18] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R'};
  15.  
  16. int d[N][N]; // Matriz de distancias
  17. int visitadas[N]; // Ciudades visitadas por el algoritmo
  18. int suma = 0; // Suma de costes
  19. int optima = 999999; // Solucion optima inicial
  20. int iteraciones = 0; // Numero de iteraciones
  21. int solucion[N]; // Vector con el trayecto realizado
  22.  
  23. void matriz_distancias (void) {
  24. srand(SEMILLA);
  25. for (int i = 0; i < N; i++) {
  26. for (int j = 0; j < N; j++) {
  27. if (i == j) {
  28. d[i][j] = 0;
  29. } else {
  30. d[i][j] = (rand() % MAX) + MIN;
  31. d[j][i] = d[i][j];
  32. }
  33. }
  34. }
  35.  
  36. for (int i = 0; i < N; i++) {
  37. for (int j = 0; j < N; j++) {
  38. printf ("%3d", d[i][j]);
  39. }
  40. printf ("\n");
  41. }
  42. }
  43.  
  44. void busqueda_profundidad (int nivel, int origen, int suma, int visitadas[]) {
  45. visitadas[origen] = TRUE;
  46. solucion[nivel - 1] = origen;
  47. iteraciones++;
  48. for (int destino = 0; destino < N; destino++) {
  49. if (visitadas[destino] == FALSE) {
  50. suma = suma + d[origen][destino];
  51. if (suma < optima) {
  52. busqueda_profundidad(nivel + 1, destino, suma, visitadas);
  53. }
  54. if (nivel == (N - 1)) {
  55. suma = suma + d[destino][CIUDAD_ORIGEN];
  56. if (suma < optima) {
  57. optima = suma;
  58. printf ("Estableciendo nueva solucion optima, coste = %6d\n", optima);
  59. printf ("Solucion = { ");
  60. for (int i = 0; i < N; i++) {
  61. printf (" %c, ", ciudades[ solucion[i] ]);
  62. }
  63. printf (" %c }\n\n", ciudades[CIUDAD_ORIGEN]);
  64. }
  65. } else {
  66. suma = suma - d[origen][destino];
  67. }
  68. visitadas[destino] = FALSE;
  69. }
  70. }
  71. }
  72.  
  73. int factorial (int n) {
  74. int f = 1;
  75. for (int i = n; i > 1; i--) {
  76. f = f * i;
  77. }
  78. return f;
  79. }
  80.  
  81. int main (void) {
  82. printf ("RESOLUCION DEL PROBLEMA DEL VIAJANTE DE COMERCIO\n");
  83. printf ("(c) Alejandro Portero Gimeno 2015\n\n");
  84.  
  85. matriz_distancias();
  86.  
  87. for (int i = 0; i < N; i++) {
  88. visitadas[i] = FALSE;
  89. }
  90.  
  91. printf ("\nNum. ciudades = %d\n\n", N);
  92.  
  93. busqueda_profundidad (1, CIUDAD_ORIGEN, suma, visitadas);
  94.  
  95. printf ("Iteraciones            = %12d\n", iteraciones);
  96. printf ("Soluciones totales     = %12d\n", factorial(N-1));
  97. printf ("Soluciones descartadas = %12d\n", factorial(N-1) - iteraciones);
  98.  
  99. system("pause");
  100. return 0;
  101. }
  102.  
  103.  

MOD: No hacer doble post. Usar el botón modificar.
Páginas: [1]
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines