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