算法分析五：回溯法与分⽀限界法-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法分析五：回溯法与分⽀限界法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、回溯法

1. 基本思想与解题步骤

基本思想：
把问题的解空间转化成了图或者树的结构表⽰，然后使⽤深度优先搜索策略进⾏遍历，遍历的过程中记录和寻找所有可⾏解或者最优解。
解题步骤：

针对所给问题，定义问题的解空间；
确定易于搜索的解空间结构；
以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。

2. ⼦集树与排列树

2.1 ⼦集树

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

void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
 x[t]=i;
if (constraint(t)&&bound(t)) backtrack(t+1);
 }
}

算法分析五：回溯法与分⽀限界法

2.2 排列树

当所给问题是确定n个元素满⾜某种性质的排列时，相应的解空间树称为排列树。例如旅⾏售货员问题(如下图)的解空间树是⼀棵排列树，这类排列树通常有n!个叶结点。遍历⼦集树的算法需O(n!)计算时间。

void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
 swap(x[t], x[i]);
if (constraint(t)&&bound(t)) backtrack(t+1);
 swap(x[t], x[i]);
 }
}

算法分析五：回溯法与分⽀限界法

2.3 满m叉树

找满足某种特性的n个元素取值的一个组合。
这类问题的解空间称为满m叉树。
n皇后问题
图的m着色问题
最小机器设计问题
参考学习：回溯法、子集树、排列数、满m叉树
算法分析五：回溯法与分⽀限界法
除了叶节点之外，每一个节点都有3个子节点，这就代表的3种选择。

3. 回溯算法的实现：递归与迭代

一说：
算法分析五：回溯法与分⽀限界法
二说：

3.1 递归

//针对N叉树的递归回溯⽅法
void backtrack (int t)
{
 if (t>n) output(x); //叶⼦节点，输出结果，x是可⾏解
 else
 for i = 1 to k//当前节点的所有⼦节点
 {
 x[t]=value(i);//每个⼦节点的值赋值给x
 //满⾜约束条件和限界条件
 if (constraint(t)&&bound(t))
 backtrack(t+1);//递归下⼀层
 }
}

3.2 迭代（递推）

void iterativeBacktrack ()
{
  int t=1;
   while (t>0) {
       if(ExistSubNode(t)) //当前节点的存在⼦节点
      {
        for i = 1 to k //遍历当前节点的所有⼦节点
         {
            x[t]=value(i);//每个⼦节点的值赋值给x
           if (constraint(t)&&bound(t))//满⾜约束条件和限界条件
           {
            //solution表⽰在节点t处得到了⼀个解
            if (solution(t)) output(x);//得到问题的⼀个可⾏解，输出
             else t++;//没有得到解，继续向下搜索
          } 
      }
    }
     else //不存在⼦节点，返回上⼀层
    { 
          t--;
    }
  }
}

4.避免无效搜索的策略

在搜索过程中，通常采⽤两种策略避免⽆效搜索：

⽤约束条件剪除得不到可⾏解的⼦树
⽤⽬标函数剪取得不到最优解的⼦树
（这两种⽅式统称为：剪枝函数）

5.经典案例问题

0-1背包问题（子集树）：回溯法求0/1背包的解空间树
装载问题：
图的m着⾊问题：
n后问题（n叉树）：
货郎问题（排列数）：

二、分⽀限界法

1. 基本思想与解题步骤

问题的解空间树是表⽰问题解空间的⼀棵有序树，常见的有⼦集树和排列树，满m叉树。
在搜索问题的解空间树时，分⽀限界法和回溯法的主要区别在于它们对当前扩展节点所采⽤的扩展⽅式不同。在分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展节点。活结点⼀旦成为扩展节点，就⼀次性产⽣其所有⼉⼦节点。在这些⼉⼦节点中，导致不可⾏解或导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活结点表中。此后，从活结点表中取下⼀节点为当前扩展节点。并重复上述节点扩展过程。这个过程移⾄持续到找到所需的解或活结点表为空为⽌。

总结如下

基本思想：
分⽀限界法常以⼴度优先或以最⼩耗费有限的⽅式搜索问题的解空间树。
解题步骤
1.（定义问题解空间，确定解空间组织结构，）按广度优先遍历的方法求解空间树。
2.在求解过程中，每⼀个活结点只有⼀次机会成为扩展节点。活结点⼀旦成为扩展节点，就⼀次性产⽣其所有⼉⼦节点。
4.在这些⼉⼦节点中，导致不可⾏解或导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活结点表中。此后，从活结点表中取下⼀节点为当前扩展节点。
4.重复上述节点扩展过程。这个过程移⾄持续到找到所需的解或活结点表为空为⽌。

注：扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在深度优先搜索中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。

2. 分支限界法的分类

从活结点表中选择下⼀扩展节点的不同⽅式导致不同的分⽀限界法。最常见的有以下两种⽅式。

队列式分⽀限界算法
队列式分⽀限界法将活结点表组织成⼀个队列，并按队列的先进先出原则选取下⼀个节点为当前扩展节点。
在活结点表中，按照FIFO先进先出原则选取下一个结点做扩展结点。
优先队列式分⽀限界算法
优先队列式的分⽀限界法将活结点表组织成⼀个优先队列，并按优先队列中规定的节点优先。
活结点表中的每个结点对应了一个耗费或收益（其实就是如果扩展该结点，会带来多大的效益），以此决定结点的优先级。 注：通常采用堆实现。