TSP programmi Java lähtekood

// Travelling Salesman Problem // Depth first search // Fourth attempt: improved algorithm // we will not continue searching paths // which are ALREADY worse than the best one // found so far

public class Tsp4 {

 static int cities=10; // nr of cities
 static int nodeslooked=0; // count nodes in search
 static int leaveslooked=0; // count leaves in search
 static int best=9999999;  // global variable recording best distance  
 // Matrix of distances (cost to travel) between cities 
 static int dist[][] =
         {{0,5,4,3,7,1,3,6,9,2},
          {5,0,2,9,4,1,7,2,3,4},
          {4,2,0,6,7,2,4,6,8,9},
          {3,9,6,0,6,2,5,6,9,9},
          {4,2,2,6,0,2,4,5,8,9},
          {3,9,6,6,6,0,5,6,9,4},
          {1,9,3,2,6,2,0,6,1,5},
          {3,2,0,6,2,2,4,0,2,3},
          {7,9,6,7,6,1,5,6,0,2},
          {1,8,2,7,6,1,3,6,2,0}};
          
 static int passedcities[]; // passed cities on a path
 static int bestpath[]; // best path so far        
          
 public static void main(String[] args) {               
    // create helper arrays
    passedcities = new int[cities];
    bestpath = new int[cities];
    // search from city 0, with 0 passed and 0 cost of travel so far      
    search(0,0,0);                     
    // print out result
    System.out.println("examined nodes during search: "+nodeslooked);
    System.out.println("examined leaves during search: "+leaveslooked);
    System.out.println("best cost: "+best); 
    System.out.println("best path: ");
    for (int i=0; i<cities; i++) System.out.print(bestpath[i] + " ");
      
 }
    
 // The recursive search function
 //
 // city: nr of city just arrived into
 // passed: number of cities passed so far
 // passedlen: length (cost) travelled so far
 
 static void search(int city, int passed, int passedlen) {
     //System.out.println("city: "+city+" passed: "+passed+
     //                   " passedlen: "+passedlen); 
     nodeslooked++; 
     // store the new passed city in the passed array
     passedcities[passed]=city;
     // maybe we have travelled through all cities - 1?
     if (passed==(cities-1)) {
         leaveslooked++;        
         // compute the final length (trip to home is left!)
         int length=passedlen+dist[0][city];
         // save the length and path if we are back home 
         // and the length found is best so far
         if (length<best) {
             best=length; 
             for (int i=0; i<cities; i++) bestpath[i]=passedcities[i]; 
         }              
     // if not all cities have been passed, try all cities
     // not yet passed          
     } else  {
          // loop over all cities
          for(int next=0; next<cities; next++) {
            // if the distance will be less
            // than the best distance so far, ONLY THEN GO!
            if (passedlen+dist[city][next] < best) {
              // check if next is OK (not passed yet)
              boolean okcity=true;
              for (int i=0; i<passed+1 && okcity; i++) 
                 if (passedcities[i]==next) okcity=false;                                    
              if (okcity) {   // if ok, continue search
               search(next,
                      passed+1,
                      passedlen+dist[city][next]); 
              }
            }  
          }    
      }    
              
 }
 

} // end of class