Temas

[public int aux_dinamica(matriz_ady matriz,int i,int dest,CopyOnWriteArrayList<Integer> sol){ int point=0; int mascorto=Integer.MAX_VALUE; if(sol.isEmpty()) { return matriz.get_dist(i,1); } else{ //guardo el dato segun el ultimo valor del conjunto mas el numero de conjuntos point=sol.get(sol.size()-1)+sol.size(); if(gtab[i-1][point-1]!=-1) { return gtab[i-1][point-1]; } for(Integer j:sol){ mascorto=Math.min(mascorto, matriz.get_dist(i, j) +aux_dinamica(matriz,j,i,quitar(sol,j))); } } gtab[i-1][point-1]=mascorto; return mascorto; }]

Hola:
necesito implementar el problema del viajante de comercio en programacion dinamica y tengo un problema a la hora de ir almacenando los resultados para mejorar la eficiencia, se sobrescriben unos encima de otros y el programa no me da el resultado optimo.

Si no uso la tabla de resultados el programa calcula bien el resultado pero tarda demasiado.

Si alguien conoce una manera de almacenar los datos aqui esta el codigo en pseudocodigo:


http://www.casimages.es/i/140531012220207842.png.html

Y aqui mi codigo en java:

public int aux_dinamica(matriz_ady matriz,int i,int dest,CopyOnWriteArrayList<Integer> sol){
      int point=0;
      int mascorto=Integer.MAX_VALUE;   
      if(sol.isEmpty()) {         
         return matriz.get_dist(i,1);
      }      
      else{   
         //guardo el dato segun el ultimo valor del conjunto mas el numero de conjuntos
         point=sol.get(sol.size()-1)+sol.size();
         
         if(gtab[i-1][point-1]!=-1) {
            return gtab[i-1][point-1];
         }                     
               for(Integer j:sol){                  
                     mascorto=Math.min(mascorto,
                        matriz.get_dist(i, j)
                        +aux_dinamica(matriz,j,i,quitar(sol,j)));                              
               }            
            }
      gtab[i-1][point-1]=mascorto;
      return mascorto;            
   }