算法分析与设计实验报告第 X 次实验姓名刘悦学号班级物联1301班时间12.26上午地点工训楼C栋309 实验名称回溯法求旅行售货员问题实验目的通过上机实验，掌握回溯算法的思想，运用回溯法求旅行售货员问题并实现实验原理旅行售货员问题的解空间树是一棵排列树当i=n时，目前扩展结点是排列树的叶结点的父结点此时算法检测图G与否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边如果这两条边都存在，则找到一条旅行售货员回路此时，算法还需要判断这条回路的费用与否优于已找到的目前最优回路的费用bestc如果是，则必须更新目前最优值bestc和目前最优解bestx 当i ④ 若均有边相连，则检测此回路的费用与否不不小于最优费用⑤ 若不不小于最优费用，则更新最优费用，同步记录最优解核心代码//定义图的顶点数 const int N = 4; /*=================================================================定义Traveling类来存储的信息/ template class Traveling { template friend T TSP(T **a, int n); private: void Backtrack(int i); int n, // 图G的顶点数 *x, // 目前解 *bestx; // 目前最优解 Type **a, // 图G的领接矩阵 cc, // 目前费用 bestc; // 目前最优值 int NoEdge; // 无边标记 }; /*=================================================================Backtrack函数为递归算法。 当i=n时，目前扩展结点是排列树的叶结点的父结点此时算法检测图G与否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边如果这两条边都存在，则找到一条旅行售货员回路此时，算法还需要判断这条回路的费用与否优于已找到的目前最优回路的费用bestc如果是，则必须更新目前最优值bestc和目前最优解bestx 当i void Traveling::Backtrack(int i) { //前扩展结点是排列树的叶结点的父结点 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] < bestc || bestc == 0)) { //记录最优解 for (int j = 1; j <= n; j++) bestx[j] = x[j]; //更新最优费用 bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1]; } } //前扩展结点位于排列树的第i-1层 else { for (int j = i; j <= n; j++) { // 判断与否可进入x[j]子树 if (a[x[i-1]][x[j]] != 0 && (cc + a[x[i-1]][x[i]] < bestc || bestc == 0)) { // 搜索子树 //互换 int temp=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]; x[i]=x[j]; x[j]=temp; } } } } /*=================================================================TSP函数进行初始化，并返回最短途径的长度。 重要为使用Backtrack函数进行搜索 =================================================================*/ template Type TSP(Type **a, int n) { //定义traveling类型的变量Y Traveling Y; //初始化Y Y.n=n; Y.x=new int[n+1]; Y.bestx=new int[n+1]; //置x为单位排列 for(int i=1;i<=n;i++) { Y.x[i]=i; } Y.a=a; Y.cc=0; Y.bestc=0; Y.NoEdge=0; //搜索x[2:n]的全排列 Y.Backtrack(2); //输出最短回路 cout<<"最短回路为："< "; } cout< 需要注意的是形参那里一定要使用&符号，否则的话修改之后的成果不会在其她函数中看到 =================================================================*/ template inline void Swap(Type &a, Type &b) { Type temp=a; a=b; b=temp; } 测试成果1. 使用的图如下所示：2. 相应的排列树如下所示：3. 至个叶结点的途径叶结点途径长度途径顺序L591 -->2 -->3 -->4-->1M661 -->2 -->4 -->3-->1N251 -->3 -->2 -->4-->1O661 -->3 -->4-->2-->1P251 -->4 -->2 -->3-->1Q591 -->4 -->3 -->2-->14. 由上表可以懂得最短的为至叶结点Q的途径1 -->3 -->2 -->4-->1，长度为25这里也许会有疑问，至结点P的距离也为25，为什么不选择途径1 -->4 -->2 -->3-->1。 这是由于只有当求得的途径比目前最优值小的时候才会记录，这里同样大，因此不会记录，也就不会输出这条途径5. 算法输出成果如下：输出时间输出源结点到目的结点的最短途径的长度输出源结点到目的结点的最短途径输入起点与终点，即源结点与目的结点6. 可以看到输出的成果与分析的成果同样，因此算法实现对的并且可以看到分支限界法在实现我们给的这个图的时候，时间性能较好实验心得由于我自己觉得解空间为排列树的问题的算法不是较好理解，因此就多编写了旅行售货员问题的代码，这里使用的是回溯法实现就整体上来说，我觉得回溯法的思想还是较好理解的，就是扩展一种结点的子结点，继续扩展子结点的子结点，当不能扩展的时候，就返回到上一种扩展结点，找其她的子结点进行扩展，当往回找到根结点，根结点没有子结点继续扩展的时候，就结束算法但是这里是排列树的回溯法，就难理解一点重要是使用了互换void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[。
④ 若均有边相连，则检测此回路的费用与否不不小于最优费用⑤ 若不不小于最优费用，则更新最优费用，同步记录最优解核心代码//定义图的顶点数 const int N = 4; /*=================================================================定义Traveling类来存储的信息/ template class Traveling { template friend T TSP(T **a, int n); private: void Backtrack(int i); int n, // 图G的顶点数 *x, // 目前解 *bestx; // 目前最优解 Type **a, // 图G的领接矩阵 cc, // 目前费用 bestc; // 目前最优值 int NoEdge; // 无边标记 }; /*=================================================================Backtrack函数为递归算法。
当i=n时，目前扩展结点是排列树的叶结点的父结点此时算法检测图G与否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边如果这两条边都存在，则找到一条旅行售货员回路此时，算法还需要判断这条回路的费用与否优于已找到的目前最优回路的费用bestc如果是，则必须更新目前最优值bestc和目前最优解bestx 当i void Traveling::Backtrack(int i) { //前扩展结点是排列树的叶结点的父结点 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] < bestc || bestc == 0)) { //记录最优解 for (int j = 1; j <= n; j++) bestx[j] = x[j]; //更新最优费用 bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1]; } } //前扩展结点位于排列树的第i-1层 else { for (int j = i; j <= n; j++) { // 判断与否可进入x[j]子树 if (a[x[i-1]][x[j]] != 0 && (cc + a[x[i-1]][x[i]] < bestc || bestc == 0)) { // 搜索子树 //互换 int temp=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]; x[i]=x[j]; x[j]=temp; } } } } /*=================================================================TSP函数进行初始化，并返回最短途径的长度。
重要为使用Backtrack函数进行搜索 =================================================================*/ template Type TSP(Type **a, int n) { //定义traveling类型的变量Y Traveling Y; //初始化Y Y.n=n; Y.x=new int[n+1]; Y.bestx=new int[n+1]; //置x为单位排列 for(int i=1;i<=n;i++) { Y.x[i]=i; } Y.a=a; Y.cc=0; Y.bestc=0; Y.NoEdge=0; //搜索x[2:n]的全排列 Y.Backtrack(2); //输出最短回路 cout<<"最短回路为："< "; } cout< 需要注意的是形参那里一定要使用&符号，否则的话修改之后的成果不会在其她函数中看到 =================================================================*/ template inline void Swap(Type &a, Type &b) { Type temp=a; a=b; b=temp; } 测试成果1. 使用的图如下所示：2. 相应的排列树如下所示：3. 至个叶结点的途径叶结点途径长度途径顺序L591 -->2 -->3 -->4-->1M661 -->2 -->4 -->3-->1N251 -->3 -->2 -->4-->1O661 -->3 -->4-->2-->1P251 -->4 -->2 -->3-->1Q591 -->4 -->3 -->2-->14. 由上表可以懂得最短的为至叶结点Q的途径1 -->3 -->2 -->4-->1，长度为25这里也许会有疑问，至结点P的距离也为25，为什么不选择途径1 -->4 -->2 -->3-->1。 这是由于只有当求得的途径比目前最优值小的时候才会记录，这里同样大，因此不会记录，也就不会输出这条途径5. 算法输出成果如下：输出时间输出源结点到目的结点的最短途径的长度输出源结点到目的结点的最短途径输入起点与终点，即源结点与目的结点6. 可以看到输出的成果与分析的成果同样，因此算法实现对的并且可以看到分支限界法在实现我们给的这个图的时候，时间性能较好实验心得由于我自己觉得解空间为排列树的问题的算法不是较好理解，因此就多编写了旅行售货员问题的代码，这里使用的是回溯法实现就整体上来说，我觉得回溯法的思想还是较好理解的，就是扩展一种结点的子结点，继续扩展子结点的子结点，当不能扩展的时候，就返回到上一种扩展结点，找其她的子结点进行扩展，当往回找到根结点，根结点没有子结点继续扩展的时候，就结束算法但是这里是排列树的回溯法，就难理解一点重要是使用了互换void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[。
需要注意的是形参那里一定要使用&符号，否则的话修改之后的成果不会在其她函数中看到 =================================================================*/ template inline void Swap(Type &a, Type &b) { Type temp=a; a=b; b=temp; } 测试成果1. 使用的图如下所示：2. 相应的排列树如下所示：3. 至个叶结点的途径叶结点途径长度途径顺序L591 -->2 -->3 -->4-->1M661 -->2 -->4 -->3-->1N251 -->3 -->2 -->4-->1O661 -->3 -->4-->2-->1P251 -->4 -->2 -->3-->1Q591 -->4 -->3 -->2-->14. 由上表可以懂得最短的为至叶结点Q的途径1 -->3 -->2 -->4-->1，长度为25这里也许会有疑问，至结点P的距离也为25，为什么不选择途径1 -->4 -->2 -->3-->1。
这是由于只有当求得的途径比目前最优值小的时候才会记录，这里同样大，因此不会记录，也就不会输出这条途径5. 算法输出成果如下：输出时间输出源结点到目的结点的最短途径的长度输出源结点到目的结点的最短途径输入起点与终点，即源结点与目的结点6. 可以看到输出的成果与分析的成果同样，因此算法实现对的并且可以看到分支限界法在实现我们给的这个图的时候，时间性能较好实验心得由于我自己觉得解空间为排列树的问题的算法不是较好理解，因此就多编写了旅行售货员问题的代码，这里使用的是回溯法实现就整体上来说，我觉得回溯法的思想还是较好理解的，就是扩展一种结点的子结点，继续扩展子结点的子结点，当不能扩展的时候，就返回到上一种扩展结点，找其她的子结点进行扩展，当往回找到根结点，根结点没有子结点继续扩展的时候，就结束算法但是这里是排列树的回溯法，就难理解一点重要是使用了互换void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[。
