tsp.cpp

这是旅行商问题的求解方法.............. 文件输入

#include "draw.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "math.h"
#define  MAX 25
#define  PI 3.14159
    
struct vertex
{
   char choose[MAX];
   int min;
   int nextpoint;
   struct vertex *next;
};
struct point 
   {
	   double x,y;
   };

int distance[MAX][MAX];
int main()
{
	FILE *input;
	int n,i,j;
	struct vertex *g[MAX][MAX];
	char s[MAX],filename[15];
    void printgraph(char s[MAX],struct vertex *g[MAX][MAX],int n);
	void v0_s_v0(int n,char s[MAX],struct vertex *g[MAX][MAX]);


        printf("input the filename:");
        scanf("%s",filename);
        if((input=fopen(filename,"r"))==NULL)
        {
           printf("error:file do not exist\n");
           return  0;
        }
	    fscanf(input,"%d",&n);
	    for(i=0;i<n;i++)
		   for(j=0;j<n;j++)
			  g[i][j]=NULL;
        for(i=0;i<n;i++)  
		    for(j=0;j<n;j++)
	  	       fscanf(input,"%d",&distance[i][j]);
	    fclose(input);
	    for(i=0;i<n;i++)
	        s[i]='0';
	    s[i]='\0';
	   
        for(i=0;i<n;i++)  
		{
		     g[i][0]=(struct vertex *)malloc(sizeof(struct vertex));
		     strcpy(g[i][0]->choose,s);
       	     g[i][0]->min=distance[i][0];  
		     g[i][0]->nextpoint=0; 
		     g[i][0]->next=NULL;
		}
	    for(i=0;i<n;i++)
	       for(j=1;j<n;j++)
		      g[i][j]=NULL;
        v0_s_v0(n,s,g);
        printgraph(s,g,n);
        return 0;
}

void v0_s_v0(int n,char s[MAX],struct vertex *g[MAX][MAX])
{
	void choose_s(int size,int k,char s[MAX],int n,struct vertex *g[MAX][MAX],int const_size);
	int size,i;
    for(size=1;size<=n-2;size++) 
	{
	   choose_s(size,1,s,n,g,size);
	   for(i=0;i<n;i++)  
	      s[i]='0';
       s[i]='\0';
	}

    g[0][n-1]=(struct vertex *)malloc(sizeof(struct vertex));
	g[0][n-1]->min=65535;  
	for(i=1;i<n;i++)
       if(g[0][n-1]->min>distance[0][i]+g[i][n-2]->min)
	   {
		   g[0][n-1]->min=distance[0][i]+g[i][n-2]->min;
		   g[0][n-1]->nextpoint=i;
	   }
	printf("min length:%d\n",g[0][n-1]->min);
}
void choose_s(int size,int k,char s[MAX],int n,struct vertex *g[MAX][MAX],int const_size)
{
	int i_s_v0_g(int i,char s[MAX],struct vertex *g[MAX][MAX],int n,int const_size);
	int i;
	if(size==0)
	{
		for(i=n-1;i>0;i--)   
			if(s[i]=='0')  
				i_s_v0_g(i,s,g,n,const_size);
	}
	else 
	{
		for(i=k;i<=n-size;i++)   
		{
			s[i]='1';
			choose_s(size-1,i+1,s,n,g,const_size);
			s[i]='0';
		}
	}
}



int i_s_v0_g(int i,char s[MAX],struct vertex *g[MAX][MAX],int n,int const_size)
{
	int getmin(int j,int n,char s[MAX],struct vertex *g[MAX][MAX],int const_size);
	int j,j_s_min,i_s_v0_min=65535;  
	struct vertex *temp_record=(struct vertex *)malloc(sizeof(struct vertex));
    temp_record->next=NULL;
	strcpy(temp_record->choose,s);
	
    for(j=1;j<=n-1;j++)  
		if(s[j]=='1') 
		{
			{
			s[j]='0';
			j_s_min=getmin(j,n,s,g,const_size-1); 
			s[j]='1'; 
			if(i_s_v0_min>distance[i][j]+j_s_min) 
				i_s_v0_min=distance[i][j]+j_s_min;
				temp_record->nextpoint=j;       
				temp_record->min=i_s_v0_min;    
			}
		}
	temp_record->next=g[i][const_size];  
    g[i][const_size]=temp_record;
	return temp_record->min;  
}

int getmin(int j,int n,char s[MAX],struct vertex *g[MAX][MAX],int const_size)
{
	struct vertex *temp_record;
	for(temp_record=g[j][const_size];temp_record!=NULL;temp_record=temp_record->next)
		   if(strcmp(s,temp_record->choose)==0)
			 break;
	return temp_record->min;
}
void printgraph(char s[MAX],struct vertex *g[MAX][MAX],int n)
{
	void x_y_vi(struct point p[MAX],int n);
	void findconnectpoint(char s[MAX],int connect [MAX],struct vertex *g[MAX][MAX],int n);
    struct point p[MAX];
	int connect[MAX];
	int i;
	char v[2];
    x_y_vi(p,n); 
    findconnectpoint(s,connect,g,n);
	openWindow();	
	resizeWindow(0,400,400,0);
	
	v[1]='\0';
	for(i=0;i<n;i++)
	{   
		ezdSetColor(ezdBlue);
        ezdDrawCircle(p[i].x,p[i].y,10); 	
		ezdSetColor(ezdBlack);
		v[0]=i+'A';
		ezdDrawText(v, p[i].x+10,p[i].y-10);
	}
	delayWindow(0.5);
	for(i=0;i<n;i++)
	{
		ezdSetColor(ezdBlue);
		delayWindow(0.3);
        ezdDrawLine(p[connect[i]].x,p[connect[i]].y,p[connect[i+1]].x,p[connect[i+1]].y);
	}
   viewWindow();
   closeWindow();	
}

void x_y_vi(struct point p[MAX],int n)
{ 
    double r,x0,y0,o;
	int i;
    r=150;
	x0=200;
	y0=200;
    o=2*PI/(float)n; 
	for(i=0;i<n;i++)
	{
		p[i].x=x0+r*cos(o*i);
		p[i].y=y0+r*sin(o*i);
	}
}

void findconnectpoint(char s[MAX],int connect [MAX],struct vertex *g[MAX][MAX],int n)
{
	int i,j;
	struct vertex *temp;
	
	for(i=-0;i<n;i++)
		s[i]='1';
	s[0]='0';
	s[i]='\0';
	connect[0]=0;
	for(n=n-1,i=1,j=g[0][n]->nextpoint;n>=0;i++,n--)
	{   connect[i]=j;
	    s[j]='0';
		if(n==0)break;
		for(temp=g[j][n-1];temp!=NULL;temp=temp->next)
			if(strcmp(temp->choose,s)==0)
				break;
		j=temp->nextpoint;
	}
}