Tema: Problema con el viajante de comercio
Ver Mensaje Individual
  #1 (permalink)  
Antiguo 30/04/2014, 19:21
numbersvj
 
Fecha de Ingreso: octubre-2013
Mensajes: 5
Antigüedad: 10 años, 6 meses
Puntos: 0
Pregunta Problema con el viajante de comercio
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++: 
Ver original
  1. int matriz[n][n];
  2. int minimo;
  3. list <int> vertice;//Subconjunto solución
  4.  
  5. /*--------------------------------------------------*/
  6. // Rellenamos matriz a ceros
  7.  
  8. for(int i=0; i<n; i++){
  9.     for(int j=0; j<n; j++){
  10.               matriz[i][j] = 0;
  11.     }
  12. }
  13.  
  14. matriz[0][1]=5;
  15. matriz[0][2]=2;
  16. matriz[0][3]=3;
  17. matriz[1][0]=5;
  18. matriz[1][2]=4;
  19. matriz[1][3]=5;
  20. matriz[2][0]=2;
  21. matriz[2][1]=4;
  22. matriz[2][3]=1;
  23. matriz[3][0]=3;
  24. matriz[3][1]=5;
  25. matriz[3][2]=1;
  26.  
  27. bool aumento;
  28. int contador;
  29. int contador2;
  30. int val1,val2;
  31.  
  32. for(int i=0; i<n; i=val2){
  33.     aumento = true;
  34.     contador2 = 0;
  35.     for(int j=0; j<n; j++){
  36.  
  37.         if (aumento){
  38.             contador = 0;
  39.  
  40.             while (matriz[i][contador]==0){
  41.                 contador++;
  42.             }
  43.  
  44.             minimo = matriz[i][contador]; 
  45.             //cout << "\nMINIMO INICIAL EN FILA " << i << " : " << minimo << endl;
  46.             aumento = false;
  47.         }
  48.         
  49.         contador2++;
  50.         if(matriz[i][j]!=0){
  51.             if(matriz[i][j] < minimo){
  52.                 minimo = matriz[i][j]; 
  53.                 val1 = i;
  54.                 val2 = j;
  55.                 //cout << "MINIMO DE LA FILA " << i << ": " << minimo << endl;
  56.                 cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
  57.                 
  58.             }
  59.         }
  60.         //cout << "CONTADOR2 : " << contador2 << endl;
  61.     
  62.         if (contador2 == n){
  63.  
  64.             vertice.push_back(val1);
  65.                 vertice.push_back(val2);
  66.  
  67.              for(int j=0; j<n; j++){
  68.  
  69.                           matriz[j][val1]=0;
  70.                           matriz[j][val2]=0; 
  71.             }
  72.  
  73.             // cout << "POSICION " << "("<<val1<<","<<val2<<")"<<endl;
  74.         }
  75.     }
  76. }

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