Lehekülje Tsp.java lähteteksti vaatamine

<pre>
class tsp {
  static int cities=14;   
  static int[] passedcities;  
  static int[] bestpath;    
  static int bestlen=999999999; 
  static int nodecount=0;
  static int leafcount=0;    
  static int dist[][] =  {
   {0,92,85,178,206,105,121,223,160,12,183,179,26,220,233,184,151,210,224,231,126,216,161,217,178,156,13,131,271,265,89,107,203,90,146,70,224,185,144,183,166,179,244,69,60,247,196,152,156,111,211,43,94,71,36,144,67,123,94},
   {92,0,68,270,298,197,137,213,131,80,250,272,118,245,223,95,243,231,317,323,218,268,72,268,89,147,105,223,261,255,40,171,295,138,57,162,242,206,218,276,77,271,234,161,125,340,265,191,216,84,304,54,159,37,100,237,132,34,158},
   {85,68,0,262,290,189,90,167,84,72,204,235,111,199,177,117,236,184,309,315,210,222,103,221,120,100,97,216,215,209,22,136,258,92,61,154,196,160,190,268,94,228,188,153,93,332,219,145,170,37,296,42,141,60,69,229,117,64,135},
   {178,270,262,0,31,175,219,265,280,190,138,76,152,233,256,347,84,208,158,56,50,168,339,120,356,255,171,66,312,306,266,153,93,189,293,108,237,199,91,9,312,82,285,123,183,73,99,202,196,249,145,221,141,249,204,78,170,300,149},
   {206,298,290,31,0,203,250,296,311,218,170,107,180,264,287,378,118,239,103,25,78,199,367,151,384,286,199,97,343,338,294,185,124,221,325,136,269,231,122,22,344,113,317,151,215,42,130,234,227,280,58,249,172,277,232,106,201,328,181},
   {105,197,189,175,203,0,216,302,256,117,222,176,79,270,293,288,148,260,221,228,123,261,266,214,283,248,98,128,349,343,193,153,200,185,234,67,274,235,152,180,265,176,322,66,140,244,193,202,206,209,208,148,140,176,131,141,162,227,106},
   {121,137,90,219,250,216,0,104,62,119,120,173,136,136,114,152,237,101,309,275,211,138,162,138,179,37,133,154,152,146,96,74,196,30,102,158,133,76,128,228,116,165,125,148,76,292,150,61,86,53,297,121,78,139,85,230,56,124,107},
   {223,213,167,265,296,302,104,0,96,221,149,193,239,32,10,219,310,60,384,322,276,128,239,153,256,71,236,233,48,42,173,149,217,133,179,244,29,67,212,274,183,186,21,234,178,338,165,97,95,130,371,198,162,216,188,304,158,201,196},
   {160,131,84,280,311,256,62,96,0,158,181,233,177,128,106,136,297,124,370,336,271,162,156,186,174,29,172,214,144,138,91,134,257,91,96,215,125,100,189,289,100,226,117,206,137,353,198,122,147,47,357,115,139,133,125,290,117,118,167},
   {12,80,72,190,218,117,119,221,158,0,181,192,38,218,231,172,163,208,237,243,138,214,149,229,166,154,25,143,269,263,76,105,215,89,133,82,223,183,142,196,154,191,242,81,58,260,208,150,154,99,224,31,92,59,34,157,65,110,92},
   {183,250,204,138,170,222,120,149,181,181,0,67,199,117,140,266,183,92,257,195,149,52,276,26,293,156,196,96,196,191,210,80,90,115,216,157,122,84,70,147,229,59,170,170,138,211,38,72,66,167,244,209,94,237,148,177,118,237,128},
   {179,272,235,76,107,176,173,193,233,192,67,0,154,161,184,301,125,136,198,132,90,96,307,48,324,208,173,50,240,235,241,108,24,143,247,112,166,128,58,85,266,8,214,125,157,149,26,131,125,202,185,222,108,250,166,118,137,269,119},
   {26,118,111,152,180,79,136,239,177,38,199,154,0,236,249,210,125,226,199,205,100,232,187,191,204,172,19,105,287,281,115,123,177,106,172,44,240,201,129,158,192,153,260,43,76,222,170,168,172,130,186,69,110,97,52,119,83,149,82},
   {220,245,199,233,264,270,136,32,128,218,117,161,236,0,23,251,278,36,352,289,244,96,270,121,288,103,233,201,79,73,205,117,185,164,211,212,4,35,180,242,215,154,52,202,210,306,133,65,63,162,339,230,130,248,185,272,156,232,164},
   {233,223,177,256,287,293,114,10,106,231,140,184,249,23,0,229,301,51,375,313,267,119,249,144,266,81,246,224,57,51,183,140,208,143,189,235,20,58,203,265,193,177,30,225,188,329,156,88,86,140,362,208,153,226,198,295,168,211,187},
   {184,95,117,347,378,288,152,219,136,172,266,301,210,251,229,0,335,246,408,403,309,284,95,283,112,153,197,282,267,261,95,202,324,157,54,253,248,222,256,356,36,293,241,252,198,420,285,206,232,100,395,141,206,134,173,328,184,62,232},
   {151,243,236,84,118,148,237,310,297,163,183,125,125,278,301,335,0,253,73,121,34,213,312,165,329,272,144,89,357,352,240,176,148,206,281,81,283,245,115,90,311,127,331,96,164,77,144,226,230,255,60,194,163,222,177,7,185,274,130},
   {210,231,184,208,239,260,101,60,124,208,92,136,226,36,51,246,253,0,326,264,219,71,256,95,273,99,223,175,107,101,190,107,159,123,196,203,40,24,154,217,210,129,80,193,164,281,107,54,54,147,313,215,121,233,175,246,145,218,155}                
  };    
   /* 
         {{0, 5, 4, 3},              
          {5, 0, 2, 9},           
          {4, 2, 0, 6},           
          {3, 9, 6, 0}};
    */      
  public static void main(String[] args) {
    int res;  
    int j;
    System.out.println("tsp starts");              
    passedcities = new int[cities];  
    bestpath = new int[cities];          
    res=search(0,0,0);        
    System.out.println("min cost: "+bestlen); 
    System.out.println("bestpath: ");   
    for(j=0;j<cities;j++) {
        System.out.print(" "+bestpath[j]);        
    }    
    System.out.println("");  
    System.out.println("cities: "+cities); 
    System.out.println("leafcount: "+leafcount+
                       " nodecount: "+nodecount);   
    
  }
  
