tanxin.cpp

用贪心法解决TSP问题.输入数据可求得所要的最值的结果.

#include<iostream.h>
#include<stdlib.h>
#include<math.h>
class tanxintsp
{ public:
int A[10][10];

 
    int n;
    int pass[10];
    int d;
    void inputA();
    void tsp(int begin);
    void outlujing();
};

void tanxintsp::inputA()
{ int i,j;
  for(i=0;i<10;i++)
    for(j=0;j<10;j++)
      A[i][j]=5000;
A[0][0]=500;   A[0][1]=1;    A[0][2]=2;   A[0][3]=7;   A[0][4]=5;     
 A[1][0]=1;    A[1][1]=500;  A[1][2]=4;   A[1][3]=4;   A[1][4]=3;     
 A[2][0]=2;    A[2][1]=4;    A[2][2]=500; A[2][3]=1;   A[2][4]=2;     
 A[3][0]=7;    A[3][1]=4;    A[3][2]=1;   A[3][3]=500; A[3][4]=3;     
 A[4][0]=5;    A[4][1]=3;    A[4][2]=2;   A[4][3]=3;   A[4][4]=500;     
  
 
 n=5;
  cout<<endl<<"各城市间的距离 矩阵为A[n][n]："<<endl;
   for(i=0;i<n;i++)
    {for(j=0;j<n;j++)  
       cout<<"   "<<   A[i][j]<<"   "   ; 
      cout<<endl;
    }
}


void tanxintsp::tsp(int begin)
{int i,j,h, knot,min,k,p[10];
d=0;
for(i=0;i<n;i++)
{pass[i]=0;
p[i]=0;}
pass[0]=begin+1;
p[begin]=1;  
min=A[begin][0];
knot=1;
i=begin;
while (knot<=n)

{  
	{min=500;
		for(j=0;j<n;j++)
       if((A[i][j]<min)&&(p[j]==0))
             {min=A[i][j];
              k=j;
             } 
	   if(knot!=n)
           d=d+min;
	      else d=d;
       pass[knot]=k+1;
       knot++;
	   p[k]=1;
	}

       i=k; 
  };


  h=pass[n-1];
   pass[n]=begin+1;
   d=d+A[h-1][begin];
}
void tanxintsp::outlujing()
{int i;
 cout<<"输出所经过路径为"<<endl;
 for(i=0;i<=n;i++)
  cout<<"-->"<<pass[i];
  
  cout<<endl<<"总路程为"<<endl;
  cout<<d;
  cout<<endl;
}


void main()
{
 int i,flag;
 flag=1;
 tanxintsp mytsp;
 mytsp.inputA();
 cout<<"请输入起始城市（从第i城市出发）："<<endl;
 cout<<"i:";
 cin>>i;
 while (flag==1)
 {if(i>=5) 
 {cout<<"图中没有该城市，请重新输入！"<<endl;
    cout<<"i:";
    cin>>i;}
  if(i<5)
	  flag=0;
 }

 mytsp.tsp(i-1);
 mytsp.outlujing();
}