tsp.cpp

用便宜算法解决旅行商问题

#include <iostream.h>
#include <stdlib.h>
#include <fstream.h>
#include <math.h>
#define PRE temp->pre->vertex*count
#define NEXT temp->next->vertex*count
#define VER temp->vertex*count

struct Node
{
	int vertex;
	Node *next;
	Node *pre;
};

struct List
{
	Node *head;
	Node *tail;
	int num;
};

void main()
{
	int *s,*graph;             //s数组用以存储尚不在图中的顶点，graph数组用以存储邻接矩阵
	int count,min;
	int sum;
	Node *node,*temp;
	List list;                 //用链表存储最终得到的回路


/***************************读取存储在“test.txt”中的测试用邻接矩阵*****************/
	ifstream file;
	file.open("test.txt");       
	if(!file)
	{
		cout<<"文件打开失败"<<endl;
		exit(0);
	}


	cout<<"输入顶点个数:"<<endl;
	cin>>count;
	graph=new int[count*count];
	s=new int[count];
	for(int i=0;i<count;i++)
	{
		s[i]=i;
	}

	for(i=0;i<count*count;i++)
	{
		file>>graph[i];
	}

/***************************将测试用邻接矩阵输出到屏幕****************************/
	cout<<"测试用图的邻接矩阵为："<<endl;
	for(int j=0;j<i;j++)
	{
		if(j!=0&&j%count==0)
		{
			cout<<endl;
		}
		cout<<graph[j]<<"  ";
	}

	node=new Node;
	list.head=list.tail=node;
	list.head->vertex=0;

/**************寻找要插入的顶点并判断插入位置，然后将其插入链表**************/
while(i!=count)
{
	if(list.head==list.tail)
	{
		min=1;
		for(i=1;i<count;i++)
		{
			if(graph[min]>graph[s[i]])
			{
				min=s[i];
			}
		}
		s[min]=0;
		node=new Node;
		node->vertex=min%count;
		list.tail=node;
		list.tail->next=list.head;
		list.tail->pre=list.head;
		list.head->next=list.head->pre=list.tail;
	}
	else
	{
		for(temp=list.head,i=0;i<count;i++)
		{
			if(s[i]>0)
			{
				if(graph[min]>graph[s[i]])
				{
					min=s[i];
				}
			}
		}
		for(temp=list.head->next;temp!=list.head;temp=temp->next)
		{
		
			for(i=0;i<count;i++)
			{
				if(s[i]>0)
				{
					if(graph[min]>graph[VER+s[i]]&&graph[VER+s[i]]!=0)
					{
						min=temp->vertex*count+s[i];
					}
				}
			}
		}
		s[min%count]=0;
		temp=list.head;
		do
		{
			if(temp->vertex==min/count)
			{
				if(abs(graph[PRE+min%count]-graph[PRE+temp->vertex])<=abs(graph[NEXT+min%count]-graph[NEXT+temp->vertex]))
				{
					node=new Node;
					node->vertex=min%count;
					node->next=temp;
					node->pre=temp->pre;
					temp->pre->next=node;
					temp->pre=node;
				}
				else
				{
					node=new Node;
					node->vertex=min%count;
					node->next=temp->next;
					node->pre=temp;
					temp->next->pre=node;
					temp->next=node;
				}
			}
			temp=temp->next;
		}
		while(temp!=list.head);
	}

	for(i=0;i<count;i++)
	{
		if(s[i]>0)
		{
			min=s[i];
			break;
		}
	}
	
}

/*********************输出最终的回路和回路的总权值***********************/
	cout<<endl<<"回路为：";
	sum=0;
	temp=list.head;
	do
	{
		cout<<"(V"<<temp->vertex+1<<")"<<"-"<<graph[temp->vertex*count+temp->next->vertex]<<"-";
		sum=sum+graph[temp->vertex*count+temp->next->vertex];
		temp=temp->next;
	}
	while(temp!=list.head);
	cout<<"(V1)"<<endl;
	cout<<"总权值为："<<sum<<endl;
}