文章目录
- 前言
- 一、回溯法概述
- 二、回溯法的基本思想
- 三、回溯法的设计步骤
- 四、回溯法效率分析
- 五、回溯法示例
- 总结
前言
大家好，越努力，越幸运，我是程序猿小猿。本篇文章小猿将跟您分享算法设计与分析中的回溯法，希望对您有所帮助。
一、回溯法概述
1、应用背景
（1）、有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。
（2）、回溯法有"通用解题法"之称，是既有系统性又有跳跃性的搜索算法。由于组织得井井有条、能避免不必要的穷举式搜索，所以这种方法适用于解一些组合数相当大的问题。
（3）、回溯法，在搜索尝试中找问题的解，当不满足求解条件就"回溯"返回，尝试别的路径。它采用了一种"走不通就掉头"的思想，作为其控制结构。
2、问题的解空间
（1）、用回溯法解问题时：应明确问题的解空间；将解空间很好地组织起来，通常组织成树或图的形式。
（2）、问题的解向量：回溯法把一个问题的可能解表示成一个等长的n元式X=(x1，x2，x3，…，xn)形式。
（3）、约束条件：
显约束：对分量xi的取值限定，即xi属于集合Si。
隐约束：为满足问题的解而对不同分量之间施加的约束。
（4）、解空间：满足显式约束条件的解向量(等长)的所有多元组，构成了问题实例的一个解空间。值得注意的是，同一个问题的解可以有多种表示，有些表示方法更简单，所需表示的状态空间更小(存储量少，搜索方法简单)。
（5）、可行解：满足约束条件的解，是解空间中的一个子集。
（6）、最优解：使目标函数取极值(极大或极小)的可行解，一个或少数几个。
3、生成问题解的方法
（1）、扩展结点：正在产生孩子的结点称为扩展结点。
（2）、活结点：一个自身己生成，但其孩子还没有全部生成的结点称做活结点。
（3）、死结点：所有孩子已经产生的结点称做死结点。 注意：这些结点都是在搜索过程中动态生成的。
（4）、深度优先的问题解生成法：如果对一个扩展结点R，一旦产生了它的一个孩子C，就把C当做新的扩展结点。在完成对子树C(以C为根的子树)的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个孩子(如果存在)。.
（5）、广度优先的问题解生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。
（6）、回溯法：为了避免生成那些不可能产生最优解的问题状态，在搜索过程中，要不断地利用限界函数来"处死"那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界面数的深度优先的解生成法称为回溯法。
二、回溯法的基本思想
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。为避免无效搜索，采用限界/剪枝函数；用约束函数(条件)在扩展结点处剪去不满足约束的子树，即剪去得不到可行解的子树；用目标函数剪去得不到最优解的子树。
三、回溯法的设计步骤
回溯法的步骤
1、针对所给问题，定义问题的解空间；
2、确定易于搜索的解空间结构；
3、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
注意点
1、用回溯法解题的显著特征
（1）、在搜索过程中动态产生问题的解空间。这里需要注意的是，解空间树是虚拟的，不需要构造一棵真正的树结构。
（2）、在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为0(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。
2、回溯法的实现方式
( 1 )、递归回溯求解
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
算法描述
( 2 )、迭代回溯求解
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。
算法描述
3、解空间树的类型
（1）、子集树
当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。
遍历子集树需O(2^n)计算时间。
（2）、排列树
当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
遍历排列树需要Q(n!)计算时间。
四、回溯法效率分析
1、回溯算法的效率在很大程度上依赖于以下因素
（1）、产生x[k]的时间；
（2）、满足显约束的x[k]值的个数；
（3）、计算约束函数constraint的时间；
（4）、计算上界函数bound的时间；
（5）、满足约束函数和上界函数约束的所有x[k]的个数。
2、好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
3、重排原理，确定解空间树的结构，可以决定前三个因素。对于许多问题而言，在搜索试探时选取x[i]值的顺序是任意的。在其它条件相当的前提下，让可取值最少的x[i]优先将较有效。
4、估算回溯法产生的结点数目，概率方法思想。在解空间树上产性一条随机的路径，然后沿此路径估算解空间树中满足约束条件的结点总数m。计算回溯法产生的结点数。
五、回溯法示例
1、装载问题
2、图着色问题
3、旅行售货员问题
4、n-皇后问题
5、批处理作业调度
…
总结
知识点总结
1、回溯法在搜索尝试中找问题的解，当不满足求解条件就"回溯"返回，尝试别的路径。即它采用了一种"走不通就掉头"的思想，作为其控制结构。
2、用回溯法解问题时：应明确问题的解空间，将解空间组织成树或图的形式。
3、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。当搜索至解空间树的任意一点时，利用剪枝函数判断该结点是否包含问题的解：用约束函数(条件)在扩展结点处剪去不满足约束的子树，即剪去得不到可行解的子树；用目标函数剪去得不到最优解的子树。
4、递归和非递归求解框架。
结语
对回溯法的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。