算法设计与分析【六】

一、回溯介绍


1、概念

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

回溯法适用于复杂的,规模较大的问题有“通用解题方法”的美称。

有许多问题,当需要找出它的解集 或者 要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法

  • 解向量:希望问题的解 能够表示成一个 n 元式(x1, x2, …, xn)的形式。
  • 解空间:对于问题的一个实例,满足显式约束条件的所有解向量,构成了该实例的一个解空间。
    • 显约束:对分量 xi 的取值限定。
    • 隐约束:为满足问题的解 而对不同分量之间施加的约束。
  • 扩展结点:正在产生儿子的结点
  • 活结点:自身已生成,但其儿子还没有全部生成的结点
  • 死结点:所有儿子 已经产生的结点
  • 深度优先生成法:扩展结点1,一旦产生了它的一个儿子2,就把结点2当做新的扩展结点。在完成 以2为根的子树 的穷尽搜索之后,将结点1重新变成扩展结点,继续产生结点1的下一个儿子
  • 宽度优先生成法:在一个扩展结点变成死结点之前,它一直是扩展结点

当所给问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间称为子集树

当所给问题的确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。

回溯法就是具有剪枝函数的深度优先生成法

2、基本思想

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。

若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

3、效率

子集树:结点数目 mn,计算时间 O(mn)

排列树:结点数目 n!,计算时间 O(n!)

回溯法的效率在很大程度上依赖于以下因素:

  1. 产生 扩展结点x[k]的时间;
  2. 满足显约束的扩展结点x[k]值的个数;
  3. 剪枝时间:计算 可行性约束函数 和 上界函数 的时间;
  4. 满足可行性约束函数和上界函数的 所有扩展结点x[k]的个数。

好的剪枝函数,能显著地减少所生成的结点数。但是,这样的剪枝函数往往计算量较大。因此,选择剪枝函数时,通常存在生成结点数与剪枝函数计算量之间的折衷。

4、用回溯法解题的一般步骤:

(1)针对所给问题,确定问题的解空间:

首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

(2)确定易于搜索的解空间结构(排列树、子集树)

子集树:从元素中选哪几个,排列树:所需元素都要有,选一种排列

(3)从根节点以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

  • 用约束函数在扩展结点处剪去不满足约束条件的子树;
  • 用限界函数剪去得不到最优解的子树。

5、算法框架

(1)问题框架

设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件,记为f(ai)。

(1)回溯方式

(2)迭代方式

6、实例

(1)装载问题

(2)旅行商问题

(3)图着色问题

(4)01背包

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~