搜索
Tenloy's Blog

(四) 回溯法(试探算法)

Word count: 3kReading time: 10 min
2021/06/26 Share

回溯算法：深度优先搜索 + 剪枝。

关于回溯算法、分支限界算法：

  • 都是一种对暴力搜索(穷举算法)中的优化算法。（关键是能准确划定问题的解空间，保证覆盖问题的全部候选解+可行解）。
  • 对于某些计算问题而言，是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（是种数学的问题，其定义为一组物件，而这些物件需要满足一些限制或条件）。
  • 分支限界算法和穷举法所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。

一、术语概念

在学习回溯和分支限界法之前了解一些术语概念

  • 问题的解向量：将一个问题的解表示成一个n元式 (x1,x2,…,xn) 的形式
  • 显式约束：对分量 xi 的取值限定，满足显式约束的解，称为候选解。
  • 隐式约束：为满足问题的解而对不同分量之间施加的约束，候选解若满足隐式约束，称为可行解。
  • 目标函数：用来衡量每个可行解的优劣。使目标函数取最大（或最小）值的可行解为问题的最优解。
  • 代价(成本)函数：在最优化，统计学，机器学习等领域中，代价(成本)函数是指一种将一个事件（在一个样本空间中的一个元素）映射到一个表达与其事件相关的经济成本或机会成本的实数上的一种函数，借此直观表示的一些”成本“与事件的关联。一个最佳化问题的目标是将代价函数最小化。
  • 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。将解空间很好地组织起来，一方面有助于快速找到问题的解，一方面也可以防止遗漏部分可行解。常见的：树(子集树/排列树)、图。
  • 解空间树：解空间的树结构（同一个问题可以有多种表示(也可能是图等)，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单））。
    • 树中每个结点称为一个问题状态(problem state)。
    • 由根节点到其它节点的所有路径确定了这个问题的状态空间，所以这个树也叫做状态空间树。
    • 如果从根到树中某个状态的路径代表一个作为候选解的元组，则称该状态为解状态(solution state)。
    • 如果从根到某个解状态的路径代表一个作为可行解的元组，则称该解状态为答案状态(answer state)。
  • 扩展结点：一个正在产生儿子的结点称为扩展结点，又称E-结点。
  • 活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点。
  • 死结点：一个所有儿子已经产生的结点称做死结点。
  • 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
  • 宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
  • 剪枝函数：搜索状态空间树过程中，剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，提高搜索效率。
    • 约束函数：在扩展结点处减去不满足约束条件的子树，避免无谓地搜索那些已知不含答案状态的子树。
    • 限界函数：其意义是对最优解状态的目标函数值的范围进行界定。如果是最优化问题，可用限界函数(bound function)剪去那些得不到最优解的子树。

约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruning function）。

使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法(backtracking)。

使用剪枝函数的广度优先生成状态空间树中结点的求解方法称为分支/枝限界法(branch-and-bound)。

回溯法/分支限界法 = 穷举 + 剪枝。

二、基本思想

回溯法是一个既带有系统性又带有跳跃性的搜索算法；

  • 系统性：它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
  • 跳跃性：算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯(满足回溯条件的某个状态的点称为回溯点)；否则，进入该子树，继续深度优先的策略进行搜索。

这种以深度优先的方式系统地搜索问题的解得算法称为回溯法。其实回溯法就是对隐式图的深度优先搜索算法

回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式 (x1,x2,...,xn) 来 表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间,逐步确定xi 的值，直到解被找到。

  • 假设我们已经确定部分解的集合 (x1,x2,...,xi)，在此基础上 通过增加解元素 xi+1 来扩展解，确定 xi+1的值后，我们要测试 (x1,x2,...,xi+1) 是否仍是可行解。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，来确保解的正确性。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

三、适用情况

有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。(找出解空间树中满足约束条件的所有解)。

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数较大的问题。

四、基本步骤

  1. 针对所给问题，定义问题的解空间

    首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。通常这个解空间是非常巨大的，所以搜索一个目标解的代价是很难想象的。为了使回溯算法更有效率，我们必须缩小搜索空间。

  2. 确定易于搜索的解空间结构(典型的组织方式是图、树-排列树/子集树等)

  3. 从根节点开始，以深度优先方式搜索解空间

  4. 在搜索过程中用剪枝函数避免搜索进入不可能得到解的子空间。

五、程序设计

5.1 一般的算法设计模式如下

