回溯算法的应用

课程名称:院系:学生姓名:学号:专业班级:指导教师:计算机科学与技术课程名称:院系:学生姓名:学号:专业班级:指导教师:计算机科学与技术（信息技术）11-1回溯算法的应用算法设计与分析计算机科学与信息工程学院******2013年12月27日1溯算法的应用摘要：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法是尝试搜索算法中最为基本的一种算法，它的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。回溯算法也叫试探法，实际上是一个类似枚举的搜索尝试方法，是一种系统地搜索问题的解的方法。它的主要思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。关键词：回溯搜索全排列最优化问题结点TOC\o"1-5"\h\z第1章绪论.11.1回溯算法的背景知识11.2回溯法的前景意义1第2章回溯算法的理论知识22.1问题的解最优化问题22.2回溯算法的一般性描述2第3章全排列问题43.1问题描述43.2问题分析43.3算法设计43.4测试结果与分析6第四章最优化问题74.1问题描述74.2问题分析74.3算法设计74.4测试结果与分析9第5章结论10参考文献101010第#页共17页第1章绪论1.1回溯算法的背景知识回溯算法是尝试搜索算法中最为基本的算法，在递归算法中，其存在的意义是在递归知道可解的最小问题后，逐步返回原问题的过程。实际上是一个类似于枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现不满足条件时就回溯返回，尝试别的路径简单的说就是：从问题的某一种初始状态出发，依次搜寻每一种可能到达的情况，当走到这条路的“尽头”时，回过头到上一个情况，看这个情况是否还有没有走过的路，依次进行下去，直到遍历完所有的情况。回溯法实际上是一种深度优先搜索的方式。对于回溯法解决的问题，通常将其解空间组织成图或者树的形式。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。1.2回溯法的前景意义在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提咼运行效率。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“全排列”“最优化问题”，这只是在教学阶段中的运用，在实际运用中回溯法也能起到很大的作用。回溯法适用于解决难以归纳一般规律解法的问题，其适用范围广，灵活性大，在解一些列举方法的问题时尤其可用。但是，其缺点也是明显的，即时间复杂度较大；因此在采用时应该因情况的不同而做出不同的选择。第2章回溯算法的理论知识2.1问题的解最优化问题对于最优化问题。一个有趣的高精度数据：构造一个尽可能大的数，使其从高到低满足前一位能被1整除，前2位能被2整除，，前n位能被n整除。记高精度数据为a1,a2,…，an,a1能被1整除且（a1*10+a2）能被2整除且Ca1*10An-1+a2*10An-2+„an）能被n整除；求最大的这样的数。此数只能用从高位到低位逐位尝试，失败回溯的算法策略求解，生成的高精度数据用数组从高位到低位存储，1号元素开始存储最高位。此数的大小无法估计不妨为数组开辟100个空间。算法中数组A为当前求解的高精度数据的暂存处，数组B为当前最大的满足条件的数，算法的首位A[1]（最高位）从1开始枚举。以后各位从0开始枚举。所以求解出的满足条件的数据之间只须比较数就能确定大小，n为当前满足条件的最大数据的位数，i为当前满足条件数据的位数，当i>=n就认为找到了更大的解。当i>n不必解释，位数多数据一定大；i=n时，由于尝试是由小到大进行的，虽然位数相等，但后来满足条件的数据一定比前面的大。2.2回溯算法的一般性描述回溯法的一般描述可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x，x，…，12x）组成的一个状态空间E={（x，x，…，x）|xUS，i=l,2,…，n}，给n12nii定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中S是分量x的定义域，且|S|有限，i=1,2,…，n。我们iii称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。对于许多问题，所给定的约束集D具有完备性，即i元组(x，x，„，12x)满足D中仅涉及到x,X，…，x的所有约束意味着j(j<=i)元组(X,X，…,TOC\o"1-5"\h\zi12i12x)一定也满足D中仅涉及到x，x，„，x的所有约束，i=1,2，„，n。换句j12j话说，只要存在OWjWn-1，使得(x，x，…，x)违反D中仅涉及到x，x，…,12j12x的约束之一，则以(x,x,„,x)为前缀的任何n元组(x,x,„,x,j12j12jx,„,x)一定也违反D中仅涉及到x,x,„,x的一个约束，n^i^j。j+1n12i因此，对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x,x，…,12x)违反D中仅涉及x,x,„,x的一个约束，就可以肯定，以(x,x,„,j12j12x)为前缀的任何n元组(x,x,„,x,x,„,x)都不会是问题P的解，j12jj+1n因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。第3章全排列问题3.1问题描述回溯搜索解全排列问题：输入自然数1到n所有不重复的排列，即n的全排列。3.2问题分析将n个元素按照一定的顺序排列起来，用数组记录前面数据的排列情况。然后进行输出，并要求在搜索过程中满足约束条件，这便需要确定搜索空间进行搜索。3.3算法设计确定搜索空间。n的全排列是一组n元一维向量，(x1,x2,x3…，xn)，搜索空间是：1〈二xi〈二ni=1，2，3，,n确定约束条件。约束条件很简单，xi互不相同。设置n个元素的一维数组d，其中的n个元素用来记录数据1~n的使用情况，已使用置1，未使用置0。主要的数据结构。从n个不同元素中任取m(m<fi)个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。一维数组d[100]记录数据1~n的使用情况，已使用置1，未使用置0；—维数组a[100]对应一维数组d[100]，记录1~n个数的排列。tr()函数是用来进行判断，把当前元素与前面的元素进行逐个比较。结构如下：tr(intk)〃当前处理的第k个元素{intj；

