tsp.cpp

本程序利用动态规划的思想实现了经典的旅行商问题

// TSP.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "math.h"

#define MAX 100000
#define VER_NUM 6 //表示城市个数
#define PROC  5   //表示寻找回路的步骤次数

//初始的路径信息
int cost_array[VER_NUM][VER_NUM]={
	{0,10,20,30,40,50},
	{12,0,18,30,25,21},
	{23,19,0,5,10,15},
	{34,32,4,0,8,16},
	{45,27,11,10,0,18},
	{56,22,16,20,12,0}};

//int cost_array[VER_NUM][VER_NUM]={{0,10,15,20},{5,0,9,10},{6,13,0,12},{8,8,9,0}};


//对于每一节点当前最小路径信息
struct min_road
{
	int dest;//要通过的节点的标号
	int res;//最小路径中与要通过节点相联的节点标号
	bool road_code[PROC];//当前最短路径中包含的节点标号
	int cost;//当前最短路径的代价
	struct min_road *next;//指向下一个具有路径节点个数相同的最小路径信息
};

//在每一阶段中各节点(不包含初始节点)所对应的最小路径信息索引
struct vertex
{
	int ver_num;
	min_road *next;
};

//各阶段各节点的信息索引数组
vertex vertex_array[PROC][PROC];

//最终的回到出发点的最小路径信息
min_road* terminate;


//复制最小路径信息
void copy_road(bool road1[PROC],bool road2[PROC])
{
	for(int i=0;i<PROC;i++)
		road1[i]=road2[i];
}

//比较两最小路径信息是否相同
bool compare_road(bool road1[PROC],bool road2[PROC])
{
	bool isequal=true;
	for(int i=0;i<PROC;i++)
	{
		if(road1[i]!=road2[i])
			isequal=false;
	}
	return isequal;
}

//计算从起始点到最后一个步骤的所有候选最短路径
//void TSP(vertex* head[VER_NUM],int cost_array[VER_NUM][VER_NUM])
min_road* TSP(vertex vertex_array[PROC][PROC],int cost_array[VER_NUM][VER_NUM])
{
	/*i表示在第i步骤中要求计算出的每个节点的最小路径信息中路径所包含的元素个数
	  j表示在第i步骤中计算第j个节点（不含起始点）的最小路径状态信息*/
	for(int i=0;i<PROC;i++)
	{
		//head[i]=vertex_array[i];
		min_road *p,*q,*r,*s,*t;
		bool temp_road[PROC]={0,0,0,0,0};
		int m;
		for(int j=1;j<VER_NUM;j++)
		{
			vertex_array[i][j-1].ver_num=j;
			vertex_array[i][j-1].next=NULL;
			//初始化最小路径集合元素为空时的每一个节点的信息
			if(i==0)
			{
				p=new min_road();
				p->dest=j;
				p->res=0;
				p->cost=cost_array[j][0];
				copy_road(p->road_code,temp_road);
				p->next=NULL;
				if(vertex_array[i][j-1].next==NULL)
					vertex_array[i][j-1].next=q=p;
				else
				{
					q->next=p;
					q=p;
				}
			}
			else
			{
				for(int k=0;k<PROC;k++)
				{
					//对于每一个当前路径集合元素个数为i-1且不包含j的最小路径进行遍历
					if((k+1)!=j)
					{
						r=vertex_array[i-1][k].next;
						while(r!=NULL)
						{
							//如果该路径不包含节点j
							if(r->road_code[j-1]==0)
							{
								for(m=1;m<VER_NUM;m++)
								{
										if(r->road_code[m-1]==0 && m!=j)
										{
										//在集合元素个数为i-1的所有最小路径中查找g(m,r->road_code),并比较求出在该集合下的路径代价最小者
											copy_road(temp_road,r->road_code);
											temp_road[m-1]=1;
											t=vertex_array[i][j-1].next;
											s=vertex_array[i-1][m-1].next;
											while(compare_road(s->road_code,r->road_code)!=true)
												s=s->next;
											while(t!=NULL)
											{
												if(compare_road(temp_road,t->road_code)==true)
												{
													if((cost_array[j][m]+s->cost)<t->cost)
													{
														t->res=m;
														t->cost=cost_array[j][m]+s->cost;
														copy_road(t->road_code,temp_road);
													}
													break;
												}
												else
													t=t->next;	
											}
											if(t==NULL)
											{
												p=new min_road();
												p->dest=j;
												p->next=NULL;
												p->res=m;
												p->cost=cost_array[j][m]+s->cost;
												copy_road(p->road_code,s->road_code);
												p->road_code[m-1]=1;
												if(vertex_array[i][j-1].next==NULL)
													vertex_array[i][j-1].next=q=p;
												else
												{
													q->next=p;
													q=p;
												}
											}
										}
								}
							}
							r=r->next;
						}
					}
				}
			}
		}
	}
	//计算最后一步回路过程
	min_road* terminate=new min_road();
	terminate->dest=0;
	terminate->road_code[0]=terminate->road_code[1]=terminate->road_code[2]=terminate->road_code[3]=terminate->road_code[4]=1;
//	terminate->road_code[0]=terminate->road_code[1]=terminate->road_code[2]=1;
	terminate->next=NULL;
	int min_cost=MAX;
	for(i=0;i<PROC;i++)
	{
		if((cost_array[0][i+1]+vertex_array[PROC-1][i].next->cost)<min_cost)
		{
			terminate->cost=cost_array[0][i+1]+vertex_array[PROC-1][i].next->cost;
			terminate->res=i+1;
			min_cost=terminate->cost;
		}
	}
	return terminate;
}

void display_road(vertex vertex_array[PROC][PROC],min_road *terminate,int cost_array[VER_NUM][VER_NUM])
{
	cout<<"The min_cost is "<<terminate->cost<<endl;
	cout<<" The min_cost path is"<<endl;
	int res,dest;
	min_road* p;
	bool temp_road[PROC]={1,1,1,1,1};
	int temp_cost;
	for(int i=PROC;i>=0;i--)
	{
		if(i==PROC)
		{
			dest=0;
			res=terminate->res;
			temp_cost=terminate->cost-cost_array[dest][res];
		}
		else
		{
			dest=res;
			temp_road[dest-1]=0;
			p=vertex_array[i][dest-1].next;
			while(p!=NULL)
			{
				if((compare_road(temp_road,p->road_code)&& temp_cost==p->cost)==true)
				{
					res=p->res;
					temp_cost=p->cost-cost_array[dest][res];
					break;
				}
				p=p->next;
			}
		}
		cout<<"   "<<dest<<"--"<<res<<endl;
	}
}

//输出初始有向图
void output(int cost_array[VER_NUM][VER_NUM])
{
	
	for(int i=0;i<VER_NUM;i++)
	{
		for(int j=0;j<VER_NUM;j++)
			cout<<"  "<<cost_array[i][j];
		cout<<endl;
	}
}

int main(int argc, char* argv[])
{
	cout<<endl;
	cout<<"**************利用动态规划解决旅行商问题****************"<<endl;
	cout<<endl;
	cout<<"初始有向图为："<<endl;
	output(cost_array);
	cout<<endl;
	terminate=TSP(vertex_array,cost_array);
	display_road(vertex_array,terminate,cost_array);
	cout<<"*************演示结束**************"<<endl;
	return 0;
}