算法分析与设计
实验报告
姓名
学号
班级
指导教师
实验名称
算法分析与设计
开设学期
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%）。
