一、回溯介绍
1、概念
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。
回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
回溯法适用于复杂的,规模较大的问题有“通用解题方法”的美称。
有许多问题,当需要找出它的解集 或者 要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法
- 解向量:希望问题的解 能够表示成一个 n 元式(x1, x2, …, xn)的形式。
- 解空间:对于问题的一个实例,满足显式约束条件的所有解向量,构成了该实例的一个解空间。
- 显约束:对分量 xi 的取值限定。
- 隐约束:为满足问题的解 而对不同分量之间施加的约束。
- 扩展结点:正在产生儿子的结点
- 活结点:自身已生成,但其儿子还没有全部生成的结点
- 死结点:所有儿子 已经产生的结点
- 深度优先生成法:扩展结点1,一旦产生了它的一个儿子2,就把结点2当做新的扩展结点。在完成 以2为根的子树 的穷尽搜索之后,将结点1重新变成扩展结点,继续产生结点1的下一个儿子
- 宽度优先生成法:在一个扩展结点变成死结点之前,它一直是扩展结点
当所给问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间称为子集树
当所给问题的确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。
回溯法就是具有剪枝函数的深度优先生成法
2、基本思想
在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
3、效率
子集树:结点数目 mn,计算时间 O(mn)
排列树:结点数目 n!,计算时间 O(n!)
回溯法的效率在很大程度上依赖于以下因素:
- 产生 扩展结点x[k]的时间;
- 满足显约束的扩展结点x[k]值的个数;
- 剪枝时间:计算 可行性约束函数 和 上界函数 的时间;
- 满足可行性约束函数和上界函数的 所有扩展结点x[k]的个数。
好的剪枝函数,能显著地减少所生成的结点数。但是,这样的剪枝函数往往计算量较大。因此,选择剪枝函数时,通常存在生成结点数与剪枝函数计算量之间的折衷。
4、用回溯法解题的一般步骤:
(1)针对所给问题,确定问题的解空间:
首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。
(2)确定易于搜索的解空间结构(排列树、子集树)
子集树:从元素中选哪几个,排列树:所需元素都要有,选一种排列
(3)从根节点以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
- 用约束函数在扩展结点处剪去不满足约束条件的子树;
- 用限界函数剪去得不到最优解的子树。
5、算法框架
(1)问题框架
设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件,记为f(ai)。