Mensajes

[MOD: No hacer doble post. Usar el botón modificar.]

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 (c) [Seleccionar] Expandir


/* SOLUCIÓN OPTIMA VIAJANTE DE COMERCIO SIMÉTRICO */
#include <stdio.h>
#include <stdlib.h>

#define N 8 // Numero de ciudades
#define MIN 1 // Distancia minima
#define MAX 9 // Distancia maxima
#define CIUDAD_ORIGEN 0 // Ciudad origen = A
#define SEMILLA 1024 // Semilla para repetir el experimento

#define TRUE (1 == 1)
#define FALSE (1 != 1)

char ciudades[18] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R'};

int d[N][N]; // Matriz de distancias
int visitadas[N]; // Ciudades visitadas por el algoritmo
int suma = 0; // Suma de costes
int optima = 999999; // Solucion optima inicial
int iteraciones = 0; // Numero de iteraciones
int solucion[N]; // Vector con el trayecto realizado

void matriz_distancias (void) {
srand(SEMILLA);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) {
d[i][j] = 0;
} else {
d[i][j] = (rand() % MAX) + MIN;
d[j][i] = d[i][j];
}
}
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf ("%3d", d[i][j]);
}
printf ("\n");
}
}

void busqueda_profundidad (int nivel, int origen, int suma, int visitadas[]) {
visitadas[origen] = TRUE;
solucion[nivel - 1] = origen;
iteraciones++;
for (int destino = 0; destino < N; destino++) {
if (visitadas[destino] == FALSE) {
suma = suma + d[origen][destino];
if (suma < optima) {
busqueda_profundidad(nivel + 1, destino, suma, visitadas);
}
if (nivel == (N - 1)) {
suma = suma + d[destino][CIUDAD_ORIGEN];
if (suma < optima) {
optima = suma;
printf ("Estableciendo nueva solucion optima, coste = %6d\n", optima);
printf ("Solucion = { ");
for (int i = 0; i < N; i++) {
printf (" %c, ", ciudades[ solucion[i] ]);
}
printf (" %c }\n\n", ciudades[CIUDAD_ORIGEN]);
}
} else {
suma = suma - d[origen][destino];
}
visitadas[destino] = FALSE;
}
}
}

int factorial (int n) {
int f = 1;
for (int i = n; i > 1; i--) {
f = f * i;
}
return f;
}

int main (void) {
printf ("RESOLUCION DEL PROBLEMA DEL VIAJANTE DE COMERCIO\n");
printf ("(c) Alejandro Portero Gimeno 2015\n\n");

matriz_distancias();

for (int i = 0; i < N; i++) {
visitadas[i] = FALSE;
}

printf ("\nNum. ciudades = %d\n\n", N);

busqueda_profundidad (1, CIUDAD_ORIGEN, suma, visitadas);

printf ("Iteraciones            = %12d\n", iteraciones);
printf ("Soluciones totales     = %12d\n", factorial(N-1));
printf ("Soluciones descartadas = %12d\n", factorial(N-1) - iteraciones);

system("pause");
return 0;
}



MOD: No hacer doble post. Usar el botón modificar.