dp_tsp.cpp

TSP问题的动态规划求解。问题描述：旅行商问题

//用动态规划发解决TSP问题代码：
#include <iostream>
#include <set>
#include <vector>
#define MAX 6
using namespace std;
int dis[MAX][MAX]={{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}};
	typedef struct
	{
		int curcity;//当前所在的城市
		vector<int> unvisited;//当前未访问的城市
		set<int> type;//由于set自动排序，相同状态的vector可能不同，但set必然相同
		int distance;//从当前城市到终点回到起点的距离
	}status;
/*/**********测试用*************/
	void printVec(vector<status> vec)
	{
		vector<status>::iterator iter;
		vector<int>::iterator it;
		for(iter=vec.begin();iter!=vec.end();iter++)
		{    
			cout<<(*iter).curcity<<" <";
			for(it=(*iter).unvisited.begin();it!=(*iter).unvisited.end();it++)
			{
				cout<<*it<<" ";
			}
			cout<<">"<<"  distance:"<<(*iter).distance<<endl;
		}
	}
	bool contain(int i, status &sta) //看看当前状态的城市中是否包括城市i
	{
		vector<int>::iterator iter;
		if(i==sta.curcity)
			return true;
		else
		{
			for(iter=sta.unvisited.begin();iter!=sta.unvisited.end();iter++)
				if(i==*iter)
					return true;
		}
		return false;
	}
	vector<status> combine(vector<status> vec) /**//*合并相同状态*/
	{
		vector<status> new_vec;
		vector<status>::iterator iter;
		status temp;
		while(vec.size()>0)
		{
			iter=vec.begin();
			temp=*iter;
			vec.erase(iter);
			for(;iter!=vec.end();iter++)
			{
				if((temp.curcity==(*iter).curcity)&&(temp.type==(*iter).type))
				{
					if((*iter).distance<temp.distance)
						temp=*iter;
					iter=vec.erase(iter);
					iter--;
				}
			}
			new_vec.push_back(temp);
		}
		return new_vec;
	}
	int main()
	{
		vector<status> pre_vector;
		vector<status> cur_vector;
		//从后往前推，初始化
		for(int i=1;i<MAX;i++)
		{
			status sta;
			sta.curcity=i;
			sta.distance=dis[i][0];
			cur_vector.push_back(sta);
		}
		//依次递推，递推MAX-2次
		for(int j=0;j<MAX-2;j++)
		{    
			pre_vector=cur_vector;
			cur_vector.clear();
			for(int i=1;i<MAX;i++)
			{
				vector<status>::iterator iter;
				for(iter=pre_vector.begin();iter!=pre_vector.end();iter++)
				{
					status temp=*iter;
					if(contain(i,temp)==false)//为确保状态中没有重复路径
					{
						status new_stat=temp;
						vector<int>::iterator int_iter=new_stat.unvisited.begin();
						new_stat.unvisited.insert(int_iter,new_stat.curcity);//加入vector
						new_stat.type.insert(new_stat.curcity);//加入set
						new_stat.distance+=dis[i][new_stat.curcity];//计算距离
						new_stat.curcity=i;
						cur_vector.push_back(new_stat);    
					}
				}
			}
			cur_vector=combine(cur_vector); //记录相同状态最短路径，并合并相同状态
		}//end for
/**/	printVec(cur_vector);
		//递推完毕后，最后一步，计算起点到每个状态的距离，找到最短路径
		vector<status>::iterator iter=cur_vector.begin();
		status shortest=*iter;
		int min_dis=shortest.distance+dis[0][shortest.curcity];
		iter++;
		for(;iter!=cur_vector.end();iter++)
		{
			int temp_dis=dis[0][(*iter).curcity]+(*iter).distance;
			if(temp_dis<min_dis)
			{
				min_dis=temp_dis;
				shortest=*iter;
			}    
		}
		//打印结果
		vector<int>::iterator iter_city;
		cout<<"minimum distance is "<<min_dis<<endl;
		cout<<"the shortest path is "<<"1 "<<shortest.curcity+1;
		for(iter_city=shortest.unvisited.begin();iter_city!=shortest.unvisited.end();iter_city++)
			cout<<" "<<*iter_city+1;
		cout<<" 1"<<endl;
		return 0;
	}