for(j=l;jv=n;j++){if(d[j]==0)〃已使用置1,未使用置0{a[k]=j;d[j]=1；}(4)程序流程图。图3-1算法流程图

3.4测试结果与分析测试结果：图3-2全排列问题的解从图3-2可以看出，输入数字4,其结果为：1234；1243；1324；1423；1432；2134；2143；2314；2341；2413；2431；3124；3142；3214；3241；3412；3421；4123；4132；4213；4231；4312；4321。输出结果和预期是一样的，这说明了算法是适应大多数情况的，是正确的。时间复杂度为O(fn)。第四章最优化问题4.1问题描述一个有趣的高精度数据：构造一个尽可能大的数，使其从高到低满足前一位能被1整除，前2位能被2整除，，前n位能被n整除。4.2问题分析对于最优化问题，一般都可以通过找出全部解方法，从而确定其中的最优解，但这样做算法的效率肯定得不到保证。在搜索解的过程中，可以考虑每一位都从9开始尝试，这样只有搜索到更多位数的解时，才算找到了更大的解，可以减少记录当前最大解的操作。用回溯搜索来解决，记高精度数据为al，a2,…，an，al能被1整除且(a1*10+a2)能被2整除且(a1*10An-1+a2*10An-2+„an)能被n整除；求最大的这样的数。4.3算法设计此数只能用从高位到低位逐位尝试，失败回溯的算法策略求解，生成的高精度数据用数组从高位到低位存储，1号元素开始存储最高位。此数的大小无法估计不妨为数组开辟100个空间。算法中数组A为当前求解的高精度数据的暂存处，数组B为当前最大的满足条件的数，算法的首位A[1](最高位)从1开始枚举。以后各位从0开始枚举。所以求解出的满足条件的数据之间只须比较数就能确定大小，n为当前满足条件的最大数据的位数，i为当前满足条件数据的位数，当i>=n就认为找到了更大的解。当i>n不必解释，位数多数据一定大；i=n时，由于尝试是由小到大进行的，虽然位数相等，但后来满足条件的数据一定比前面的大。流程图如图4-1所示：图4-1算法流程图结束4.4测试结果与分析测试结果：图4-2最优化问题的解从图4-2可以看出，构造一个尽可能大的数，使其从高到低满足前一位能被1整除，前2位能被2整除，……，前n位能被n整除。其输出结果是3608528850368400786036725。输出结果和预期是一样的，这说明了算法是适应大多数情况的，是正确的。第5章结论通过本次课程设计，对回溯法有了更进一步的理解，学会了用回溯法解决相关问题的思路。在本次课程设计的过程中，也遇到了一些问题，比如：在用回溯搜索解最优化问题时程序没有输出结果和解全排列问题时对于tr()函数的不理解，对于其中出现的问题经过同学的帮助以及查阅相关的资料，在程序最后增加了一个for循环和cout输出格式，并将#include"stdio.h"改为了#include"iostream",最终输出了程序的正确结果；并了解了tr()函数是用来进行判断，是把当前元素与前面的元素进行逐个比较。并在过程中对回溯算法有了更深一步的理解。回溯法是尝试搜索算法中最为基本的一种算法，其采用了“走不通就掉头”的思想，作为其控制结构。在用回溯算法解决问题中每向前走一步都有很多路需要选择，但当没有决策的信息或决策的信息不充分时,只好尝试某一路线向下走，到一定程度后得知此路不通时，再回溯到上一步尝试其他路线；当然在尝试成功时，则问题得解算法结束。回溯算法也叫试探法，实际上是一个类似枚举的搜索尝试方法，是一种系统地搜索问题的解的方法。它的主要思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。参考文献[1]算法设计与分析(第二版)源代码全排列问题源程序#include"stdio.h"intp=0,n,a[100],d[100];tr(intk);output(intj);voidmain(){intj;printf("Inputn二：")；scanf("%d"，&n);for(j=1;j<=n;j++)d[j]=0;tr(1);}tr(intk){intj;for(j=1;j<=n;j++){if(d[j]==0){a[k]=j;d[j]=1;}elsecontinue;if(k<n)tr(k+1);else{p=p+l;output(k);}d[a[k]]=0;吕国英主编//输出结果//当前处理的第k个元素//变量p记录排列的数组}output(intj){printf("%d:",p);for(j=l;j〈二n;j++)printf("%d",a[j]);printf(〃\n〃)；}最优化问题源程序：#include"iostream"usingnamespac