三种解决TSP问题的近似算法的实现

最近邻策略(NearestNeighbor)解决TSP问题的算法实现——是基于贪心思想； 最短链路策略(ShortestLinkedHeuristic)解决TSP问题的算法实现——也是基于贪心算法，但与上述实现细节有所不同； 最短插入启发式策略(NearestInsertion)解决TSP问题的算法实现——插入启发式策略基本思想是对由|V|个城市的某m个城市所构成的回路，陆续地选择一个未在回路中的城市，然后插入到该回路，使得引起的权和的改变量最小。重复上述过程，直到所有的城市被插入。根据选择待插入城市的不同，插入启发式策略包括最近点插入、最远点插入以及随机插入法。

/*
Function:采用最近插入启发式算法计算TSP问题
		其思想是：从TSP路径只含一个节点始态出发，每次从剩余节点中找出离TSP路径中
				新近加入的节点最近的点（此处我不知理解是否正确），标记此节点vk为已访问；
				然后找出将此vk节点加入到某边的两个节点中间时，能够使加入后的代价最小的这样的
				边，修改这个边的路径，使其两个节点要能够连接起来的话，需要经过中间节点vk;如此
				进行下去，直到所有的节点都在TSP路径中
Date:2012/5/2
Author:黄其华
*/
#include
#include

using namespace std;
#define N 50
typedef struct _edge
{
	int weight;
	int start;
	int end;
}Edges;
/*
int Sets[N];	//顶点集
*/
Edges Result[N*（N-1）/2];		//因为是完全无向图
Edges endEdge;						//路径的起始端点
int n=0;		//代表顶点数

int NearestInsertion（int v0bool visited[]int dis[][N]）
{
	int m=0k=0vk=v0vj;
	int cost=0;
	Result[1].start=v0;	//先初始结点
	Result[1].end=v0;
	Result[1].weight=0;
	while（1）
	{
		int min=10000;
		//找离TSP路径中已有点后一个点最近的点
		for（int i=1;i<=n;i++）
			if（!visited[i]&&min>dis[vk][i]）
				{
					vj=i;
					min=dis[vk][i];
					//visited[i]=true;
				}
		vk=vj;		//记下最后加入到TSP路径中的顶点
		visited[vj]=true;
		if（Result[1].weight==0）		//如果是TSP路径中只有一个节点的情况
			{
				Result[1].end=vk;
				endEdge.end=vk;
				m++;
				Result[1].weight=dis[Result[1].start][vk];
				cost+=Result[1].weight;
				continue;
			}
		int minW=10000;
		int p=1;
		for（p;Result[p].weight!=0&&p<=n*n-1;p++）
		{
			
			if（minW>dis[Result[p].start][vk]+dis[vk][Result[p].end]-Result[p].weight）		//选边
			{
				k=p;
				minW=dis[Result[p].start][vk]+dis[vk][Result[p].end]-Result[p].weight;
				//m++;
			}

		}
		//replace Result[i] with new Result[i]and Result[k] with new value
		m++;
		int tmpStart=Result[k].start;
		int tmpEnd=Result[k].end;
		Result[k].start=Result[k].start;
		Result[k].end=vk;
		Result[k].weight=dis[Result[k].start][vk];
		Result[p].start=vk;
		Result[p].end=tmpEnd;
		Result[p].weight=dis[Result[p].end][vk];
		cost+=minW;//Result[k].weight;
		if（m==n-1）		//已有了n个结点
			break;
	}
	return cost;
}
int main（）
{
	scanf（“%d“&n）;
	int dis[N][N];		//距离矩阵
	memset（dis0N*N*sizeof（int））;		//对距离矩阵初始化为0，所以，为防止后面的过程中出现对0编号的干扰，所有顶点从1开始编号
	memset（Result0N*（N-1）/2*sizeof（Edges））;
	/*
	for（int i=1;i<=n;i++）
		Sets[i]=i;			//从1开始编号
		*/
	//接收输入距离矩阵
	for（int j=1;j<=n;j++）
		for（int k=1;k<=n;k++）
			scanf（“%d“&dis[j][k]）;
	bool visited[N];
	memset（visitedfalseN*sizeof（bool））;	//用来标记某个结点是否访问过
	int v0=rand（）%（n-1+1）+1;		//随机生成1到n的数作为初始的TSP路径的起点
	endEdge.start=v0;
	visited[v0]=true;
	int cost=NearestInsertion（v0visiteddis）;
	for（int i=1;Result[i].weight!=0;i++）
		printf（“\nstart:%d  end:%d  weight:%d\n“Result[i].startResult[i].endResult[i].weight）;
	endEdge.weight=dis[endEdge.start][endEdge.end];
	printf（“cost:%d\n“cost+endEdge.weight）;
	system（“pause“）;
	return 0;
}

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

     文件        794  2012-05-02 20:23  实验14\NearestInsertion\Debug\cl.command.1.tlog

     文件       8880  2012-05-02 20:23  实验14\NearestInsertion\Debug\CL.read.1.tlog

     文件        552  2012-05-02 20:23  实验14\NearestInsertion\Debug\CL.write.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link-cvtres.read.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link-cvtres.write.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.2752-cvtres.read.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.2752-cvtres.write.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.2752.read.1.tlog

     文件          2  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.2752.write.1.tlog

     文件       1888  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.command.1.tlog

     文件       3128  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.read.1.tlog

     文件       1218  2012-05-02 20:23  实验14\NearestInsertion\Debug\link.write.1.tlog

     文件      33965  2012-05-02 20:23  实验14\NearestInsertion\Debug\main.obj

     文件        510  2012-05-02 20:23  实验14\NearestInsertion\Debug\mt.command.1.tlog

     文件        566  2012-05-02 20:23  实验14\NearestInsertion\Debug\mt.read.1.tlog

     文件        498  2012-05-02 20:23  实验14\NearestInsertion\Debug\mt.write.1.tlog

     文件       3116  2012-05-02 20:08  实验14\NearestInsertion\Debug\NearestInsertion.Build.CppClean.log

     文件        406  2012-05-02 20:08  实验14\NearestInsertion\Debug\NearestInsertion.exe.embed.manifest

     文件        472  2012-05-02 20:08  实验14\NearestInsertion\Debug\NearestInsertion.exe.embed.manifest.res

     文件        381  2012-05-02 20:23  实验14\NearestInsertion\Debug\NearestInsertion.exe.intermediate.manifest

     文件         95  2012-05-02 20:23  实验14\NearestInsertion\Debug\NearestInsertion.lastbuildstate

     文件       3270  2012-05-02 20:23  实验14\NearestInsertion\Debug\NearestInsertion.log

     文件        222  2012-05-02 20:08  实验14\NearestInsertion\Debug\NearestInsertion_manifest.rc

     文件        762  2012-05-02 20:08  实验14\NearestInsertion\Debug\rc.command.1.tlog

     文件        470  2012-05-02 20:08  实验14\NearestInsertion\Debug\rc.read.1.tlog

     文件        478  2012-05-02 20:08  实验14\NearestInsertion\Debug\rc.write.1.tlog

     文件     207872  2012-05-02 20:23  实验14\NearestInsertion\Debug\vc100.idb

     文件     233472  2012-05-02 20:23  实验14\NearestInsertion\Debug\vc100.pdb

     文件       3015  2012-05-02 20:22  实验14\NearestInsertion\main.cpp

     文件       3926  2012-05-02 13:12  实验14\NearestInsertion\NearestInsertion.vcxproj

............此处省略76个文件信息