回溯法求解TSP问题.doc

《回溯法求解TSP问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能实验报告实验名称：TSP问题姓名：xxx学号：xxxxx大学计算机学院2014年1月14日一．实验目的掌握递归回溯法的思想，能够求解TSP问题，增强自己的编程能力.二．实验内容下图是5个城市的交通图，城市之间的连线权重表示城市之间路程的费用。要求从A城出发，经过其它城市一次且仅一次，最后回到A城，找出一条费用最低的回路。请用伪代码形式描述所设计的算法。三、回溯法思想：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就

2、退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I

3、回溯法如果城市id=0并且深度等于5？否是通过比较，找到最小的距离否，返回是则返回，输出最小距离，记录最优解四、关键技术：1、使用了递归回溯法，通过递归调用，节省了代码量，使代码更简洁易懂。关键代码：voidBacktracking(intcityId,intdepth,intlen){//正走到的城市的节点号经过的节点数走过的长度if(cityId==0&&depth==5){//如果从A节点出发又回到A节点，且经过刚好走过所有城市所得的长度值较小，则替换minDisif(len<=minDis){minDis=len;sav

4、ePath();}return;}if(len>=minDis){//如果长度值较大，直接回溯选择下一个城市return;}for(inti=0;i

5、ng(tab[cityId][i].second,depth+1,len+tab[cityId][i].first);//递归调用，直到走完5个节点pre[tab[cityId][i].second]=-1;//返回上一层hasVis[tab[cityId][i].second]=false;//false表示没有走过这个城市}}}1、把原问题需要的数据存放在了txt文件当中，通过读取文件来读取题目要求，使得操作更简单关键代码：voidgetTab(){//用户输入城市信息intu,//城市uv,//城市vw;//uv之间的距离

6、//printf("Inputingendsupwith-1-1-1");while(1){fscanf(fp,"%d%d%d",&u,&v,&w);if(u==-1&&v==-1&&w==-1)break;tab[u].push_back(PII(w,v));//对于城市u来说，uv之间的距离是wtab[v].push_back(PII(w,u));//对于城市v来说也是一样}}2、使用了vector容器，更有利于存放子空间的解，避免了使用数组不当造成的相关问题。typedefpairPII;//定义

7、nt,int>类型存放城市的相邻城市和它们之间的费用vectortab[10];tab[u].push_back(PII(w,v));tab[nodeId][i].firsttab[nodeId][i].second六、实验心得1、重温了算法课程里面学过的回溯法，强化了这种编程思想。2、深刻理解了递归调用的思想。3、学习了容器这样一种结构，可以简单的理解为一种数组，但是它有很多有用的方法，很多时候可以直接调用相关函数以减少代码的冗余。4、通过这次实验对TSP算法的C++解法有了进一步的了解，把理论知识应用于实验中。