[SOLUCIONADO] Problema con el viajante de comercio

[numbersvj]

La idea de mi siguiente codigo es recorrer una matriz 4x4 rellenada cada posicion con las distancias entre las ciudades. Quien conozca el problema del viajante de comercio le sonara, pero la idea basica es ir elegiendo la ciudad mas cercana a una ciudad v0 elegida, que para mi es el primer valor.

Les muestro mi codigo

Código C++:

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;
        }
    }
}
 

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 ...

[CalgaryCorpus]

Podrias explicar, de la linea 32, la idea detras de hacer i = val2 ?

[vangodp]

jeje calgary como siempre... el ojo afilado =D, seguramente el problema este ahí XDDD
Se dejan el código por la mitad y cree que vamos a poder ayudar de esta forma.

[numbersvj]

Es lo que pensaba que podía estar mal, la verdad xD. Con i=val2 quiero que ese bucle empiece con i=0. Cuando encuentre el (0,2), el 2 en la siguiente iteración, luego de encontrar el (2,3), el 3 ... así.

El código está completo, vangodp, el resto son otros apartados que no influyen en esto :/

[CalgaryCorpus]

Creo que el problema esta aqui:
1- Haces un ciclo inicial en el que descubres el primero distinto que 0, lo consideras minimo
2- Comparas el resto contra el minimo y actualizas el minimo si alguno de ellos es menor que el elegido en el paso anterior. Actualizas val1 y val2 cuando ello ocurre.
3- Luego actualizas la matriz para que nadie pueda visitar ni las ciudades val1 o val2 nuevamente.

Todo eso parece estar bien, el problema esta que en 3) cada vez 2) tiene menos que recorrer. En la "ultima" iteracion, 2) nunca se ejecuta, por lo que el minimo que elegiste en 1) se queda.

Consecuencia de esto es que val1 y val2 no son actualizados y se mantiene lo dicho en la vuelta anterior.

Sugiero actualizar val1 y val2 al calcular el minimo inicial.

[numbersvj]

Exacto, era eso, ya funciona correctamente. Muchísimas gracias ^^

[nup_]

Hola:

Solo agregar q el algoritmo q usas no es la solución exacta al problema del viajante, usualmente da una solución más o menos buena pero a veces puede darte la peor.

slds;

nup_