回溯法求旅行售货员问题_物联1301班_刘悦_201308080112.doc

《回溯法求旅行售货员问题_物联1301班_刘悦_201308080112.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第X次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309实验名称回溯法求旅行售货员问题实验目的通过上机实验，掌握回溯算法的思想，利用回溯法求旅行售货员问题并实现。实验原理旅行售货员问题的解空间树是一棵排列树。当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。如果是，则必须更新当

2、前最优值bestc和当前最优解bestx。当i

3、则更新最优费用，同时记录最优解。关键代码//定义图的顶点数constintN=4;/*=================================================================定义Traveling类来存储的信息。=================================================================*/templateclassTraveling{templatefriendTTSP(T**a,intn);private:voidBacktra

4、ck(inti);intn,//图G的顶点数*x,//当前解*bestx;//当前最优解Type**a,//图G的领接矩阵cc,//当前费用bestc;//当前最优值intNoEdge;//无边标记};/*=================================================================Backtrack函数为递归算法。当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，

5、算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。当i

6、voidTraveling::Backtrack(inti){//前扩展结点是排列树的叶结点的父结点if(i==n){//检测是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边//存在且这条回路的费用小于已找到的最优费用if(a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]

7、

8、bestc==0)){//记录最优解for(intj=1;j<=n;j++)bestx[j]=x[j];//更新最优费用bestc=cc+a[x[n-1]]

9、[x[n]]+a[x[n]][1];}}//前扩展结点位于排列树的第i-1层else{for(intj=i;j<=n;j++){//判断是否可进入x[j]子树if(a[x[i-1]][x[j]]!=0&&(cc+a[x[i-1]][x[i]]

10、

11、bestc==0)){//搜索子树//交换inttemp=x[i];x[i]=x[j];x[j]=temp;//当前费用累加cc+=a[x[i-1]][x[i]];//排列向右扩展,排列树向下一层扩展Backtrack(i+1);//当前费用减少cc-=a[x[i-1]][x[i]];//交换temp=x[i]

12、;x[i]