Fork me on GitHub

回溯法和分支定界法概述

发表于 | 分类于 | | 本文总阅读量 次
要求解一个问题，最可靠的一种方法是：列出所有候选解，然后逐个检查，在检查所有或部分候选解之后，便可找到所需要的解。理论上只要候选解数量有限，这种方法就是可行的。不过实际中，这种方法很少用，因为候选解的数量通常都非常大（比如是实例大小的指数级，甚至是阶乘），无法在合理的时间内解决。回溯法和分支定界法是对候选集进行系统检查的两种方法。

1. 概述

要求解一个问题，最可靠的一种方法是：列出所有候选解，然后逐个检查，在检查所有或部分候选解之后，便可找到所需要的解。理论上只要候选解数量有限，这种方法就是可行的。不过实际中，这种方法很少用，因为候选解的数量通常都非常大（比如是实例大小的指数级，甚至是阶乘），无法在合理的时间内解决。

回溯法和分支定界法是对候选解进行系统检查的两种方法。这两种方法使最坏情况和一般情况下的求解时间大大减少。事实上，这两种方法可以省去对很大一部分候选解的检查，同时还能够找到所需要的解。一般回溯法使用深度优先方法搜索树，而分支定界法使用广度优先或最小耗费方法搜索树。

当需要求解NP-复杂问题的最优解时，使用回溯法和分支定界法来系统检查候选解经常可以得到最好的算法。相对而言，分支定界法的空间需求比回溯法要大得多，因此当内存容量有限时，回溯法常常更容易成功。

2. 回溯法

2.1. 算法思想

回溯法（backtracking）是搜索问题解的一种系统的方法。回溯法的步骤如下：

  1. 首先需要定义问题的一个解空间（solution space），这个空间至少包含问题的一个解。比如在$n$个对象的01背包问题中，可以把$2^n$个长度为$n$的01向量的集合定义为解空间，这个解空间集合代表着向量$x$取值0或1的所有可能。当$n=2$时，解空间为{(0,0),(0,1),(1,0),(1,1)}；
  2. 组织解空间，使解空间便于搜索。典型的组织方法时图或树。如下图是用树形结构描述两个对象的01背包问题的解空间，每条边，向左表示1，向右表示0。从根结点到叶节点的每条路径都是解空间的一个元素。从根节点A到叶节点E的路径所表示的解为$x=[1,0]$。根据实际情况，从根节点到叶节点的路径中一部分或全部都可能不是解。
    1
    2
    3
    4
    5
         A
       /   \
      B     C
     / \   / \
    D   E F   G     每条边向左表示1，向右表示0.
  3. 一旦确定了解空间，这个空间即可按深度优先方式从开始节点进行搜索。开始节点既是一个活动节点（live node）又是一个E-节点（expansion node）。从E-节点试着移到一个新节点。如果从当前的E-节点移到一个新节点，那么这个新节点就变成一个活动节点和新的E-节点，而原来的E-节点仍是一个活动节点。如果不能移到一个新节点，那么当前节点就“死掉”，即不再是活动节点。然后返回到最近的活动节点，这个活动节点就变成了新的E-节点。当已经找到了答案或者不再有活动节点时，搜索过程结束。在上述问题中，开始节点即是根节点。

当问题需要$n$个元素的一个子集来优化函数时，解空间树称为子集树（subset tree）。比如01背包问题，解空间树便是一个子集树。这样一颗树有$2^n$个叶节点，全部节点有$2^n-1$个。因此，访问树中所有节点的每一个算法都要耗时$O(2^n)$。

当问题需要$n$个元素的一个排列来优化函数时，解空间树称为排列树（permutation tree）。比如旅行商问题，解空间树便是一颗排列树。这样的树有$n!$个叶节点，遍历树中所有节点的每一个算法都要耗时$O(n!)$。

2.2. 优化策略

确定一个新到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索过程。如果不能，则移动到该节点的任何一颗子树都是无意义的，这个节点可被立即“杀死”。用来杀死活动节点的策略称为界定函数（bounding function）。比如01背包问题中，杀死那些不可行解的节点。

2.3. 小结

回溯法的步骤如下：

  1. 定义一个解空间，它包含对问题实例的解；
  2. 用适合于搜索的方式组织解空间；
  3. 用深度优先方式搜索解空间，利用界定函数避免进入无解的子空间。

3. 分支定界法

3.1. 算法思想

分支定界法（branch and bound）是另一种系统地搜索解空间的方法。它与回溯法的主要区别在于E-节点的扩充方式。当一个节点变为E-节点时，从该节点移动一步即可到达的节点都是生成的新节点。在生成的节点中，那些导出可行解的节点被舍弃，剩余节点加入活动列表，然后从表中选择一个节点作为下一个E-节点。将选择的节点从表中删除，然后扩展该节点。这种扩展过程一直持续到一个解找到了或活动表表成为空表。

有两种常用的方法可用来选择下一个E-节点：

  • 先进先出（FIFO）：从活动节点表中取出节点的顺序与加入节点的顺序相同。活动节点表于队列相同。
  • 最小耗费或最大收益法：每个节点都有一个对应的耗费或收益。若搜索的是耗费最小的解，则活动节点表可以组织成最小堆，下一个E-节点是耗费最小的活动节点。若搜索的是收益最大的解，则活动节点表可以组织成最大堆，下一个E-节点是收益最大的活动节点。

4. 总结

一般来说，在内存利用方面，回溯法优于分支定界法。回溯法需要的内存是O(解空间的最长路径长度)，而分支定界法所占用的内存为O(解空间大小)。因此在实际应用中，在回溯法还没有超出时间的上限之前，分支定界法已经超出了内存的上限。