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

2020-04-10  本文已影响0人  Tenloy
目录
- 学习回溯和分支限界法之前了解一些术语
- 基本思想
- 适用情况
- 基本步骤
- 程序设计
  - 一般的算法设计模式
  - 子集树与排列树
- 经典运用

深度优先搜索 + 剪枝。回溯法的求解目标一般是找出解空间树中满足约束条件的所有解。

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

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

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

# 基本思想：

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

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

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

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

# 适用情况

有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。(找出解空间树中满足约束条件的所有解)
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数较大的问题。

# 基本步骤：

  1. 针对所给问题，定义问题的解空间
    首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。通常这个解空间是非常巨大的，所以搜索一个目标解的代价是很难想象的。为了使回溯算法更有效率，我们必须缩小搜索空间。
  2. 确定易于搜索的解空间结构(典型的组织方式是图、树-排列树/子集树等)
  3. 从根节点开始，以深度优先方式搜索解空间
  4. 在搜索过程中用剪枝函数避免搜索进入不可能得到解的子空间。

# 程序设计

## 一般的算法设计模式如下：

（1）问题框架

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

（2） 递归的算法框架

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

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] 置空值等）;
            }
        }
    }
}

（3）非递归回溯框架（递归转非递归，这里可以参考树的遍历，或者看上篇博客——递归算法介绍）

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)!)内存空间。

## 子集树与排列树

回溯法解题的时候常遇到两种类型的解空间树：

子集树

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

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);
      }
}
排列树

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

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]);
      }
}

# 经典运用：

上一篇下一篇

猜你喜欢

热点阅读