用回溯法解决TSP问题

本压缩文档包含三个文件：用回溯法解决TSP问题可执行源代码，word文档报告，实验测试数据

#include “stdio.h“
#include “math.h“
#include “stdlib.h“


#define N 10
//#define M 1*2*3*4
#define num 100
int noEdge=-1;      //无边标记

struct object
{
	int n;   //城市编号
	int x;   //x坐标
	int y;   //y坐标
}wup;

struct object wp[N+1];  //共N个城市
  
double A[num][num];//存放各个城市之间的代价
int count;//记录走过的节点数
int bestA[num];//当前最优解
int x[num];//当前解

double currentP;//当前路径值
double bestPath;//当前最短路径值

int distant（int x1int y1int x2int y2）
{
	double x=0;
	x=sqrt（pow（abs（x1-x2）2）+pow（abs（y1-y2）2））;

 return （int）x;

}

void Backtrack（int i）
{
	count++;
	if（i==N）
	{
		if（A[x[N-1]][x[N]]!=noEdge && A[x[N]][x[1]]!=noEdge）
		{
			if（ bestPath == noEdge ||bestPath > currentP+A[x[N-1]][x[N]]+A[x[N]][x[1]]）
			{
			
				for（int j=1;j<=N;j++）
				{
					bestA[j]=x[j];
				}
				bestPath=currentP+A[x[N-1]][x[N]]+A[x[N]][x[1]];
			}

		}
	}
	else
	{
		int j;
		for（j=i;j<=N;j++）
		{
			if（A[x[i-1]][x[j]] !=noEdge）
			{
				if（bestPath ==noEdge || bestPath > currentP+A[x[i-1]][x[j]]+A[x[j]][x[1]] ）
				{
					int temp;
					currentP +=A[x[i-1]][x[j]];
					temp=x[i];
					x[i]=x[j];
					x[j]=temp;
					Backtrack（i+1）;
					temp=x[i];
					x[i]=x[j];
					x[j]=temp;
					currentP -=A[x[i-1]][x[j]];
				}
			}
		}
    }	
}

double tsp（）
{
	//初始化
	bestPath=noEdge;
	currentP=0.0;
	int i;
	for（i=1;i<=N;i++）
	{
		x[i]=i;
	}
	Backtrack（2）;
	return bestPath;
}

void output（）
{
	int i;
	for（i=1;i<=N;i++）
	{
		printf（“%4d“bestA[i]）;
	}
	printf（“  1“）;
	printf（“\n“）;
}

int main（） 
{    
	int ij;
	//获取数据
    FILE *fp;        /*文件指针*/

	if（（fp=fopen（“data.txt““r+“））==NULL） 
	{
		printf（“cannot open the file!“）; 
		exit（0）; 
	} 
	//读取文件
	
	for（i=1;i<=N;i++）
	{
		fscanf（fp“%d%d%d“&wp[i].n&wp[i].x&wp[i].y）;
	}

	printf（“  城市编号  x坐标  y坐标\n“）;
	for（i=1;i<=N;i++）
	{	
		printf（“     %d      %d   %d\n“wp[i].nwp[i].xwp[i].y）;
	}
	printf（“--------------------------------------\n\n“）;

	for（ i=1;i<=N;i++）
	{ 
	  for（j=1;j<=N;j++）
	  { 
		  if（i==j）
		  {
			A[i][j]=-1;
		  }
		  else
		  {
			  A[i][j]=distant（wp[i].xwp[i].ywp[j].xwp[j].y）;
		  }
	  }
	}
	for（i=1;i<=N;i++）
	{
		printf（“第%d行:  “i）;
		for（j=1;j<=N;j++）
		{ 
			printf（“%2.0f  “A[i][j]）;
		}
		printf（“\n“）;
	}

	printf（“\n“）;
	printf（“--------------------------------------\n“）;
     printf（“走%d个城市最短路径为：%lf\n“Ntsp（））;
     printf（“走法为:“）;  
	 output（）;
	 printf（“循环次数：%d\n“count）;
}  

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     221877  2018-07-01 18:59  15计2-2015551239-王维-用回溯法解TSP问题\15计2-2015551239-王维-用回溯法解TSP问题.docx

     文件       2136  2015-05-07 14:17  15计2-2015551239-王维-用回溯法解TSP问题\data.txt

     文件       2620  2018-07-01 15:47  15计2-2015551239-王维-用回溯法解TSP问题\tsp.cpp

     文件     163437  2018-07-01 15:37  15计2-2015551239-王维-用回溯法解TSP问题\tsp.exe

     目录          0  2018-07-01 18:59  15计2-2015551239-王维-用回溯法解TSP问题

----------- ---------  ---------- -----  ----

               390070                    5