回溯算法的应用.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 算法 应用
限制150内