assignment2.cpp

实现了TSP算法。TSP是算法课上讲的一个经典算法

#include <stdio.h>
#include <fstream>
#include <iostream>
#include <time.h>

using namespace std;
#define MAX_DIS 9999
#define MAX_VAL 1200
#define Final 50
int a[50][50];
int b[50][50];
fstream m1, m2;
struct node {
	int v;
	int val;
	int dis;
	node * parent;
// 	node * child[50];
// 	int n;
};

node * queue[20000];
int front, rear;
node * searchnode(int &k);	

int main()
{
	clock_t start, end;
	start = clock();
	m1.open("m1.txt");
	m2.open("m2.txt");
	for(int i = 0; i < 50; i++)
	{
		for(int j = 0; j < 50; j++)
		{
			m1 >> a[i][j];
			m2 >> b[i][j];
		}
	}

	/*
	int n = 50;
	bool s[50] = {false};
	int dist[50];
	int val[50];
	int prev[50];
	
	for(i = 0; i < n; i++)
	{
		dist[i] = a[0][i];
		val[i] = b[0][i];
		if(dist[i] == MAX_VALUE)
			prev[i] = -1;
		else
			prev[i] = 0;
	}

	dist[0] = 0; s[0] = true;
	*/
	
	// 搜索树的根结点
	node * s = new node;
// 	s->n = 0;
	s->dis = 0;
	s->parent = NULL;
// 	for(i = 0; i < 50; i++)
// 		T.child = NULL;
	s->v = 0;
	s->val = 0;
	// 距离上届，用于剪枝
	int upperDis = MAX_DIS-1;
	int upperVal = MAX_VAL;
	front = rear = -1;
	// 搜索树初始化
 	queue[++front] = s;
	node * result = s;
	int route[50], n;
	int valM[50];
	int disM[50];
	for(i = 0; i < 50; i++)
	{
		valM[i] = MAX_VAL;
		disM[i] = MAX_DIS;
	}
	valM[0] = 0;
	disM[0] = 0;
	int k = 0;

	while(front != rear) {
		// 使用优先级找到当前扩展节点
		node * t = searchnode(k);
		queue[k] = queue[++rear];
// 		node * t = queue[++rear];
		int v = t->v;
		int j = 0;
		for(i = 0; i < 50; i++)
		{
			bool flag = true;
			node * p = t;
			while(p != NULL)
			{
				if (i == p->v)
				{
					flag = false;
					break;
				}
				p = p->parent;
			}
			// 可扩展节点
			if (a[v][i] < MAX_DIS && flag)
			{
// 				
// 				st->dis = s->dis + a[t][i];
// 				st->n = 0;
// 				st->parent = s;
// 				st->v = i;
// 				st->val = s->val + b[t][i];
				// 距离和养路费上剪枝
				if (t->dis + a[v][i] <= upperDis && t->val + b[v][i] <= MAX_VAL)
				{
					if (t->dis + a[v][i] < disM[i]/* || t->val + b[v][i] < valM[i]*/)
					{
						node * st = new node;
						st->dis = t->dis + a[v][i];
						st->val = t->val + b[v][i];
						st->parent = t;
						st->v = i;
						
						// 修改上届
						if(st->dis + a[st->v][Final-1] <= upperDis && st->val + b[st->v][Final-1] <= MAX_VAL)
						{
							upperDis = st->dis + a[st->v][Final-1];
							upperVal = st->val + b[st->v][Final-1];
							result = st;
						}	
						if (t->dis + a[v][i] < disM[i] && t->val + b[v][i] < valM[i])
						{
							disM[i] = st->dis;
							valM[i] = st->val;
						}
						queue[++front] = st;
					}
					
				}
				
			}	
		}
	}
	route[0] = Final-1;
	n = 1;
	node * p = result;
	while(p != NULL)
	{
		route[n++] = p->v;
		p = p->parent;
	}
	cout << "route: ";
	while(n > 0)
		cout << route[--n]+1 << " ";
	cout << endl << "distance: " << upperDis << endl;
	cout << "cost: " << upperVal << endl;
	end = clock();
	cout << end - start << endl;

	return 0;
}

node* searchnode(int &k)
{
	int distemp = queue[rear+1]->dis;
	node * ret = queue[rear+1];
	k = rear+1;
	for(int i = rear + 2; i <= front; i ++)
	{
		if(queue[i]->dis < distemp )
		{
			ret = queue[i];
			distemp = queue[i]->dis;
			k = i;
		}
	}
	return ret;
}