用回溯法解决旅行商问题

宁夏师范学院数学与计算机科学学院算法分析与设计实验报告实验序号：11 实验项目名称：用回溯法解决旅行商问题 学号姓名专业、班实验地点指导教师时 间2014.06.23一、实验目的及要求（1） 理解算法复杂度的概念（2） 掌握算法复杂度计算的方法二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：Windows XP操作系统、Office2003、多媒体播放软件。三、实验内容与步骤#include#define N 4double cc,/当前路径费用 bestc;/当前最优解费用double aN+1N+1;/邻接矩阵，存放图的信息int bestxN+1;/当前最优解int xN+1;/当前解void inputAjac()int i,j;printf(输入大于0.0的值表示有边,小于0.0表示无边：n);for(i=1;i=N;i+)for(j=i+1;j0.0&axNx10.0)if(bestccc+axN-1xN+axNx1)int j;for(j=1;j=N;j+)bestxj=xj;bestc=cc+axN-1xN+axNx1;elseint j;for(j=i;j0.0)if(bestccc+axi-1xj+axjx1)int temp;cc+=axi-1xj;temp=xi;xi=xj;xj=temp;backtrack(i+1);temp=xi;xi=xj;xj=temp;cc-=axi-1xj;double tsp()/初始化int i;for(i=1;i=N;i+)xi=i;cc=0.0,bestc=-1.0;inputAjac();backtrack(2);return bestc;void output() int i;for(i=1;i=N;i+)printf(%4d,bestxi); printf(n);void main()printf(走%d个城市最少路费为：%lf,N,tsp();printf(走法为:);output();四、实验结果与数据处理五、分析与讨论 旅行售货员问题的解空间是一棵排列树。 在递归算法 backtrack中，当i=n时，当前扩展结点时排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点xn-1到顶点xn的边和一条从顶点xn到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，算法还需判断这条回路的费用是否优于当前已找到的最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。当in时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点xi-1到顶点xi的边时，x1:i构成图G的一条路径，且当x1:i的费用小于当前最优值时算法进入排列树的第i层；否则，将剪去相应的子树。算法中用变量cc记录当前路径x1:i的费用。算法效率：如果不考虑更新bestx所需的计算时间，则算法backtrack需要O(n-1)!)计算时间。由于算法backtrack在最坏情况下可能需要更新当前最优解O(n-