课程编号：C0801003130算法分析与设计实验报告姓名学号班级指导教师实验名称算法分析与设计开设学期20 -20 第一学期开设时间第9周——第17周报告日期评定成绩评定人评定日期东北大学软件学院一、实验目的写出你认为比较重要的实验目的理解回溯法的思想和本质掌握一些经典问题的解决方法二、实验内容简短明确地写出实验的内容旅行收货商问题问题描述假设一个旅行商人要拜访n个城市，他必须选择这样一条路径，路径中每个城市只能拜访一次且仅一次，然后回到出发的城市，路径的选择目标是要求得的路径长度为所有路径之中的最小值。
编程任务利用回溯法设计一个算法求出该问题的解数据输入和输出邻接矩阵的初始化值input.txt提供将计算出的最优值和最优解输出到output.txt中n后问题问题描述在n×n格的棋盘上放置彼此不受攻击的n个皇后。
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
N皇后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
编程任务利用回溯法设计一个算法，求出n后问题的解。
数据输入和输出皇后的个数n由input.txt提供将程序求出的解输出到output.txt中三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号操作系统：Windows 10 1809调试软件：Microsoft Visual Studio 2017上机地点：信息A415机器台号：HP笔记本电脑四、问题分析 (对三个实验分别写出该问题，以下问题同)分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
问题分析1、旅行收货商问题此题是一个求最小汉密尔顿回路问题，已知用回溯法解决，该问题的解空间可以组织成排列树形式（4个结点的情况）：本程序设计的基本思想为：深度遍历该排列树，遍历下一层结点时，判断下一层结点的权值与当前解的和是否比最优解差。
若比最优解好，继续遍历，若比最优解差，不继续遍历，遍历下一个解，当遍历到叶子节点时，得到的解与最优解比较，得到的解较优，更新最优解，得到的解较差，不进行任何操作，枚举结束，打印结果。
流程图表示：2、n后问题n后问题的解空间同样可以组织成排列树，树的第i层代表第i个皇后，结点的值代表皇后在棋盘的第i行的位置，分析得出本题的约束条件为：对于每个皇后，不能与其他皇后处于同一列或对角的位置。
本程序设计的基本思想为：对于第i个皇后的放置，对于第i行的每个位置，检查前i-1行的每个皇后是否与这个有冲突，若没有，进入下一个皇后的放置，若有，进入回溯过程。
当摆放完最后一个皇后后，打印所有可能的结果。
流程图如下：分析利用你的想法解决该问题可能会有怎样的时空复杂度。
旅行收货商问题排列树问题，因为第一个结点已经选定，对于第二个节点有（n-1）选择，一直到最后一个结点，有1种选择，时间复杂度为O((n-1)!)，空间复杂度为,为邻接矩阵的大小。
n后问题对于n个皇后，每个皇后有n种排放方法，时间复杂度为，空间复杂为O(n)用一维数组存储每个皇后在棋盘上位置。
因为约束函数的存在，计算过程种会“剪掉”一些不必要的解，时间复杂度会远低于理论值。
其它（你认为需要在此说明的）五、问题解决根据对问题的分析，写出解决办法。
旅行收货商问题使用三个一维数组currPath,bestPath, set，分别存储当前解，最优解和选过的结点，一个二维数组dest存储邻接矩阵，两个变量currCost和bestCost存储当前费用和最优费用。
首先，从文件读出并初始化dest，然后使用回溯法计算最优解，当结点被选中，set种将对应索引的值置为1，示意已被选过，当currCost<bestCost时，更新，bestCost，每次到达叶子节点，就判断是否有更好解。
运算结束后，将最优解和最优值输出到文件中。
n后问题使用一个一维数组status，存储第i个皇后在第i行的位置，用一个变量sum保存解的个数，每次到达叶子结点，都将解以追加的形式输出到文件中，sum的值更新。
描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
旅行收货商问题主要函数 void traceback(int level)核心代码：if (level == num)//到达叶子节点，保存结果{if (currCost < bestCost) //计算出新最优值{memcpy(bestPath, currPath, num sizeof(int));bestCost = currCost +dest[bestPath[num - 1]][bestPath[0]];//更新最优值}return;}for (int i = 0; i < num; ++i){if (currCost + dest[currPath[level - 1]][i] < bestCost&&set[i] == 0) //满足约束条件{currPath[level] = i;set[i] = 1;currCost += dest[currPath[level - 1]][i]; //标记trackback(level + 1);//选择下一个结点//回溯的过程currPath[level] = -1;currCost -= dest[currPath[level - 1]][i];set[i] = 0;}}此算法的时间复杂度为O((n-1)!)，空间复杂度为。
巧妙之处：约束条件除了上界还有结点是否已经选过，能减去更多不必要的解。
n后问题主要函数：void traceback(int i)bool conflict(int i)核心代码:if (i == numOfQueens)//到达叶子结点，打印结果{++sum;//解个数更新printResult("output2.txt");//打印到文件中return;}for (int k = 0; k < numOfQueens; ++k){status[i] = k;if (!conflict(i))//没有发生冲突{trackback(i + 1);//回溯过程status[i] = 0;}}此算法的时间复杂度为，空间复杂度为O(n)。
针对你所选的问题，你认为应该特别注意哪些方面的处理？比如循环何时结束等。
递归终止条件递归结束，即到达树的叶子节点时，打印结束后，return语句是必不可少的，不然会造成数组越界或程序不终止的结果。
回溯过程进入下一层递归结束后，回溯的过程不能缺少，若缺少，则只能找出一个解。
约束条件约束条件尽量设置较多的约束，才能避免多余的计算。
你在调试过程中发现了怎样的问题？又做了怎样的改进？未设置递归终止条件到达叶子结点时，打印了结果，但是缺少return语句，造成数组的越界改进：添加了return语句约束条件设计缺陷n后问题种，原conflict函数设计如下：bool conflict(int i, int j){ if (status[i] == status[j] ||(abs(i - j) == abs(status[i] - status[j]))){return true;}}return false;}将for语句放在函数之外，导致计算第0个皇后时，一次conflict都没有得到调用。
改进：将for语句放入conflict函数中for (int row = 0; row < i; ++row){//判断两个皇后是否同列或在一条斜线上if (status[i] == status[row] ||(abs(i - row) == abs(status[i] - status[row]))){return true;}}return false;其它（你认为需要在此说明的）六、实验结果总结回答以下问题：算法实现的复杂度在问题规模很大时可以接受吗？因为本次实验的两个问题都采用了递归的方法，时间复杂度在指数或阶乘级别，虽然会少计算一些解，但n变大时程序复杂度会很大，采用迭代形式的回溯法时间复杂度可能会变低一些。
如果不用回溯方法还能想到其他的解决方式吗？和回溯相比会有更好的效率吗？还可以使用分支界限法，和回溯法类似，分支界限法本质上也是列举，只不过分支界限法是以广度优先遍历排列树，通过维护优先队列寻找解的过程。
两种算法效率都差不多所选用的数据结构合适吗？本次实验并不涉及元素的增加和删除，涉及到大量的随机访问和元素值修改，用数组较为合适。
叙述通过实验你对回溯法的理解及其优缺点回溯法本质上还是穷举，只不过回溯法是把所有解以树形结构组织起来，通常组织成子集树和排列树两种形式，然后采用深度遍历遍历每个解，遍历过程中若发现当前解比最优解差，则放弃计算当前解。
优点：（1）算法有固定模型递归求解，易于理解缺点：（1）问题规模较大时，算法效率较低。
七、附录如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。
教师评语或评价表格：考核标准得分（1）正确理解和掌握实验所涉及的概念和原理（10%）；（2）按实验要求合理设计数据结构和程序结构（20%）；（3）能设计测试用例，运行结果正确（20%）；（4）认真记录实验数据，原理及实验结果分析准确（20%）；（5）实验过程中，具有严谨的学习态度和认真、踏实、一丝不苟的科学作风（10%）；（6）所做实验具有一定的创新性（10%）；（7）实验报告规范（10%）。