//用动态规划发解决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;
}
alvarocfc
- 粉丝: 131
- 资源: 1万+
最新资源
- 职工上、下班交通费补贴规定.docx
- 房地产公司圣诞活动策划方案.docx
- 全球旅游与经济指标数据集,旅游影响因素数据集,旅游与收入数据(六千六百多条数据)
- 公司下午茶费用预算.xlsx
- 下午茶.docx
- 毕设和企业适用springboot计算机视觉平台类及在线平台源码+论文+视频.zip
- 2014年度体检项目.xls
- 年度员工体检项目.xls
- 年度体检.xlsx
- 毕设和企业适用springboot跨境电商平台类及虚拟现实体验平台源码+论文+视频.zip
- 毕设和企业适用springboot平台对接类及全球电商管理平台源码+论文+视频.zip
- 数据库-sqlite客户端-sqlite-访问sqlite数据库
- 住宅小区汽车超速检测及报警系统设计(单片机源码+图+报告)
- 毕设和企业适用springboot区块链技术类及客户关系管理平台源码+论文+视频.zip
- 毕设和企业适用springboot区块链技术类及音频处理平台源码+论文+视频.zip
- 毕设和企业适用springboot区块链交易平台类及交通信息平台源码+论文+视频.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
评论0