/*
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個文件信息