回溯法

0 概述

基本思想

  • 回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的基本思想：该方法系统地搜索一个问题的所有的解或任一解。

  • 与剪枝相结合，也称为回溯-剪枝法。

  • 深度优先搜索与回溯剪枝这两个思想有一个非常重要的优势。它是一条路经走到黑。如果这条路径合适的话，就可以直接返回。另外。当前所有的搜索选项中，只有一条路径在工作。也就是说只需要记录当前一条路径的状态。所以解决迷宫问题的时候，不需要复杂的状态记录方法。只需要记录当前这一个分支的路径状态即可。

要素

  • 解向量-问题解的表示：
    回溯法将问题的解表示成n元式$(x_1,x_2,\cdots,x_n)$。
  • 显示约束：
    对分量xi的取值限定。
  • 隐式约束：
    对满足问题的解而对不同分量之间施加约束
  • 解空间：
    对于一个实例，解向量满足显示约束条件的所有多元组，构成了该实例的一个解空间。

回溯法的适用条件

  • 适用于搜索问题和优化问题

  • 多米诺性质：叶子节点的解一定满足其父节点。叶子结点为真则父节点一定为真。同理父节点为假则叶子结点一定为假（逆否命题）。用父节点为假的情况进行剪枝操作。

  • 设P(x1,x2,…,xi)是关于向量<x1,x2,…,xi>的某个性质，那么P(x1,x2,…,xi+1)真蕴含P(x1,x2,…,xi) 为真，即P(x1,x2,…,xi+1) → P(x1,x2,…,xi) (0<i<n) (n为向量维数)

2 求解过程

基本方法

  1. 明确定义问题的解空间。

    • 将问题的解空间组织成树的结构，通过采用系统的方法隐含搜索解空间树，从而得到问题解。回溯法的基本做法是搜索，是一种组织的井井有条的，能避免不必要搜索的穷举式搜索。搜索策略主要有：深度优先、广度优先、函数优先、广度深度结合。

  2. 节点分支判定条件：

    • 满足约束条件：分支扩展解向量。
    • 不满足约束条件：回溯到当前节点的父结点。

  3. 结点状态：

    • 白结点：尚未访问的节点
    • 灰节点：正在访问以该节点为跟的子树。
    • 黑节点：以该节点为根的子树遍历完成。

  4. 存储当前索索路径

  5. 搜索策略（避免无效搜索）

    • 约束函数：在扩展节点处减去不满足约束条件的子树。
    • 界限函数：在扩展节点处减去得不到最优解的子树。

具体的步骤

判断问题是否满足多米诺性质

  1. 定义解空间
    • 问题解向量
    • 解向量分量取值集合
    • 构造解空间树
  2. 确定剪枝函数
  3. 搜索解空间树
  4. 存储搜索路径，确定存储的数据结构

两种典型的解空间树

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

  • 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间成为排列树。排列树有n！个叶结点。

  • 问题所有可行解分布在集合{<x1, x2, …, xn> | 1 ≤ xi ≤N, 1 ≤ i ≤N}（解空间）之中。可将问题解空间表示为一定的结构，通过对解空间的搜索，得到满足要求的问题解。

简单来说，解空间是子集树时不具有排列性质，没有位置关系。为排列树时需要考虑每个要素的顺序。

回溯法的时间复杂度

依赖以下条件

  • 产生x[k]的时间；
  • 满足显约束的x[k]值的个数；
  • 计算约束函数constraint的时间；
  • 计算上界函数bound的时间；
  • 满足约束函数和上界函数约束的所有x[k]的个数。

是NPhard难题。需要遍历解空间树。

回溯法的程序结构

  • 递归回溯
1
2
3
4
5
6
7
8
9
void backtrack (int t)
{
       if (t>n) output(x);
       else
         for (int i=f(n,t);i<=g(n,t);i++) {
           x[t]=h(i);
           if (constraint(t)&&bound(t)) backtrack(t+1);
           }
}
  • 迭代回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void iterativeBacktrack ()
{
  int t=1;
  while (t>0) {
    if (f(n,t)<=g(n,t))
      for (int i=f(n,t);i<=g(n,t);i++) {
        x[t]=h(i);
        if (constraint(t)&&bound(t)) {
          if (solution(t)) output(x);
          else t++;}
        }
    else t--;
    }
}

分支限界与回溯法对比

  • 求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解。而分支限界的求解目标是找出满足约束条件的一个解。这个解可能是最优解。
  • 搜索方式不同：回溯法以深度优先的方式搜索解空间。而分支限界法则以广度优先或以最小消耗优先的方式搜索解空间。

3 常见问题

m着色问题

装载问题

批作业调度问题