Viajante comercio

[Dato Vagabundo]

Lo esencial del problema. Segun la matriz que he introducido, deberia calcular el minimo de la primera fila, excluyendo siempre el cero, seleccionar el 0,2 que es el minimo y borrar las columnas de ambos numeros. Luego iria a la fila 2, buscaria el minimo que esta en el 2,3 y borraria de nuevo columnas. El problema es que a partir de ahi no avanza y entra en bucle cuando deberia seguir con 3,1 y acabar.

Código (c) [Seleccionar] Expandir

int matriz[n][n];
int minimo;
list <int> vertice;//Subconjunto solución

/*--------------------------------------------------*/
// Rellenamos matriz a ceros

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
              matriz[i][j] = 0;
    }
}

matriz[0][1]=5;
matriz[0][2]=2;
matriz[0][3]=3;
matriz[1][0]=5;
matriz[1][2]=4;
matriz[1][3]=5;
matriz[2][0]=2;
matriz[2][1]=4;
matriz[2][3]=1;
matriz[3][0]=3;
matriz[3][1]=5;
matriz[3][2]=1;

bool aumento;
int contador;
int contador2;
int val1,val2;

for(int i=0; i<n; i=val2){
    aumento = true;
    contador2 = 0;
    for(int j=0; j<n; j++){

        if (aumento){
            contador = 0;

            while (matriz[i][contador]==0){
                contador++;
            }

            minimo = matriz[i][contador];
            //cout << "\nMINIMO INICIAL EN FILA " << i << " : " << minimo << endl;
            aumento = false;
        }
       
        contador2++;
        if(matriz[i][j]!=0){
            if(matriz[i][j] < minimo){
                minimo = matriz[i][j];
                val1 = i;
                val2 = j;
                //cout << "MINIMO DE LA FILA " << i << ": " << minimo << endl;
                cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
               
            }
        }
        //cout << "CONTADOR2 : " << contador2 << endl;
   
        if (contador2 == n){

            vertice.push_back(val1);
                vertice.push_back(val2);

             for(int j=0; j<n; j++){

                          matriz[j][val1]=0;
                          matriz[j][val2]=0;
            }

            // cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
        }
    }
}

MOD EDIT: Etiquetas GeSHi.

[.rn3w.]

disculpa y tu pregunta?

[JonaLamper]

Lo que ocurre es que el Viajante de comercio no se resuelve así. Es una buena idea (e incluso podría parecer óptima) el ir cogiendo los caminos mínimos desde un punto inicial hasta que vuelves otra vez al punto de partida, pero como he dicho, esa no es la forma de resolver el Viajante de comercio (te podría poner un ejemplo muy fácil donde tu algoritmo no es óptimo).

En el problema del viajante actualmente sólo puede resolverse de una forma: explorando todos los caminos posibles y quedándote con la ruta mínima. Lo cual supone un tiempo exponencial (que es muchísimo) y por eso el problema del viajante pertenece a la clase de complejidad NP.

Lo que tú estás intentando hacer se llama algoritmo de Dijkstra.


Posdata: no he visto el código, sólo he leído lo que has dicho. Por cierto, intenta usar las etiquetas de código porque no se entiende nada.

[Dato Vagabundo]

He encontrado este codigo por internet pero no se porque no me hace bien los caminos,
soy principiante no me juzgueis  

Código (c) [Seleccionar] Expandir

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

#define N 4 // Numero de ciudades
#define CIUDAD_ORIGEN 0


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

char ciudades[4] = {'0', '1', '2', '3'};

int d[4][4]={{0,20,40,60},
    {30,0,50,25},
            {20,25,0,50,},
            {20,30,0,0}}; // 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 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));
printf ("Soluciones descartadas = %12d\n", factorial(N) - iteraciones);

system("pause");
return 0;
}


MOD EDIT: Etiquqtas GeSHi (por 2da vez).

[JonaLamper]

No sirve de mucho coger código por Internet, menos aún si estás aprendiendo y no sabes un concepto un poco avanzado como un DFS Depth First Search (búsqueda en profundidad). Yo te recomiendo que intentes hacer esto: debes establecer un punto de origen. En tu primer ejemplo había 4 pueblos (pueblo 0, pueblo 1, pueblo 2 y pueblo 3), vamos a suponer que queremos resolver el problema del viajante desde el pueblo 0 (o sea, partimos desde matriz[0][0]). De lo que se trata es de explorar todos los caminos y de VOLVER otra vez al origen (o sea, al pueblo 0). Con lo cual, vamos a tener que hacer las siguientes rutas:

Ruta 1: 0, 1, 2, 3, 0.
Ruta 2: 0, 1, 3, 2, 0.
Ruta 3: 0, 2, 1, 3, 0.
Ruta 4: 0, 2, 3, 1, 0.
Ruta 5: 0, 3, 2, 1, 0.
Ruta 6: 0, 3, 1, 2, 0.

Los números obviamente representan el pueblo al que vamos. Ahora bien, en tu matriz tenías: matriz[0][1] = 5, es decir, hay 5 km (por ejemplo) desde el pueblo 0 al pueblo 1. Pues bien, te animo a que intentes lo siguiente: recorre todas esas rutas que he puesto y quédate con la menor ruta. Cuando tengas la menor ruta, habrás resuelto el problema del viajante.

Por cierto, el número de combinaciones es n!, donde n es el número de ciudades a las que tienes que ir (sin contar el origen). En este caso: 3! = 6 rutas posibles.

[alex64128]

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.