1、算法设计与分析回溯法回溯算法的应用课程名称： 算法设计与分析 院 系： 学生姓名： 学 号： 专业班级： 指导教师： 2013年12月27日回溯算法的应用摘 要：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，
2、只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统地搜索问题解的回溯算法，它适用于解决一些类似n皇后问题等求解方案问题，也可以解决一些最优化问题。在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以
3、大大提高运行效率。 关键词：回溯法 深度优先搜索 递归第1章 绪论1.1 回溯算法的背景知识 回溯算法是尝试搜索算法中最为基本的算法，在递归算法中，其存在的意义是在递归知道可解的最小问题后，逐步返回原问题的过程。实际上是一个类似于枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现不满足条件时就回溯返回，尝试别的路径。简单的说就是：从问题的某一种初始状态出发，依次搜寻每一种可能到达的情况，当走到这条路的“尽头”时，回过头到上一个情况，看这个情况是否还有没有走过的路，依次进行下去，直到遍历完所有的情况。回溯法实际上是一种深度优先搜索的方式。对于回溯法解决的问题，通常将其解空间
4、组织成图或者树的形式。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。1.2 回溯法的前景意义在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题
5、的分析可以大大提高运行效率。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题”、“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中回溯法也能起到很大的作用。回溯法适用于解决难以归纳一般规律解法的问题，其适用范围广，灵活性大，在解一些列举方法的问题时尤其可用。但是，其缺点也是明显的，即时间复杂度较大；因此在采用时我们应该因情况的不同而做出不同的选择。第2章 回溯算法的理论知识2.1 回溯算法设计过程 （1）确定问题的解空间应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。 （2）确定结点的扩展规则，如每个皇后在一行中的不同位置移动，
6、而象棋中的马只能走“日”字等。 （3）搜索解空间 回溯算法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。2.2 回溯算法框架（1）问题框架设问题的解是一个n维向量（a1,a2,.,an）
7、，约束条件是ai(i=1,2,3, .,n)之间满足某种条件，记为f(ai)。（2）非递归回溯框架 int an,i; 初始化数组a; i=1; While(i0(有路可走)）and(未到达目标) /还未回溯到头 if（in） /搜索到叶结点 搜索到一个解，输出； else /正在处理第i个元素 ai第一个可能的值； while(ai在不满足约束条件且在搜索空间内) ai下一个可能的值； if（ai在搜索空间内） 标识占用的资源； i=i+1; /扩展下一个结点 else 清理所占的状态空间； /回溯 i=i-1; (3)递归算法框架回溯法是对解空间的深度优先搜索，在一般情况下用递归函数来实现
8、回溯法比较简单，其中i为搜索深度，框架如下：int an;try(int i)if(in) 输出结果；else for(j=下界；j=上界;j+) if(f(j) ai=j; . try(i+1); 回溯前的清理工作（如ai置空值等）； 2.3 回溯算法的一般性描述回溯法的一般描述可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间E=（x1，x2，xn）xiSi ，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，n。我们称E中满足D的全部
9、约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，xi）满足D中仅涉及到x1，x2，xi的所有约束意味着j（j=i）元组（x1，x2，xj）一定也满足D中仅涉及到x1，x2，xj的所有约束，i=1，2，n。换句话说，只要存在0jn-1，使得（x1，x2，xj）违反D中仅涉及到x1，x2，xj的约束之一，则以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）一定也违反D
10、中仅涉及到x1，x2，xi的一个约束，nij。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，xj）违反D中仅涉及x1，x2，xj的一个约束，就可以肯定，以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。第3章 找n个数中r个数的组合问题3.1 问题描述回溯搜索解找n个数中r个数的组合问题3.2 问题分析 递归算法是找大规模问题和小规模问题的关系，回溯法是对问题的解空间进行深度优先搜索的算法。必须先确定搜索空间以
11、及约束条件，本题采用回溯搜索算法求解找n个数中r个数的组合问题。3.3 算法设计 不同于递归算法，递归算法是找大规模问题和小规模问题的关系，回溯法是对问题的解空间进行搜索的算法。(1) 问题的解空间为一组r元一维向量，（a1,a2,a3,.,ar），1=ai=n，1=i=r+1，若ri+ari 用二维数组job1002存储作业在M1，M2上的加工时间。2 由于f1在计算中，只须当前值，所以用变量存储即可；而f2在计算中，还依赖前一个作业的数据，所以有必要用数组存储。(4) 流程图 图4-1流水作业调度主函数流程图图4-2流水作业调度try()函数流程图图4-3流水作业调度swap()函数流程图
12、4.4 测试结果与分析图4-4流水作业车间调度问题的解 由流水作业调度问题分析可知，M1机器是顺序加工，M2机器在加工时有可能出现空闲或积压问题，因此当数据不同时，会根据此两种情况进行分析处理。 第5章 结论在两个实例编程中，总的算法思想都是利用回溯算法求解问题，在n个数中找出r个数实例中，利用递归的算法设计，使算法过程逐步递归地回溯，以便简化问题，进行求解问题。在流水作业调度问题中，也是利用回溯算法是问题得到最优解。 在通过两个实例编程后，对回溯算法的思想结构以及求解问题的方法有了更深入的理解，对回溯法的解题框架更清楚了。但在另一方面，也认识到自己的不足之处，比如在调试流水作业调度问题时，对
13、swap()函数没有调试，以为只是一个互换函数，但调试程序时一直出错，最后才明白过来，有关内容的交换，必须利用指针进行交换。由此，通过两个实例的编程，又使自己收获很多，但还是需要多加学习。算法问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯的一个重要特性。具体来说：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
14、此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 参考文献1 算法设计与分析（第二版） 吕国英 主编 指导教师评语：1、文档：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未实现 部分实现 全部实现 d、文档格式： 不规范 基本规范 规范 2、答辩： a、未能完全理解题目，答辩情况较差 b、部分理解题目，部分问题回答正确 c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利 文档成绩： ，占总成绩比例： 40% 答辩成绩： ，占总成绩比例： 60% 总 成 绩： 指导教师签字：年 月 日