  static int search(int start, int passednr, int len) {
    int i;  
    int j;  
    int tmp;      
    boolean okgo;  
    int bestn;
    int bestnlen;      
    
    nodecount++;  
    passedcities[passednr]=start;   
      
    //System.out.println("search: "+start+passednr+len);               
    //System.out.print("passed: ");  
    //for(j=0;j<=passednr;j++) System.out.print( passedcities[j]);  
    //System.out.println("");  
    
    if (passednr>=cities-1)  {
      leafcount++;  
      len=len+dist[start][0];  
      if (len<bestlen) {
        bestlen=len;
        for(j=0;j<cities;j++) bestpath[j]=passedcities[j];  
      }
      //System.out.println("returning len and bestlen: "+
      //                         len+bestlen);             
      return len;   
    }        
    bestn=0;
    bestnlen=999999;
    for(i=0; i<cities; i++) {
      okgo = true;  
      for(j=0;j<=passednr;j++) {
        if (passedcities[j]==i) {
          okgo=false;
          break;            
        }             
      }   
      if (okgo) {      
        tmp=len+dist[start][i];
        if (tmp<bestnlen) {
          bestnlen=tmp;
          bestn=i;  
        }          
      }        
    } 
    tmp=len+dist[start][bestn];
    if (tmp<bestlen) {         
          tmp=search(bestn,passednr+1,tmp);       
    }   
    for(i=0; i<cities; i++) {
      if (i==bestn) continue;  
      okgo = true;  
      for(j=0;j<=passednr;j++) {
        if (passedcities[j]==i) {
          okgo=false;
          break;            
        }             
      }   
      if (okgo) {
        tmp=len+dist[start][i];
        if (tmp<bestlen) {         
          tmp=search(i,passednr+1,tmp);       
        }    
      }    
    } 
    return len;     
  }    


}

</pre>