tsp_dp.cpp

用动态规划方法手工和编程求解下面的问题

#include <list>
#include <iostream>
#include <string>

using namespace std ;
typedef list<int> LISTINT;

typedef struct  {
	int minDist;					//最短距离
	LISTINT path;					//最优路径
} minPath;							

#define N 6							//输入矩阵大小
#define MAX 65535
int D[N][N]={{0,10,20,30,40,50},	//输入邻接矩阵D
			{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}};

minPath TSP(int i, LISTINT S)
{
	int dist,min=MAX;			
	int nextcity;					//保存最优路径上，S中的第一个城市
	minPath temp1,temp;				//用于保存中间结果以及处理返回值
	
	if(S.empty())
	{
		temp.minDist=D[i][0];
		temp.path.push_back(0);
 		return temp;
	}
	
	for(int n=S.size();n>0;n--)		//循环n次，每次取出一个元素
	{
		LISTINT Sub(S);			
		int j=S.front();			//取出S中第一个元素j
		S.pop_front();				
		S.push_back(j);				//S中元素循环左移1位
		Sub.pop_front();			//Sub = S\{j}

		temp1.path.clear();					
		temp1=TSP(j,Sub);				
		dist = D[i][j]+temp1.minDist;
		if(dist<min)						//寻找i出发，经过S中每个城市一次
		{									//且仅一次并最后返回城市i的最短距离
			min=temp.minDist=dist;		
			temp.path.clear();
			while(!temp1.path.empty()){	
				temp.path.push_back(temp1.path.front());
				temp1.path.pop_front();
			}
			nextcity=j;						
		}	
	}
	temp.path.push_back(nextcity);
	return temp;
}


void PrintPath(minPath p)				//打印结果
{
	cout<<"The shortest distance is: ";
	cout<<p.minDist<<endl;
	cout<<"The best path is: ";
	cout<<"v1";
	while(!p.path.empty()){
		cout<<"->v"<<(p.path.back()+1);
		p.path.pop_back();
	}
	cout<<endl;
}


void main()
{
	LISTINT S;
	for(int i=1;i<N;i++)		//初始化集合S
		S.push_back(i);			//v1,v2,v3,v4,v5,v6 分别对应 0,1,2,3,4,5,6

	PrintPath(TSP(0,S));
}