tsp1.cpp

人工智能经典问题TSP问题的C语言实现

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

void main()
{
	int city[15][15];
	int i;
	int j;
	int c;
	int temp;
	int path[15];   //记录访问路径
	int tour[15]={0};   //标记是否已经走过
	int temppoint=0;
	int nowpoint=0;
	long length=0;
	
	
    

	srand( (unsigned)time( NULL ) );

	for(i=0;i<15;i++){
		for(j=0;j<15;j++)
		{
		if(i==j)
		    {	
		    city[i][j]=0;
	     	}
	
		else 
		{
	    temp=rand()%100;
        c=temp;
        while(c==0)
		{ 
		  temp=rand()%100;
       	  c=temp;
	    
		}
	    city[i][j]=c;	
	    city[j][i]=c;
	    
		}
		
	  }
	}

	cout<<" ";
	for(i=0;i<15;i++)
		cout<<i<<" ";
	cout<<endl;

	for(i=0;i<15;i++)
	{    
        cout<<i<<" ";
		for(int j=0;j<15;j++)
		{
	     cout<<city[i][j]<<"  ";
		}
		cout<<endl;
	}
   
    path[0]=0;
	tour[0]=1;
	for(i=1;i<15;i++){
		temp=1000;
		
		for(j=0;j<15;j++){
			if(city[nowpoint][j]==0)
				continue;
			if(city[nowpoint][j]<temp){
				if(tour[j]==0){
					temp=city[nowpoint][j];
					temppoint=j;
				}
			}
		}

		tour[temppoint]=1;
		nowpoint=temppoint;
		path[i]=temppoint;
	}
    
	cout<<"the path is:"<<endl;
	for(i=0;i<15;i++){
		if(i==14)
			cout<<path[i];
		else
		    cout<<path[i]<<"->";
	}
    cout<<endl;

	cout<<"the total length is:"<<endl;

	for(i=0;i<14;i++){
       temppoint=path[i];
	   nowpoint=path[i+1];
       length+=city[temppoint][nowpoint];
	 }
     cout<<length<<endl;





}