huisu-lvxing.cpp

旅行售货员问题,采用回溯算法实现,可以运行,带注释

// 旅行售货员问题?
#include <iostream.h>
#include <iomanip.h>
const int n=4; //图的顶点数
class Traveling
{
friend int TSP(int a[][n], int v[]);
private:
void Swap(int &, int &);
 void Backtrack(int i);
  int *x, //当前解
   *bestx, // 当前最优解
    a[n][n], //图G的邻接矩阵
      cv, //当前费用
       bestv;//当前最优值
       };
void Traveling::Backtrack(int i)
{
if (i+1>n)
 {
  if (a[x[n-2]][x[n-1]] && a[x[n-1]][0] && cv+a[x[n-1]][0]<bestv)
  {
   for (int j=0; j<n; j++)
   bestx[j]=x[j];
    bestv=cv+a[x[n-1]][0];
      }
      return;
      }
 for (int j=i; j<n; j++)  // 是否可进入x[j]子树
  if (a[x[i-1]][x[j]] && cv+a[x[i-1]][x[j]]<bestv)
   {   // 搜索子树
    Swap(x[i], x[j]);
    cv+=a[x[i-1]][x[i]];
      Backtrack(i+1);
       cv-=a[x[i-1]][x[i]];
        Swap(x[j], x[i]);
    }
 }
void Traveling::Swap(int &a1, int &b1)
{
int temp=a1;
 a1=b1;
  b1=temp;
  }
int TSP(int a[][n], int v[])
{ // 初始化
Traveling Y;
Y.x=new int [n];
for (int i=0; i<n; i++)
 Y.x[i]=i;
 for (int i=0; i<n; i++)
  for (int j=0; j<=i; j++)
   Y.a[i][j]=Y.a[j][i]=a[i][j];
    Y.cv=0;
    Y.bestv=100000; // ∞
     Y.bestx=v;
 cout<<"Adjacency Matrix of G:\n";
 for (int i=0; i<n; i++)
  {
  for (int j=0; j<n; j++)
  cout<<setw(5)<<Y.a[i][j];
  cout<<endl;
   }
 Y.Backtrack(1);
 delete Y.x;
  return Y.bestv;
  }
void main()
{
int t[][n]={{0},{30},{6,5},{4,10,20}}, v[n]={0,1,2,3};
 cout<<"\nBestv= "<<TSP(t, v)<<endl<<"Path = ";
 for (int i=0; i<n; i++)
 cout<<v[i]+1<<setw(4);
 cout<<v[0]+1<<endl<<endl;
 }