算法设计与分析——回溯法——旅行售货员问题

╰+攻爆jí腚メ 2022-10-15 10:55 325阅读 0赞

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    const int noEdge=65535;
    class Traveling
    {
        
    	public:
    		void BackTrack(int i);
    		
    		int n;		//图G的顶点数 
    		int *x;		//当前的解 
    		int *bestx; // 当前的最优解 
    		int **a;    // 图G的临界矩阵 
    		int cc;     // 当前费用 
    		int bestc;  //当前最优花费的值 
    	//  int noEdge  无边标记 
     };
     
     void Traveling::BackTrack(int i)
     {
        
     	if(i == n)
     	{
        
     		if(a[x[n-1]][x[n]] !=noEdge && a[x[n]][1] !=noEdge 
    		   &&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc || bestc ==noEdge))
    		   {
        
    		   	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]][x[j]] != noEdge && (cc+a[x[i-1]][x[j]]<bestc||bestc == noEdge))
    	 		{
        
    	 			swap(x[i],x[j]);
    	 			cc+=a[x[i-1]][x[i]];
    	 			BackTrack(i+1);
    	 			cc-=a[x[i-1]][x[i]];
    				swap(x[i],x[j]);
    			 }
    		 }
    	 }
      } 
      
      int TSP(int **a,int v[],int n)
      {
        
      	Traveling Y;
      	Y.x = new int [n+1];
      	for(int i=1;i<=n;i++)
      	{
        
      		Y.x[i]=i;
    	  }
    	  Y.a= a;
    	  Y.n= n;
    	  Y.bestc = noEdge;
    	  Y.bestx = v;
    	  Y.cc = 0;
    	  
    	  Y.BackTrack(2);
    	  cout<<"旅行售货员问题的最优路径：";
    	  for(int i=1;i<=n;i++)
    	{
        
    		cout<<Y.bestx[i]<<"  ";
    		 
    	}
    	cout<<1<<endl;
    	  delete []Y.x;
    	  return Y.bestc; 
    	  
      }
    int main()
    {
        
    	int n;
    	
    	cout<<"输入城市的个数";
    	cin>>n;
    	int **vector = new int *[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		vector[i] = new int [n+1];
    	}
    	for(int i=1;i<=n;i++)
    	 {
        
    	 	for(int j=1;j<=n;j++)
    	 	{
        
    	 		vector[i][j]= noEdge;
    		 }
    	
    	 }
    	int x;
    	cout<<"输入城市间存在的通路的个数";
    	cin>>x;
    	cout<<"输入数据的形式为：(1 2 3)"<<endl;
    	int index_i,index_j,value;
    	 for(int i=0;i<x;i++)
    	 {
        
    	 	cin>>index_i>>index_j>>value;
    	 	vector[index_i][index_j]=value;
    	 	vector[index_j][index_i]=value;
    	 }
    	 cout<<"输出临界矩阵"<<endl; 
    	 for(int i=1;i<=n;i++)
    	 {
        
    	 	for(int j=1;j<=n;j++)
    	 	{
        
    	 		cout<<setw(5)<<vector[i][j]<<"  ";
    		 }
    		 cout<<endl;
    	 }
    	 int *v = new int [n+1];
    	 
    	 
    	 
    	cout<<"旅行售货员问题的最优值为:"<<TSP(vector,v,n)<<endl;
    	
    	
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221014/9434b9db6a7d4bf1b136e8c3358ede42.png