分支限界法（Branch and Bound）是一种用于求解组合优化问题的经典算法，常用于解决最优化问题，如旅行商问题（TSP）、背包问题、任务分配问题等。

它与回溯法类似，但目标不同：回溯法通常用于找到所有解（或一个可行解），而分支限界法用于找到最优解。

求解过程

设 $x=(x_1, x_2, \cdots, x_n)$ 为可行解的元组，对每个可行解有一个成本值 $\text{cost}(x)$。

最小成本优化问题就是求使得 $\text{cost}(x)$ 达到最小的可行解 $x$。

定义状态空间树上任一节点 $x$ 的成本函数 $c(x)$：

• 如果 $x$ 为可行叶节点则 $c(x) = \text{cost}(x)$
• 否则，定义 $c(x)$ 为 从 $x$ 展开的状态空间树能得到的最小成本值（状态空间树上以 $x$ 为根的子树中可行解成本的最小值）。如果它的子树中无可行解则 $c(x)=\infty$

分支

一个节点成为 $E$ 节点后，它要展开它的所有子节点并将这些子节点放在一个称为活节点表的数据结构中。从活节点表中的节点可以展开所有状态空间树的节点，即广度优先遍历状态空间树.

活节点表可以是FIFO，LIFO和优先级队列。当使用优先级队列时必须对活节点表中的节点赋一个权值。

按一定的规则从活节点表中取出一个节点作为 $E$ 节点进行展开。

检索

如果活节点表中每个节点以 $c(x)$ 为权值，每次从活节点表中取出最小权值节点作为 $E-$ 节点，则算法能很快找到优化解。但是，在展开 $x$ 前不可能知道 $c(x)$ 的值，不过有可能从历史信息获得 $c(x)$ 的某一下界 $\hat{c}(x)$。

以 $c(x)$ 的下界估值 $\hat{c}(x)$ 做为活节点表中节点的权值，每次取出有最小 $\hat{c}(x)$ 的节点进行展开。

要求设计的 $\hat{c}(x)$ 满足：当 $x$ 为可行叶节点时 $ĉ(x)=\text{cost}(x)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

E=T;
// 置活节点表为空

while(true) {
    if E是可行叶节点 return;
    for E的每个子节点x {
        Add(x);
        parent(x) = E;
    }
    delete(E);  
}   

delete(E) 表示从活节点表中取出有最小 $\text{cost}(x)$ 的活节点并从中删除之。

限界

令 $U$ 为当前获得的最优成本值。设 $x=(x_1, x_2 \cdots, x_k)$，如果 $\hat{c}(x) \geqslant U$ 则停止展开子节点 $x$ （即不将其放入活节点表）。

$U$ 初始值设为 $\infty$，此后每次得到一个新的可行解则用其成本值对 $U$ 加以修改，即令

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

E = T; 
U = INF;
// 置活节点表为空

while(true) {
    for E的每个子节点x {
        if x是叶节点 {
            U = min(U,cost(x));
        } 
        if c(x)<U {
            Add(x);
            parent(x) = E;
        }
        if 活节点表为空 return;
    }
    delete(E);
    if c(E) >= U return; 
} 

算法结束时，如果 $\hat{c}(E) \geqslant U$，活节点表中其它节点 $x$ 的下界也满足：$\hat{c}(x) \geqslant \hat{c}(E) \geqslant U$，展开这些活节点不能产生更好的解，$U$ 的值即为优化值。

为加快搜索的速度，在每个中间节点 $x$ 处可进一步估计展开 $x$ 能得到的优化成本值的某一上界 $u(x)$，并使用

修改 $U$ 的值。从 $x$ 展开得到的任何一个可行解都可作为 $u(x)$。

问题举例

作业调度问题

已知 $n$ 个作业，$1$ 台处理机，每个作业 $i$ 对应一个三元组 $(p_i, d_i, t_i)$，分别表示罚款额、截止期、需要的处理机时间。

