tsp.cpp

本程序实现了NPC问题旅行商的三个近似算法。

#include "tsp.h"

bool cmp(edge_info &e1, edge_info &e2)
{
	return e1.fee<e2.fee;
}

tsp::tsp()
{
}

tsp::~tsp()
{
}

bool tsp::LoadGraph()
{
	int i, j;
	FILE* fp = fopen("tsp20.txt", "r");
	if(fp==NULL) return false;
	fscanf(fp, "%d", &iCityNum);

	for(i=0; i<iCityNum; i++)
	{
		for(j=0; j<iCityNum; j++)
			fscanf(fp, "%d", &Graph[i][j]);
	}
	return true;
}

bool tsp::NearestNeighbor()
{
	int cost = 0;
	int cnt = 1;
	int n = iCityNum;
	int i, j;

	bool *visited = new bool[n+1];
	int *H = new int[n + 1];
	for(i=0; i<n; i++) visited[i] = false;
	visited[0] = true;
	H[0] = 0;


	int u=0, v;
	while(cnt<iCityNum)
	{
		int min = 0x7FFFffff;
		for(j=0; j<n; j++)
		{
			if(j!=u && !visited[j])
			{
				if(Graph[u][j] < min) min = Graph[u][j];
				v = j;
			}
		}
		if(min ==0x7FFFffff) // no vetex to go
		{
			cout << "no solution" << endl;
			return false;
		}
		else
		{
			cost += Graph[u][v];
			H[cnt]  = v;
			cnt++;
			u = v;
			visited[v] = true;
		}
	}

	cost += Graph[ H[0] ][ H[n-1] ];
	cout << "the total cost is " << cost << endl;
	cout << "the path is:" << endl;
	for(i=0; i<n; i++)
		cout << H[i]+1 << " ";

	cout << endl;
	delete []H;
	delete []visited;
	return true;
}

int tsp::findaedge(bool f[], int ecnt)
{
		for(int i=0; i<ecnt; i++)
		{
			if(!f[i])
				return i;
		}
		return -1;
}

bool tsp::ShortestLinkHeuristic()
{
	struct edge_info *edges = new edge_info[(iCityNum*(iCityNum-1))/2+1];
	struct edge_info *H = new edge_info[iCityNum+1];
	struct link_state *ls = new link_state[iCityNum+1];
	int *degree = new int [iCityNum+1];
	bool *edge_flag  = new bool[(iCityNum*(iCityNum-1))/2+1];
	bool *vst = new bool[iCityNum+1];

	int cost = 0;
	int n = iCityNum;
	int cnt = 0;
	int i, j, u, v, t;
	bool makeloop;

	int conn_num = n-1;
	int edge_index, edge_cnt;
	for(i=0; i<n; i++)
	{
		degree[i] = 0;
		ls[i].neighbor = 0;
		for(j=i+1; j<n; j++)
		{
			edges[cnt].fee = Graph[i][j], edges[cnt].c1 = i, edges[cnt].c2 = j;
			edge_flag[cnt++] = false;
		}
	}

	sort(edges, edges+n*(n-1)/2, cmp);
	edge_index=1;
	edge_cnt = 1;
	cost += edges[0].fee;
	degree[edges[0].c1] = degree[edges[0].c2] = 1;
	ls[ edges[0].c1 ].neighbor = 1; ls[ edges[0].c1 ].p[0] = edges[0].c2;
	ls[ edges[0].c2 ].neighbor = 1; ls[ edges[0].c2 ].p[0] = edges[0].c1;
	
	edge_flag[0] = true;
	cout << edges[0].c1 << " " << edges[0].c2 << endl;

	while(edge_cnt<n )
	{
		edge_index = findaedge(edge_flag, cnt);
		
		u = edges[edge_index].c1, v = edges[edge_index].c2;
		if(degree[u]+1 <3 && degree[v]+1<3) // no cross
		{
			bool bf = ((degree[u]+1) == 2) && ((degree[v]+1) ==2);
			if(!bf)
			{
				H[edge_cnt] = edges[edge_index];
				degree[u]++; degree[v]++;
				cost +=edges[edge_index].fee;
				cout << edges[edge_index].c1 << " " << edges[edge_index].c2 << endl;
				edge_cnt ++;
				edge_flag[edge_index] = true;
				ls[u].p[ ls[u].neighbor++ ] = v;
				ls[v].p[ ls[v].neighbor++ ] = u;
			}
			else
			{
				for(i=0; i<n; i++) vst[i] = false;
				vst[u] = true; vst[v] = true;
				makeloop = false;
				int pre = u, cp = ls[u].p[0];
				while(ls[cp].neighbor ==2)
				{
					if(vst[ cp ])
					{
						makeloop = true;
						break;
					}
					vst[cp] = true;
					
					t = cp;
					if(ls[cp].p[0] != pre) cp = ls[cp].p[0];
					else cp = ls[cp].p[1];
					pre = t;
					
				}
				vst[cp] = true;
			
				pre = v, cp = ls[v].p[0];
				while(!makeloop && ls[cp].neighbor ==2)
				{
					if(vst[ cp ])
					{
						makeloop = true;
						break;
					}
					vst[cp] = true;

					t = cp;
					if(ls[cp].p[0] != pre) cp = ls[cp].p[0];
					else cp = ls[cp].p[1];
					pre = t;	
				}
				
				if(!makeloop || edge_cnt==n-1)
				{
					H[edge_cnt] = edges[edge_index];
					degree[u]++; degree[v]++;
					cost +=edges[edge_index].fee;
					cout << edges[edge_index].c1 << " " << edges[edge_index].c2 << endl;
					edge_cnt ++;
					

					ls[u].p[ ls[u].neighbor++ ] = v;
					ls[v].p[ ls[v].neighbor++ ] = u;
				}
				edge_flag[edge_index] = true;
			}
		}
		else if( (degree[u]+1) ==3 || (degree[v]+1)==3 ) edge_flag[edge_index] = true;
	}
	cout << "cost is " << cost << endl; 

	delete []edges;
	delete []H;
	delete []ls;
	delete []degree;
	delete []vst;
	delete []edge_flag;

	return true;
}

bool tsp::NearestInsertion()
{
	struct node
	{
		int vex;
		node *next;
	};

	int cost = 0, increament, minvex;
	int i, j;
	int n = iCityNum;
	bool *inH = new bool[n];
	int vex_cnt = 0;
	node *H = new node;
	H ->next = H;
	H -> vex = 0;
	node *tp, *minp;
	
	for(i=0; i<n; i++) inH[i] = false;
	inH[0] = true;
	vex_cnt++;

	cout << "0 ";
	while(vex_cnt<n)
	{
		increament = 0x7FFFFFFF;
		minp = tp = H;
		do
		{
			int u = tp->vex, v = tp->next->vex;
			for(j=0; j<n; j++)
			{
				if(!inH[j])
				{
					int t = Graph[u][j] + Graph[j][v] - Graph[u][v];
					if( t < increament)
					{
						increament = t;
						minvex = j;
						minp = tp;
					}
				}
			}
			tp = tp->next;
		}while(tp != H);
		cost += increament;
		cout << minvex << " ";
		inH[minvex] = true;
		tp = new node;
		tp->vex = minvex;
		tp->next = minp->next;
		minp->next = tp;
		vex_cnt++;
	}
	cout << " total cost is " << cost << endl;
	tp = H;
	do
	{
		node * ptr = tp->next;
		free(tp);
		tp = ptr;
	}while(tp!=H);
	delete []inH;
	return true;
}