travel.cpp

旅行售货员问题的近似算法 数据结构 算法 NP完全问题

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
int m,n;
int**  value;
int* temporder;
void Swap(int& a,int& b)
{
  int temp;
  temp = a; a = b; b= temp;
}
int compute()
{
	int distance=0;
	for (int i=1;i<m+1;i++)
		distance+=value[temporder[i]][temporder[i+1]];
	return distance;
}
int valuechange(int i,int j)
{
 int change = 0;
 change = value[temporder[i]][temporder[i+1]] - value[temporder[j]][temporder[i+1]];
 change = change + value[temporder[i-1]][temporder[i]] - value[temporder[i-1]][temporder[j]];
 change = change + value[temporder[j]][temporder[j+1]] - value[temporder[i]][temporder[j+1]];
 change = change + value[temporder[j-1]][temporder[j]] - value[temporder[j-1]][temporder[i]];
 return change;
}
void main()
{   
	clock_t start,end;
	start = clock();
	int  tempresult,result = 10000000;
    ifstream input("input.txt");  
	ofstream output("output.txt");  
	input>>m>>n;
    value=new int*[m+1];
	for(int i=0;i<=m;i++)  value[i] = new int[m+1];
	temporder = new int[m+2];
	int* order = new int[m+1];
	for(i=0;i<m+1;i++)
	  for(int j=0;j<m+1;j++)
	  {
	     value[i][j] = 500000;
	  }
    for(i=0;i<n;i++) 
	{
	 int x,y,temp;
	 input>>x>>y>>temp;
	 value[x][y] = temp;
	}
	for(i=1;i<m+1;i++)  order[i] = i;
	srand((unsigned)time(NULL));
	do{ 
		for(i=1;i<m+1;i++)  temporder[i] = i;
        temporder[m+1] = 1;
	    for(i=2;i<m+1;i++) 
		{
		  int j = rand()%(m-i+1)+i;
		  Swap(temporder[i],temporder[j]);
		}
		tempresult = compute();
	   for(i=2;i<m+1;i++)
		for(int j=2;j<m+1;j++) 
		 if(i!=j)
		  { 
			int changenum = valuechange(i,j);
			if (changenum>0) 
			{
			 Swap(temporder[i],temporder[j]);
			 tempresult = tempresult - changenum;
			}
		 }
      if(tempresult<result) 
	  {
		result = tempresult;
		for(i = 1;i<m+1;i++) order[i] = temporder[i];
	  }
	  end = clock();
   }while(end-start<=985);
  if(result>500000)  output<<"No Solution"<<endl;
  output<<result<<endl;
  for(i=1;i<m+1;i++)  output<<order[i]<<" ";
}