求可行的作业子集 $J$，使得罚款额 $\sum p_j$ 最小（其中 $j$ 为不在 $J$ 中的作业）。

对于每个节点 $x$，快速计算一个可行解，并以该可行解的成本值记为 $u(x)$，修改 $U$ 的值。下界 $\hat{c}(x)$ 可估计为展开到 $x$ 时已得到的罚款额 $\displaystyle \sum_{j=1}^{k}(1-x_j)p_j$。

例如取 $x(k+1)=\cdots=x(n)=0$ 或用贪心法快速得到一个可行解。算法每生成一个子节点时就用 $u(x)$ 修改 $U$。

例如，设4个作业的三元组 $(p_i,d_i,t_i)$ 分别为 $(5,1,1)$，$(10,3,2)$，$(6,2,1)$，$(3,1,1)$。

状态空间树如下：

注意，这里的每个节点并非有序排列，仅表示选择了对应的任务。例如节点12可能的调度有 $\{1,2,3\}$，$\{1,3,2\}$，$\{2,1,3\}$，$\{2,3,1\}$，$\{3,1,2\}$，$\{3,2,1\}$

执行剪枝限界后的状态树：

故优化解为 $\{2,3\}$，此时罚款额为8。

旅行商问题

设 $f=(e_1, e_2 \cdots, e_n)$ 为一条周游路线：$e_i$ 来自邻接矩阵的第 $i$ 行的边，所有 $e$ 不同列。则 $\text{cost}(e_i) = A(i,j_i)$，$r_i = \min\{A(i,j) \mid 1 \leqslant j \leqslant n\}$。则有

称 $\displaystyle \sum_{j=1}^{n} r_j$ 为行归约数。

从矩阵的每行减去一个常数，不影响最优回路的选择。

设 $\tilde{\bm{A}}(i,j) = \bm{A}(i,j)-r_i$，则称 $\tilde{\bm{A}}$ 为行归约后的矩阵，进一步对 $\tilde{\bm{A}}$ 做列归约得到矩阵 $\bm{R}$ 和归约数 $\displaystyle \sum_{j=1}^{n} c_j$，则

以此为基础，可以得出求解方法：

• 令 $j$ 为 $\bm{R}$ 的子节点且不是叶节点，则 $$\hat{c}(i \rightarrow j) = \hat{c}(i)+A(i,j)+r$$其中 $r$ 为节点 $j$ 矩阵的归约数，$A(i,j)$ 为 归约矩阵 $\bm{R}$ 的边 $(i,j)$ 的权值。然后进行如下操作得到 $j$ 处的矩阵：
  • 将 $\bm{R}$ 的归约矩阵中 $i$ 行 $j$ 列置为 $\infty$（禁止再选择节点 $i$ 的出边和的 $j$ 入边）。
  • 将 $A(j,1)$ 置为 $\infty$ （防止立即返回）。
  • 对其归约得到 $j$ 处的矩阵。
• 如果 $j$ 为叶节点，$\hat{c}(j)$ 即为根到此叶节点的周游路线成本。

📝 备注

每行每列均含有 $0$ 的矩阵称为规约矩阵。假设第 $i$ 行的约数为 $t_i$，第 $j$ 列的约数为 $r_j$ $(1 \leqslant i,j \leqslant n)$。那么各行各列的约数之和

$$L = \sum_{i=1}^n t_i + \sum_{j=1}^n r_j$$

称为矩阵约数。

例如，设邻接矩阵

上述矩阵的行约数等于 $10+2+2+3+4=21$，行规约后的矩阵为

对行规约后的矩阵做列归约得约数 $1+0+3+0+0=4$，列规约后的矩阵为

则根节点的约数 $r=21+4=25$，即 $\hat{c}(1)=25$。

若接下来的路径为 $(1,2)$，则节点2对应的矩阵为

已是归约矩阵，则 $\hat{c}(1 \rightarrow 2)=25+10=35$。