27.分支限界与剪枝

发表于 更新于 分类于 ，

分支限界与剪枝

分支限界与剪枝通过跳过不可能产生最优解的搜索路径，有效加速寻找最佳解决方案的过程。

回顾回溯

回顾：13.暴力枚举

利用回溯可以枚举排列、子集，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DFS(int cur) {     // cur 指 "current", 当前在确定第 cur 个位置是谁
    if(cur == n) {                              // 递归终点
        for(int i = 0; i < n; i ++)             // 输出一个排列
            printf(" %d" + !i, record[i]);
        printf("\n");
        return;                                 // 注意return
    }
    for(int i = 0; i < n; i ++) {               // 枚举每个元素
        if(vis[i]) continue;                    // 已放元素排除
        vis[i] = true; record[cur] = a[i];      // 标记已放本次排列第cur个为a[i]
        DFS(cur + 1);                           // 递归放第cur+1个
        vis[i] = false;                         // 回溯取消标记
    }
}

回溯本质上是在约束条件下枚举每个元素的所有可能性，其复杂度必然是指数级的，输入规模稍大，时间复杂度就会难以接受。

回溯的结构是搜索树，八皇后等例子已经体验到，搜索树的一些子树可以跳过不搜。跳过整个子树的操作称为剪枝。

如果有一个固定的套路可以跳过尽可能多的子树，即进行尽可能多的剪枝，就可以一定程度上让回溯跑的更快。

分支限界

最优化问题，即每一种可能性（排列或组合）都对应某种收益，希望这个收益最大化，找最优的可能性。

当回溯用来处理最优化问题，就可以维护一个搜索过程中的最好收益——每当搜到某个方案收益更大，就更新最好收益。

针对搜索树的一棵子树，如果能估算子树可能取得的最好结果，当最好结果不及已经搜到的最好收益时，这棵子树就没有搜索下去的必要，完成一次剪枝。

例：用回溯解01背包

回溯解01背包，就是枚举所有子集，在能装进背包的子集中更新获得价值的最大值。

1
2
3
4
5
6
7
8
9
void DFS(int cur) {
    if(cur == -1) {                             // 递归终点,所有元素都已确定
        // 这里计算搜到的子集能否装进背包及价值
        return;                                 // 注意return
    }
    // 由n-1~0逆序以便按字典序枚举子集
    chose[cur] = false; DFS(cur - 1);           // 不取a[cur]后确定第cur-1个
    chose[cur] = true; DFS(cur - 1);            // 取a[cur]后确定第cur-1个
}

当某一刻搜索到第 \(k\) 层，即第\(1\sim k-1\) 个物品是否取已经有一个临时决定时，就在面对一棵子树，估算这棵子树（即第\(k\sim n\)个物品取与不取）所有可能性中收益不可能超越的上限，有很多思路，其中一个思路如图：

用背包容量扣除已经放入背包的物品（\(1\sim k - 1\) 的某个子集），剩余容量全放单价最高的，且强行塞满，做一个价值估值。如果这个估值不大于之前已经搜到的最优方案，那这棵子树就不必搜下去了，即当前\(1\sim k - 1\) 选定了特定子集前提下，\(k\sim n\) 的任何子集都不用尝试了。

估算子树的最优可能性不需要是合理的方案，只需要让这个估值必定优于子树所有可能性即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DFS(int cur, int lft, int vcur) {
    // cur: 当前物品编号； lft: 剩余容量； vcur: 当前已装入价值
    if(cur == n) {
        ans = std::max(vcur, ans);
        return;
    }
    // ************************************************** //
    // 最理想情况不如已有解，剪枝
    // vsum[cur]为cur之后物品价值之和；maxvw[cur]为cur之后最高单价
    if(vcur + std::min(vsum[cur], lft * maxvw[cur]) <= ans) return; 
    // ************************************************** //
    // 尝试第cur个物品装或不装
    if(lft >= w[cur]) DFS(cur + 1, lft - w[cur], vcur + v[cur]);
    DFS(cur + 1, lft, vcur);
}

// *** 之间的这部分代码，就是在枚举子集的基础上增加的分支限界规则。

例：用回溯解旅行商问题

若干城市两两之间有路，从一个城市出发，每个城市恰好经过一次并回到原点，总路程最小的方案。

枚举排列——行走城市的顺序

子树最优可能性估算策略，即搜索到 \(k\) 步某个走法情况下，后面所有走法里路程最短可能性：

  • 剩下每一步都走全局最短边
  • 剩下每一步都走剩下最短边
  • 剩下每一步都走所在点发出的最短边

以上策略是否都“对”，哪个最“好”

“对”的策略：估算的值一定比所有可能性都优，因为当估值差于已经得到的解，就剪枝，如果估值不能保证比所有可能性更优，就可能导致剪枝错杀，错过了潜在最优解。

“好”的策略：估值比所有可能性更优的前提下，越贴近实际可能性越好。因为估值瞎猜一个很极端的值，也能做到是“对”的，但“对”不表明有用，它越贴近真实可能值，就越有可能比已经得到的解差，才越可能实现剪枝。不能剪枝的估值没什么用。

例：回溯解圆排列

给定若干圆的半径，各圆与底相切，求横向宽度最小的摆放顺序

先解决个小问题：两圆横向距离计算

枚举排列，找宽度最小的排列。

子树估算方案：假设剩下的圆全用剩下的最小的那个

当想不出更“好”的估值方案时，简单粗暴但“对”的估值方案仍然有用

剪枝

相对分支限界，剪枝是一个更宽泛的概念，无论用什么方式，减少搜索树的子树，都是可用的剪枝技巧

例：等长的木棒

有一堆长短不一的木棒是由等长的木棒切割成的

已知各个木棒的长度，求原先那些等长的木棒最短可能的长度

例1：5,2,1,5,2,1,5,2,1

原先为4个长度为6的木棒

例2：1,2,3,4

原先为2个长度为5的木棒

从小到大枚举等长木棒的长度，回溯尝试所有木棒拼凑出整数个该长度

一些可以尝试的剪枝思路：

  • 枚举可能的长度去拼凑，这个枚举的长度至少要被总长度整除
  • 短木棒更“灵活”，所以排序优先尝试使用更长的木棒
  • 某次构建使用的第一个最长木棒没成功，则直接回溯