回溯算法的应用.pdf

《回溯算法的应用.pdf》由会员分享，可在线阅读，更多相关《回溯算法的应用.pdf（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、回溯算法的应用回溯算法的应用课程名称：算法设计与分析院系：*学生姓名：*学号：*专业班级： *指导教师：*2013 年 12 月 27 日1第 1 页 共 19 页回溯法的应用回溯法的应用摘摘要：要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。 但当探索到某一步时， 发现原先选择并不优或达不到目标， 就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法， 它的主题思想是在搜索尝试过程中寻找问题的解，当发

2、现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比

3、如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。关键词：关键词：回溯法全排列最优值枚举2第 2 页 共 19 页目目录录第 1 章绪论. 41.1 回溯法的背景知识.41.2 回溯法的前景意义.4第 2 章回溯法的理论知识.52.1 问题的解空间树.52.2 回溯法的一般性描述.6第 3 章 n 的全排列 . 73.1 问题描述. 73.2 问题分析. 73.3 算法设计. 73.4 测试结果与分析.9第 4 章最优化问题.114.1 问题描述. 114.2 问题分析. 114.3 算法设计. 114.4 测试结果与分析.14第 5 章结论. 15参考文献. 16附件.

4、163第 3 页 共 19 页第 1 章绪论1.1 回溯法的背景知识回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在递归算法中，其存在的意义是在递归知道可解的最小问题后，逐步返回原问题的过程。实际上是一个类似于枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解， 当发现不满足条件时就回溯返回， 尝试别的路径。简单的说就是：从问题的某一种初始状态出发，依次搜寻每一种可能到达的情况，当走到这条路的“尽头”时， 回过头到上一个情况， 看这个情况是否还有没有走过的路，依次进行下去，直到遍历完所有的情况。回溯法实际上是一种深度优先搜索的方式

5、。对于回溯法解决的问题，通常将其解空间组织成图或者树的形式。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解与约束函数进行对照从而删除一些不可能的解， 这样就不必继续把解的剩余部分列出从而节省部分时间。1.2 回溯法的前景意义在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构

6、明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题” 、 “0/1 背包问题” ，这只是在教学阶段中的运用，在实际运用中回溯法也能起到很大的作用。回溯法适用于解决难以归纳一般规律解法的问题，其适用范围广，灵活性大，在解一些列举方法的问题时尤其可用。但是，其缺点也是明显的，即时间复杂度较大；因此在采用时我们应该因情况的不同而做出不同的选择。4第 4 页 共 19 页第 2 章回溯法的理论知识2.1 问题的解空间树对于全排列问题。对 n 位数进行全排列，知道了这个数的位数就知道有多少种排列方法，在 n 位数中选定一个数

7、为首位就可以进行下面的排列。当n=4 时，我们要从一个数开始排列，再进行其他两位数。假设排列从 1 开始出发，则可能的路径如下图 2.1。图 2.1选择的路径活结点：不是叶结点，满足约束条件，使目标函数有所改善，儿子结点有尚未访问的（可继续搜索下去） 。否则为死结点。E-结点：扩展结点，当前正在搜索的活结点。死结点：即如果取了这个结点，将不会有可行解。5第 5 页 共 19 页2.2 回溯法的一般性描述回溯法的一般描述可用回溯法求解的问题 P，通常要能表达为：对于已知的由n 元组（x1，x2， xn）组成的一个状态空间 E=（x1，x2，xn）xiSi，i=1，2，n，给定关于 n 元组中的一

8、个分量的一个约束集 D，要求 E 中满足 D 的全部约束条件的所有 n 元组。其中Si是分量 xi的定义域，且 |Si| 有限，i=1，2，n。我们称E 中满足 D 的全部约束条件的任一 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

9、，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 中仅涉及到 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 的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这

10、类问题的上述性质而提出来的比枚举法效率更高的算法。6第 6 页 共 19 页第 3 章n 的全排列3.1 问题描述输出自然数 1 到 n 所有不重复的全排列。3.2 问题分析在 n 的全排列是一组 n 元一维向量， （x1,x2,x3,xn）,搜索空间是：1=xi=ni=1,2,3,n约束条件很简单，xi 互不相同。3.3 算法设计1、算法介绍本例题采用“数组记录状态信息”的方法检查在搜索过程中是否满足约束条件。一般的方法是用 cheak()函数进行判断， cheak()函数中当前元素与前面的元素进行逐个比较。而在这个算法中用的是 try()函数，是搜索的过程更加快。void TRY(int

11、k)/找第 k 个数int j;for(j=1;j=n;j+)if(dj=0)/判断第 k 个数是否可用ak=j;dj=1;elsecontinue;/第 k 个数不可用if(kn)TRY(k+1);/找第 k+1 个数elsep+;output() ; /输出元素7第 7 页 共 19 页dak=0;/将数组中的数设为未使用具体方式为： 设置 n 个元素的一维数组 d， 在该算法中的一维数组 d 用于记录数组中的元素的状态（是否被搜索过） ，其中的n 个元素用来记录数据 1n 的使用情况，已使用置 1，未使用置 0。直到所有元素的已使用，输出结果；然后循环进行，直到输出所有排列。在该算法中最