5.1.1 问题框架

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

5.1.2 递归的算法框架

回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[n];
try (int i) {
    if (i > n)
        输出结果;
    else {
        for (j = 下界; j <= 上界; j = j + 1) // 枚举i所有可能的路径
        {
            if (fun(j)) // 满足限界函数和约束条件
            {
                a[i] = j;
                ... // 其他操作
                try (i + 1);
                回溯前的清理工作（ 如a[i] 置空值等）;
            }
        }
    }
}

5.1.3 非递归回溯框架

递归转非递归，这里可以参考树的遍历，或者看上篇博客——递归算法介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int a[n], i;
初始化数组a[];
i = 1;
while (i > 0(有路可走) and(未达到目标)) // 还未回溯到头
{
    if (i > n) // 搜索到叶结点
    {
        搜索到一个解， 输出；
    } else // 处理第i个元素
    {
        a[i] 第一个可能的值；
        while (a[i] 在不满足约束条件且在搜索空间内) {
            a[i] 下一个可能的值；
        }
        if (a[i] 在搜索空间内) {
            标识占用的资源；
            i = i + 1; // 扩展下一个结点
        } else {
            清理所占的状态空间； // 回溯
            i = i– 1;
        }
    }
}

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 h(n)，则回溯法所需的计算空间通常为 O(h(n)) 。而显式地存储整个解空间则需要 O(2^h(n)) 或 O(h(n)!)内存空间。

5.2 回溯法搜索子集树

回溯法解题的时候常遇到两种类型的解空间树：子集树、排列树。

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。例如，n个物品的0-1背包问题所相应的解空间树就是一棵子集树。这类子集树通常有 2^n 个叶结点，其结点总个数为 2^(n+1)-1。遍历子集树的任何算法均需：Ω(2^n) 的计算时间。

子集树

用回溯法搜索子集树的算法框架可描述为：

1
2
3
4
5
6
7
8
9
10
void backtrack (int t)
{
  if (t>n) output(x);
    else
      for (int i=0;i<=1;i++) {
        x[t]=i;
        //Constarint(t)和Bound(t)表示当前扩展结点处的约束函数和限界函数
        if (Constarint(t)&&Bound(t)) backtrack(t+1);
      }
}

5.3 回溯法搜索排列树

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有 n! 个叶结点。因此遍历排列树需要 Ω(n!) 的计算时间。

排列树：

用回溯法搜索排列树的算法框架可描述为：

1
2
3
4
5
6
7
8
9
10
11
void backtrack (int t)
{
  if (t>n) output(x);
    else
      for (int i=t;i<=n;i++) {
        swap(x[t], x[i]);//swap作用是交换两个元素
        //Constarint(t)和Bound(t)表示当前的约束函数和限界函数
        if (Constarint(t)&&Bound(t)) backtrack(t+1);
        swap(x[t], x[i]);
      }
}

六、经典运用：

  • 装载问题
  • 批处理作业调度
  • 符号三角形问题
  • n后问题
  • 0-1背包问题
  • 最大团问题
  • 图的m着色问题
  • 旅行售货员问题
  • 圆排列问题
  • 电路板排列问题
  • 连续邮资问题

Author：Tenloy

原文链接：https://tenloy.github.io/2021/06/26/back-track.html

发表日期：2021.06.26 , 4:40 AM

更新日期：2024.04.07 , 8:02 PM

版权声明：本文采用Crative Commons 4.0 许可协议进行许可

CATALOG
  1. 一、术语概念
  2. 二、基本思想
  3. 三、适用情况
  4. 四、基本步骤
  5. 五、程序设计
    1. 5.1 一般的算法设计模式如下
      1. 5.1.1 问题框架
      2. 5.1.2 递归的算法框架
      3. 5.1.3 非递归回溯框架
    2. 5.2 回溯法搜索子集树
    3. 5.3 回溯法搜索排列树
  6. 六、经典运用：
数据结构与算法 计算机组成原理 计算机网络 汇编语言 数据的存储与传输 操作系统 互联网标准RFC 编译链接与装载 iOS 架构与设计模式 图形处理与渲染 软件工程 音视频处理 DSL Swift Git Web
Total : 75
搜索
2022
2021
2020
AutoreleasePool GCD hexo ISA Microarch Soc CLI Shell ARM64 多线程 Docker DSL 协程 Fiber dp RunLoop SwiftUI Swift-Syntax LagMonitor CrashMonitor Log AFN