//本程序取自王曉東編著“算法分析與設計”第 174 頁，例
//貨郎擔問題的回溯解法
//
 
    class Bttsp
      {
        static int n;          //圖G的頂點個數
        static int []x;        //當前解
        static int [] bestx;  //當前最優解
        static float bestc;   //當前最優值
        static float cc;      //當前費用
        static float [][]a;   //圖G的臨界矩陣

      public static float tsp(int[] v)
        {//置x為單位排列
          x=new int[n+1];
          for(int i=1;i<=n;i++)
            x[i]=i;
          bestc=Float.MAX_VALUE;
          bestx=v;
          cc=0;
          //搜索x[2:n]的全排列
          backtrack(2);
          return bestc;
        }

      private static void backtrack(int i)
        {
          if(i==n)
            {
              if(a[x[n-1]][x[n]]<Float.MAX_VALUE && a[x[n]][1]<Float.MAX_VALUE &&
                (bestc==Float.MAX_VALUE||cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc))
              {
                for(int j=1;j<=n;j++)
                  bestx[j]=x[j];
                bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];    
              }
            }
          else
            {
            for(int j=i;j<=n;j++)
             {//
              if(a[x[i-1]][j]<Float.MAX_VALUE &&
                (bestc==Float.MAX_VALUE||cc+a[x[i-1]][x[j]]<bestc));
              {//
               swap(x,i,j);
               cc+=a[x[i-1]][x[i]];
               backtrack(i+1);
               cc-=a[x[i-1]][x[i]];
               swap(x,i,j);
              }
            }
           }
       }
       static void swap(int[] a,int i1,int j1)
        {
          int temp;   
          temp=a[i1];
          a[i1]=a[j1];
          a[j1]=temp;
        }      
       }//

   public class Fac5_9{
  
      public static void main(String args[])
  {
     Bttsp abc=new Bttsp();
     int n1=4;   
     int v1[]=new int[n1+1];
     float a1[][]=new float [n1+1][n1+1];
      a1[1][1]=0.0f; a1[1][2]=30.0f; a1[1][3]=6.0f;  a1[1][4]=4.0f; 
      a1[2][1]=30.f; a1[2][2]=0.0f;  a1[2][3]=5.0f;  a1[2][4]=10.0f; 
      a1[3][1]=6.0f; a1[3][2]=5.0f;  a1[3][3]=0.0f;  a1[3][4]=20.0f; 
      a1[4][1]=4.0f; a1[4][2]=10.0f; a1[4][3]=20.0f; a1[4][4]=0.0f;
      for(int k=0;k<=n1;k++)      
        v1[k]=0;
     
     abc.a=a1;         
     abc.n=n1;
         
     System.out.println("貨郎擔問題的最優解   " + abc.tsp(v1));
     for(int k=1;k<=n1;k++)
     System.out.print("  "+abc.bestx[k]);
     System.out.println();
  }
}