12、重要的一个函数就是 dak=0，这是回溯的核心，用以上回溯法搜索算法完成算法的全排列问题的复杂度为 O（nn）,不是最佳算法。如果在算法中运用try（）函数自身之间的交换，for 循环语句 for（j=t;j=n;j=j+1）,而且 for 循环体中的第二个 swap（）调用，是用来恢复原顺序的，在每次回溯时，都要恢复本次操作前的原始操作。这个全排列算法的复杂度为 O（n！ ） ，其结果可以为搜索排列树所用。2、流程图8第 8 页 共 19 页开始输入 n,初始化数组 d为 0调用递归函数 try 进行全排列，并输出排列Try 函数开始Ydj=0NNk =n 就认为找到了更大的解。当 in 不

13、必解释，位数多数据一定大；i=n 时，由于尝试是由小到大进行的，虽然位数相等，但后来满足条件的数据一定比前面的大。（1）从A1=1开 始 ， 每 增 加 一 位Ai( 初 值 为0) 先 计 算r=（A1*10i-1+A2*10i-2+Ai） ，再测试 r=r modi 是否。（2）r=0 表示增加第 i 位后，满足条件，与原有满足条件的数（存在数组 B 中）比1 1第 11 页 共 19 页较，若前者大，则更新后者（数组 B） ，继续增加下一位。（3）r ！ 0 表示增加 i 位不满足整除条件， 接下来算法中并不是继续尝试 Ai=Ai+1,而 是 继 续 尝 试Ai=Ai+i-r ， 因 为

14、 若Ai=Ai+i-r9 时，要进位也不能满足条件。这时，只能将此恢复初值 0且回退到前一位（i=i-1）尝试Ai=Ai+1，以此类推。这正是算法中最后一个 while 循环所做的工作。（5）当回溯到 i=1 时，A1加 1 开始尝试首位为 2 的情况，最后直到将 A1=9 的情况尝试完毕，算法结束。主要的函数及功能while(A1=n)/判断 i 的值n=i;/转存到数组 B 中for(k=1;k=n;k=k+1)Bk=Ak;i=i+1;r=0;for(j=1;j9 & i1)/搜索完第 i 位的解，回溯到前一位Ai=0;i=i-1;Ai=Ai+i;2、流程图1 2第 12 页 共 19 页

15、开始A 数组首位赋为1，其它位为 0.i = 1; n = 1;NA1 = n ?n = i ;k = 1;Nk=NYBk=Akk+;i +;r = 0;j = 1;r = 10 * rY+Aj;j 9&iiNYAi=0;i-;Ai=Ai+i;结束1 3第 13 页 共 19 页4.4 测试结果与分析（1）测试结果：图 4.1最优值（2）对测试结果的分析：对输出的数据进行检验，例如3 能被 1 整除，36 能被 2 整除，360 能被 3 整除，3608 能被 4 整除检查完输出结果的所有数位发现满足题意，说明结果是正确的，该算法使用与此类问题的求解。1 4第 14 页 共 19 页第 5 章

16、结论通过本次课程设计，我对回溯法有了更为深入的理解，学会了用回溯法解决相关问题的思路。在本次课程设计的过程中，小组遇到了一些问题，比如：开始时，对于深度优先搜索知识的欠缺，在查找时产生错误；回溯函数放错了地方等。对于其中出现的问题经过我们的讨论以及查阅相关的资料都得到了解决， 并在讨论的过程中对知识的理解更为深刻。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免

17、移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的， 这是回溯算法的一个重要特性。具体来说：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有

18、活结点时为止。1 5第 15 页 共 19 页参考文献1 算法设计与分析（第二版） 吕国英 主编附件全排列问题源程序：#includeint p=0,n,a100,d100;void output()int j;printf(%dn,p);/p 为第几组排列for(j=1;j=n;j+)printf(%d,aj);/输出排列printf(n);void TRY(int k)/找第 k 个数int j;for(j=1;j=n;j+)if(dj=0)/判断第 k 个数是否可用ak=j;dj=1;elsecontinue;/第 k 个数不可用1 6第 16 页 共 19 页if(kn)TRY(k+1

19、);/找第 k+1 个数elsep+;output();/输出元素dak=0;/将数组中的数设为未使用int main()int j;printf(Input n=);/输入 nscanf(%d,&n);for(j=1;j=n;j+)/函数完成初始化dj=0;TRY(1);return ；最优化问题源程序：#includeint main()int A101,B101;int i,j,k,n,r;A1=1;for(i=2;i=100;i=i+1)/置初值：首位为 1，其余为 0Ai=0;n=1;i=1;1 7第 17 页 共 19 页while(A1=n)/判断 i 的值n=i;/转存到数组

20、B 中for(k=1;k=n;k=k+1)Bk=Ak;i=i+1;r=0;for(j=1;j9 & i1)Ai=0;i=i-1;Ai=Ai+i;printf(max is:);for(i0;i=n;i+)printf(%d,Bi);/第 i 位是否满足条件/第 i 位可能的解/搜索完第 i 位的解，回溯到前一位1 8第 18 页 共 19 页指导教师评语：指导教师评语：1、文档：a、内容：不完整完整详细b、方案设计： 较差合理非常合理c、实现：未实现部分实现全部实现d、文档格式： 不规范基本规范规范2、答辩： a、未能完全理解题目，答辩情况较差b、部分理解题目，部分问题回答正确c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利文档成绩：，占总成绩比例： 40%答辩成绩：，占总成绩比例： 60%总 成 绩：指导教师签字：年月日1 9第 19 页 共 19 页