算法复习

算法分析

复杂度分析

复合变量

数组、链表、树、图等数据结构

空间复杂度

对于非递归程序，我们需要考虑复合变量大小即可
对于递归程序，需要考虑的点有
- 复合变量
- 函数调用时的参数
- 环境栈地址（environment stack address）(这个不是很懂)
- ·递归深度

时间复杂度

量度被设定为指令数量

解题方法：找到基本操作，数操作数

算法情况分析

对于一个算法，通常有最优平均和最差复杂度，最优复杂度Ω(big-Omega)是最简单的输入样例，其复杂度可能为常数级别，是用处最少的case，而 $\Theta$ (big-theta)平均情况复杂度比较难找，一般取的都是最差情况复杂度，即O(big-oh)，算法复杂度的上界往往是最常用的。

对于常见的几种情形，有

$logn<n^\alpha<a^n<n!<n^n 1 < logn < n < nlogn < n^2 < n ^3 < a^n < n!$

递归算法分析

递归树

https://www.cnblogs.com/wu8685/archive/2010/12/21/1912347.html
迭代法
Master方法

对于 $T(n)=aT(n/b) +f(n), \ k=log_ba$ 则有

$T(n) = \left\{\begin{aligned} \Theta(n^k) & \ if \quad f(n) \in O(n^{k-\epsilon}) \\ \Theta(n^klogn) & \ if \quad f(n) \in \Theta(n^k) \\ \Theta(n^klog^{k+1}n) & \ if \quad f(n) \in \Theta(n^klog^kn) \\ \Theta(f(n)) & \ if \quad f(n) \in \Omega(n^{k+\epsilon}) \text{AND af(n/b) < cf(n) for large n} \end{aligned}\right.$

贪心算法

贪心选择：自顶向下地做出贪心选择，将问题化为规模更小的子问题

条件：证明每一步所做的贪心选择最终导致问题的整体最优解

特点：

不回溯
常常使用最大增量的选择方法
使用局部优化，也导致了不一定得到的是精确解
使用需要证明

证明贪心算法的正确性

数学归纳法

归纳基础P(1)或者P(n0)为真，n0为某个自然数
P(k) => P(k+1) 或者对任意P(k) => P(n)

交换论证

从最优解出发，不断替换，同时使最优解仍然是最优解，最后得到贪心解。

例 Maximum Cardinality Disjoint Interval Problem

问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。

Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。

证明上面说的Greedy Algorithm是最优的。

下面就用第一个证明的步骤来证。

我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。

假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。

现在我们构造一个O’，O’ = O-（aj，bj）+（ai，bi）。

1）很显然，O’是这个问题的一个解，也就是说O’中的intervals没有重叠的。

在O’中，（ai，bi）前的intervals和A中的一样，所以前一部分没有重叠。在（ai，bi）后的intervals和O中的一样，所以也没有重叠，同时bi<=bj，所以（ai，bi）也不会和它相邻的重叠，所以O’中的所有intervals都没有重叠。

2）O’是一个最优解，因为他的intervals的个数和O一样。

综上，我们找到了一个最优解O’，它和A具有的共同的intervals有K个，这和我们前提假设最多有k-1个相矛盾，所以，A是最优的。证毕。

http://jalan.space/2019/12/11/2019/greedy/

https://www.cnblogs.com/cherry231/p/5267932.html

典例

货箱装船问题

目标函数为装载的集装箱数目，每次尽可能地装最轻的箱子，使船上能装的数量最大。

证明：

数学归纳法
1. 假设序列为(y1, y2, …, yn)，（按wi递增排序的货物序列）
2. **【归纳基础】**在第一步时，选取y1，如果最优解A中没有y1，则把最优解里的第一个A1替换为y1，由于y1 <= A1（即总重量不会超过C），且替换后数量仍相同，所以替换后的A’仍为最优解，换言说，最优解总是包含y1.
3. **【归纳步骤】**在第k步时，我们选择ik，需要证明的是如果ik在最优解A中，那么在第k+1步选择的ik+1也在A中。
  
  对于给定条件“ik在最优解A中”，可以认为，Sk = {y1,i2,i3…ik}，已经在最优解A中，设剩下的解从S’ = {yi | yi >= ik}中选取，只要证明，A = Sk 并上 S’的一个最优解集合 B，即可证明k+1选择ik+1也在A中。
  
  那么我们使用反证法，如果B不是S’的最优解，而是B‘，那么|B’|>|B|（B’中的解个数大于B），那么可以知道， $|A'=\{B' \cup S_k\}| > |A=\{B \cup S_k\}|$ ，即A不再是最优解，与条件相悖，即我们的证明正确。
  
  此时得证。
交换论证。
1. 首先假设最优解为O(y1, y2, …, yn)，贪心解为G(g1, g2, …, gm)
2. 那么n >= m，我们需要证明n == m
3. 设前k-1个解相同，即有O(g1, g2, …, gk-1, yk, …, yn)，G(g1, g2, …, gk-1, gk, …, gm)，我们讨论是否可以将yk替换为gk。
  
  由于贪心解的特性，所以gk总是gk-1之后最小的那一个，所以一定有gk <= yk，如果进行替换，那么解数量不变，且新重量 $W_O' <= W_O$ ，故新解O’（g1, g2, …, gk-1, gk, yk+1, …, yn)，同样为最优解。
4. 重复第3步直至将G中的gm替换完，得到O’(g1, g2, …, gm, ym+1, …, yn)，对于解{ym+1, …, yn}，由于贪心解的特性，gm一定是最后一个能取到的重量最小的货物，ym+1 >= gm，即 $W_G + y_{m+1} > C$ ，不符合题目条件，所以{ym+1, …, yn}不存在，故最优解就是G(g1, g2, …, gm)

01背包问题

贪心解无法得到最优解，一般使用密度优先的贪心策略。

贪心值和最优解的误差用以下比值的百分比来度量|优化值-贪心解值|/优化值*100%。

伪代码

SortByDensity(w, p)
for (i = 0; i < n; i++) {
	if cw + w[i] > c {
		continue
	}
	cw += w[i]
	cp += p[i]
}
return cw

k-优化算法是密度贪心算法的改进，误差可以在1/(k+1)*100%之内

k-优化算法也要先对物品按密度从大到小排序;

先将一些物品装入背包**,**然后对其余物品用贪心法;
预先装入的物品数不超过k
对所有物品数不超过k的物品子集执行上述过程**,并从中找到有最大效益值的解作为k-**优化算法的解.

例n=4,w=[2,4,6,7], p = [6,10,12,13],c = 11

使用2-优化算法：

k = 0，直接用密度贪心，得到(1, 1, 0, 0) P = 16
k = 1，得到{1}, {2}, {3}, {4}，分别对剩下的进行贪心，最后得到最大的为(1, 1, 0, 0) P = 16
k = 2，得到{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}，最后得到(0, 1, 0, 1) P = 16

伪代码

最优前缀码问题

对于前缀码问题，每个字符对应一串不相同的前缀码，使得字符串能够用一个01字符串所替代，最优前缀码就是使得频率最高的字符能够以最短的前缀码相对应以求01字符串尽可能地短。

哈夫曼归并问题

给定一个不同长度的文件序列，S={f1, f2, …, fn}，fi代表第i个文件含有的项数（可以理解为权值），使用二分归并文件成一个有序文件。

归并代价：每个树叶的深度乘以文件大小之和再减去归并次数n-1

$D = \sum_{i\in S}d(i)f_i - (n-1)$

离散里面讲了，每次选择最小的两个文件进行归并即可。

拓扑排序

拓扑排序可以用来排序AOV网络（Activity on Vertex），即活动置于结点上的网络，且网络为有向无环图，拓扑排序序列中有两个特点

每个结点出现且只有一次
若存在一条A到B的路径，那么A一定在B的前面

拓扑排序的方法使用栈来实现，首先将入度为0的结点入栈，栈不空时，出栈时将其相邻结点的入度减一，并将其放入结果序列中，并且将入度为0的结点入栈。

如果有剩余的顶点则说明图内有环路

ad9bw-t4ehr

时间复杂度为邻接矩阵： $\Theta(n^2)$ 邻接表： $\Theta(n+e)$

伪代码

计算每个顶点入度
将入度为0的结点入栈
while (栈不空) {
	出栈一个结点，将其放入拓扑序列中
	将其相邻的结点的入度减一
	若有新的入度为0的结点，则将其入栈
}
如果有剩余的入度不为0的结点则说明图中有环路

单源最短路

任给一个有向图G，每条边都有一个非负权值，路径的长度定义为路径上边的权值之和。问题要求为找到s结点到图中所有其他结点的最短路径及其长度。

Dijkstra算法

它给出，如果链路的权值非负，则最短路的子路径也是最短路（构成最优子结构）。

贪心策略为：按最短路长度从小到大依次求解。

算法为：

维护集合S，包含源节点到其他结点的最短路
从结点集合中找到一个结点v，满足源节点s到v的距离最小
更新v的邻结点的到源节点的距离值。（即假设有邻结点x，从源节点s到v到x的距离l’比s到x的距离l短，则使s到x的距离l=l’）
重复2到3直至所有结点都在S内。

Bellman-Ford算法

Dijkstra算法只适用于非负权值的图中，要解决这个问题，还得用Bellman-Ford算法

其算法为：

创建s到所有结点的向量S，除了s->s为0，其他均为正无穷
进行V-1次遍历，每次遍历都对每一条边做如下操作：如果起点的距离d1加上边权值小于终点的距离d2，则更新d2为d1+e，比如边E1 ab，起点的a的距离d1（在S里，就是源节点s到a的距离）+ e1 < 终点b的距离d2，则更新d2位d1+e1
再进行一次遍历，如果还能得到s到某些结点更短的路径，则存在负环路，否则向量就是我们的解。（如果在V-1次遍历中，到k<V-1次时的结果与k-1相同，那么可以提前结束）。

Dijkstra算法的单源最短路复杂度为O(E + VlogV)，多源最短路为\text{O(VE + V^2logV)}

Bellman-Ford算法分别为O(VE)和\text{O(V^2E)或O(V^4)}

最小生成树

对于有n个顶点的无向连通图，求具有最小成本的生成树，每个生成树具有n-1条边。

Kruskal算法

递增排序边集合E，使E = {e1, e2, …, en}
创建生成树集合T
对E进行遍历，取出e

如果e的两端点不在同一个连通分支上（即不形成环），则放入T
重复3直到|T| = n-1

证明：

**【形成命题】**对于任意n>1，算法对n阶图得到一颗最小生成树
**【归纳基础】**n=2时，只有一条边，命题正确
**【归纳步骤】**假设n个顶点时能生成最小生成树，对于n+1个顶点的图G，设图中最小权边e={i, j}，短接i, j （合并i, j结点)，得到图G’，由归纳假设，由算法，存在G’的最小生成树T’，令 $T=T'\cup\{e\}$ （将短接的i,j拉伸回来），则T是关于G的最小生成树

否则存在G的含边e的最小生成树T*，（W为生成树的总权）W(T*)<W(T)(如果 $e\notin \text{T*}$ ，在T*中加上边e，形成回路，去掉回路中任意边所得的生成树的权仍旧最小），在T*中短接e，得到G’的生成树T*-{e}，且

$W(T^*-{e}) = W(T^*)-w(e)<W(T)-w(e)=W(T')$

与T’的最优性矛盾

Prim算法

设A为生成树中的结点集合，初始化A包含图中某一结点，令B为空
在E中选取选取权值最小的边<u, v>，其中u为A中的元素，而v不在A中，并且v在V中
将v加入A中，将<u,v>加入B中
重复2，3步直至A==V

动态规划

动态规划算法具有以下特点：

用动态􏰀规划求解的问题􏰉􏰊必􏰽满􏰿足优化原理：优化解包含的子问题也是优化的。
利用优化原理，使用枚举法建立不同􏰒长度子问题的优化值之间􏰖的􏱅递归关系——动态􏰀规划方程.
子问题的数目决定算法的复杂性。

适用条件

最优子结构：如果问题的最优解是由其子问题的最优解来构造，则称该问题具有最优子结构性质。
重叠子问题：在使用递归算法自顶向下界问题时，有些产生的子问题并不总是新问题，而是已经计算过的问题，此时就可以将解保存在一个表格中，以后该子问题计算可以通过查表得到。

多段图

多段图被定义如下

**【证明最优子结构】**其问题满足最优子结构。

设s.u.v.t是一条从s到t的最短路径，则u.v.t也是一条从u到t的最短路径。
**【写出递归方程】**设c(i)为结点i到汇点的最短路长度，A(i)为i的邻结点集合，有

$\left\{\begin{aligned} &c(t) = 0 \\ &c(i) = min_{j\in A}\{c(j)+cost(i, j)\} \end{aligned}\right.$

01背包

相比课件上奇葩的从右到左从上到下和从左到右从下到上的，我们使用从左到右从上到下的显然更容易理解。

状态转移方程为

$DP[i][j]=max\{DP[i-1][j], DP[i-1][j-w_i] + v_i\}$

w[i]为i的重量，v[i]为i的价值，i代表物品的下标，j代表背包容量。max左边代表不选择i物品，右边代表选择了i物品，剩下的容量能够装到的最大值。

边际条件为

$DP[0][j] = \begin{cases} v_0 && j > w_0 \\ 0 && else \end{cases}$

伪代码

for (j = 0; j < n; j++) {
	dp[0][j] = j > w[0] ? v[0] : 0
}
for (i = 1; i < n; i++)
	for(j = 0; j < n; j++) {
		dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + v[i]}
	}
return dp[n-1][n-1]

矩阵乘法链

有M1, M2, …, Mn个矩阵相乘，使用c(i, j)代表Mi到Mj矩阵相乘的最小值。则返回值为c(1, n)

还有r数组，ri代表Mi的行数，ri+1代表Mi的列数，（可以想想为什么可以这样定义）

同时有

$c(i,j)=\begin{cases} 0 & i = j\\ r_i*r_{i+1}*r_{i+2} &i = j-1\\ min_{i\le k < j}\{c(i,k)+c(k,j)+r_i*r_{k+1}*r_{j+1}\} & i < j-1 \end{cases}$

伪代码

recur(i, j) {
	if i == j {
		return 0
	}
	if i == j - 1 {
		return r[i]*r[i+1]*r[i+2]
	}
	if i < j - 1 {
		min = INT_MAX
		for (k = i; k < j; k ++) {
			if min > recur(i, k) + recur(k, j) + r[i]*r[k+1]*r[j+1] {
				min = recur(i, k) + recur(k, j) + r[i]*r[k+1]*r[j+1]
			}
		}
		return min
	}
}

All-Pair问题

定义cij(k)为从i到j的路径，k为中间结点的最大编号

那么有

cii(k) = 0
cij(0)=wij或者∞
cik(k)=cik(k-1)
ckj(k)=ckj(k-1)

因此得出递归表达式

$c_{ij}k=min\{c_{ij}(k-1),c_{ij}(k-1)+c_{kj}(k-1)\}$

时间复杂度为O(n3)，在k次里更新一个i*j的矩阵

TSP问题

问题描述：在无向有权图中从某个给定结点出发，遍历所有结点再回到出发结点的最短路径

设s为出发点，S=V-{s}

p(i, S)为从si出发，经过所有S中的结点到达s的最短路径。L(i, S)为p(i, S)的最短路径

可以推出递归表达式：

$L(i, S) = min_{j\in S}\{w_{ij}+L(j, S-\{s_i\})\}$

分治算法

特点：

将问题分解为子问题，且子问题的规模尽可能相等，最后再把子问题的解合并

金块问题

给定一些一定大小的金块，找到里面最大和最小的金块。

对于顺序比较，是O(2n)的复杂度

如果使用分治法，每次寻找当前列表里的最大值和最小值时，只取比较前一半和后一半的最大最小值。

这样我们有

T(n) = 2T(n/2) + 2

加上的2为比较左右最大值和左右最小值的操作。

利用master方法，T(n) = $\Theta(n)$

归并排序

每对一个数组排序时，将左右两边排好序的序列组成一个新的序列。

这句话是不是没听懂？但这就是归并排序的算法。

每次都对一个完整的序列做划分，划分出来的前后又做划分，最终会导致前后两个序列都只含一个数，这时候再将其开始组合，1生2，2生4，最后能够组合成一个完整排好序的数组。

其伪代码可以写成。

MergeSort(array, start, end) {
	mid = (start + end) / 2
	MergeSort(array, start, mid)
	MergeSort(array, mid+1, end)
	Merge(array, start, mid, end) // 组合已经排序的两个数组
}

时间复杂度

对于二分的归并，有n>1时T(n) = 2T(n/2) + cn

根据主定理，有logab = 1，即logab = k，所以复杂度为 $\Theta(nlogn)$

快速排序

分治法不仅仅能生产出归并排序，还能产生出快速排序，重点是这两种排序的时间复杂度还很低，分治法nb。

在快速排序中，n个元素被分为三个部分，左序列右序列和中间的pivot。

在左序列中，所有元素小于等于pivot，而右序列中的所有元素大于等于pivot。

因此，如果我们不断地找到每个序列的pivot，在找到底的时候，整个数组也被排序完毕。

方法是：

取序列的第一个元素为pivot，不断进行交换操作，直至pivot前面的元素小于等于pivot，后面的元素大于等于pivot。
然后对pivot两边的序列做第1步，直至序列里只有一个元素。

不难发现，快速排序算法的难度在于第1步之中的交换操作。具体操作为：

从后往前，找到第一个比pivot小的元素，与pivot交换
然后从原来pivot的位置往后找，直至找到一个比pivot小的元素，与pivot交换。
重复以上两步，直到两边的下标交汇。

复杂度分析

最坏情况，每次pivot都是取的当前序列中最大或者最小的元素，即

$\begin{align*} T(n) &= T(0) + T(n-1) + \Theta(n) \\ &= \Theta(1) + T(n-1) +\Theta(n) \\ &= T(n-1) + \Theta(n) \\&=\Theta(n^2) \end{align*}$

最好情况，每次pivot结束后总是把当前的数组分为两半，即 $T(n) = 2T(n/2) +\Theta(n)$ ，由master方法，f(n)中logn的次数为0，且logab = 1，所以结果为 $\Theta(nlogn)$

如果需要计算平均情况

当n>1时，有

$T(n)=cn+\frac{1}{n}\sum\limits^{n-1}\limits_{s=0}[T(s)+T(n-s-1)]$

假设关键字彼此不同则

$\begin{align*} T(n) & \le n+1+\frac{1}{n}\sum\limits^{n-1}\limits_{s=0}[T(s)+T(n-s-1)] \\ nT(n) & \le n(n+1) + 2\sum\limits^{n-1}\limits_{s=0}T(s) \\ (n+1)T(n+1) & \le (n+2)(n+1) + 2\sum\limits^{n}\limits_{s=0}T(s) \\ ... \\ \frac{T(n+1)}{n+2} & = \frac{T(n)}{n+1} + \frac 2 {n+2} \\ \end{align*}$

这个式子还挺复杂的，到这一步后令f(n) = T(n) / (n+1)

即f(n) = f(n-1) + 2/(n+1)，递归得 $f(n) = f(1) + \sum\limits^{n+1}\limits_{i=3}(2/i)$

计算 $\sum\limits^{n+1}\limits_{i=3}(2/i)$ 可以用定积分粗略估计。。最后结果得到f(n) ~ 2lnn

所以结果T(n) =2 (n+1)f(n) = $\Theta(nlnn)$

回溯算法

回溯算法的核心就是深度优先搜索。

同时要了解两个树，一个是子集树，一个是排列树，这分别讲的是解题算法的状态空间，所有回溯算法的状态空间树都能划分为这两种。例如子集树，时间复杂度为 $\Omega(2^n)$ ，例如01背包问题，排列数的时间复杂度为 $\Omega(n!)$ ，例如旅行商问题。

回溯算法适用于存在性问题和优化问题。

存在性问题是指：能否找到满足题意条件的解。例如最短路径问题。

优化问题是指：给定一组约束条件，在满足约束条件的元组中找到使目标函数最大化的解。例如01背包问题。

不过话说回来，虽然回溯算法的核心是深度优先搜索，但是加入了剪枝操作，即在搜索到某一结点时，首先判断这个结点往下走是否可能包含问题的解，如果不，则删去这个结点。

问题的解空间

在用回溯法解决问题的时候，常常需要先定义问题的解空间。解空间往往用向量集表示。向量集是一个定长元组。

显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。
解空间：所有满足显约束的解向量构成了该实例的解空间。

限界函数

限界函数是对元组进行计算看是否需要剪枝的函数，算法还需要比较简单。

剪枝函数

包括约束函数和限界函数，约束条件剪去不满足约束的左子树，限界函数剪去的得不到最优解的右子树

空间复杂度

如果解空间树从根节点到叶结点的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。显式存储整个解空间则需要 $O(2^{h(n)})$ 或 $O(h(n)!)$

01背包问题

上界约束：就是剩下的最大价值加上当前已得价值是否大于当前最大价值，如果大于则展开右子树，否则不展开。

伪代码为

Backtrack(i) {
	if i == n {
		best = cp
		return
	}
	if w[i] + cw <= c {
		cw += w[i]
		cp += p[i]
		Backtrack(i+1)
		cw -= w[i]
		cp -= p[i]
	}
	if cp + rest <= best {
		Backtrack(i+1)
	}
}

货箱装船问题

现在有两艘船，所有货物的重量小于两艘船的载重和c1+c2，装载方案为：首先让第一艘船尽可能地装满，然后去装第二艘船，即等价于，求第一艘船能装满的最大重量。

约束函数为：cw+wi > c1 -> false

限界条件为：cp+rest <= bestp -> false

伪代码类似01背包

n皇后问题

n元组可定义为(x1, x2, …, xn)，xi是放在第i行的皇后所在的列号，于是解空间是由 $n^n$ 个n元组组成

约束函数仅仅要求1<=xi<=n即可

限界函数为xi != xj，且|i-j| != |xi-xj|

通过限界函数，可以剪枝原来的解空间为n!

伪代码

x[1] = 0
int k = 1
while (k > 0) {
	x[k] += 1
	while x[k] <= n && !place(k) {
		x[k] += 1
	}
	if x[k] <= n {
		if k > n {
			sum ++ // 解+1
		} else {
			k++;
			x[k] = 0
		}
	} else {
		k--;
	}
}

子集和数问题

假定有n个不同的正数，要找到一个子集使得其和数为M

限界函数为：cw+rest < M -> true

该问题的解空间树显然为一个子集树

限界函数的强化

假如Wi按递增排列，那么限界函数可以变为 cw + w[i] > M -> false

可以写出伪代码

backtrack(i, rest) {
	if rest == 0 {
		return x
	}
	if w[i] <= rest {
		x[i] = 1
		backtrack(i+1, rest-w[i])
	} else {
		x[i] = 0
		backtrack(i+1, rest)
	}
}

TSP问题

要遍历所有结点，只是顺序决定了费用大小，所以解空间是排列数。

当i=n时，检查x[n-1]到x[n]和x[n]到x[1]的边是否存在，如果存在则继续计算回路费用。

伪代码为

backtrack(i) {
	if (i == n) {
		if edge(n-1, n) && edge(n, 1) {
			if sum(1, n) > best {
				best = sum(1, n)
			}
		}
	} else {
		for node in unselectedNodes {
			if sum(1, n) + edge(n, node) < best {
				x[i] = node
				backtrack(i+1)
			}
		}
	}
}

分支限界算法

分支限界和回溯法区别在哪？

求解目标，回溯法会遍历所有可能的结果，得到所有解或者最优解，而分支限界的求解目标则是

找出满足问题条件的一个解，比如拿回溯的状态空间树来，在第一个满足条件的解时就已经可以返回了。
搜索方式，分支限界法一般用广度优先或者最小成本优先的方式搜索。

在分支限界法中，对每个活结点只有一次展开的机会，而回溯里面，一个活结点有多次展开的机会（二叉空间树时，如果可以展开左子树会先进入到左子树的展开过程，之后再来展开右子树）。在这次机会里，活结点的儿子如果包含不可行解或非最优解，则会被舍弃（即不满足限界函数或者约束函数），其他可行的儿子被添加到活结点表中。

限界函数的构造

在分支限界算法中，限界函数的构造变得更加重要，限界函数f(x)通常有两个部分构成，g(d)和h(d)，g(d)为当前已有成本值，h(d)为从d结点到达目标的期望成本值。

分支限界框架

常见的两种为FIFO Queue和Priority Queue，都是虽然都是队列，但是一个是使用队列的数据结构，一个是使用堆的数据结构来实现的。上文讲到，每展开一个活结点时，会将可行的儿子结点添加到活结点表中，我们说的队列就是这个表的数据结构。

来看第一个应用

01背包问题

优先队列分支限界法

设cost(x)为可行解的成本，最小优化问题要求找有最小成本的可行解，定义任一结点x的成本函数c(x)为，如果x为可行叶结点，则c(x) = cost(x)，否则c(x) = 状态空间树上以x为根的子树中可行解成本的最小值，若子树无可行解则c(x) = $\infin$

然后对B展开，左子树不满足约束条件，右子树可行，加入优先队列，由于c(E) =25，故优先队列为[E, C]

然后对E展开，左子树由于约束条件不展开，右子树加入优先队列，当前优先队列为[C, K]

对C展开，加入F，队列为[F, K]

展开F，到达叶子结点，算法结束。

FIFO队列分支队列

这方法引入一个U值，作为最优成本值，成本为没有选择的物品的价值总和，每次展开活结点时更新U值。若c(x) >= U，则说明该结点的最低成本大于等于最优成本，它的子节点只可能大于或者等于最优成本值，则不选择展开该活结点。

入队顺序为A, B, C, E, K, F, L（先进先出）

最后的U值为45，选择L叶子节点的所在路径。

我是一条分割线

那么可以总结一下做题思路

找到c(x)函数，其被定义为该结点的最小成本值，也就是下界。
找到限界函数，也就是上界，用于更新结点的最大可能成本，并且每当最大可能成本小于最优成本值U时，更新最优成本值。
在展开过程中，如果c(x) >= U 且结点不为叶子结点，即可以不展开该活结点。

作业调度问题

有n个作业，一台处理器，每一个作业由(p, d, t)组成，p为罚款额、d为截止期、t为完成该任务所需的处理机时间。

需要找到完成这些作业罚款额最小的可行作业子集。令下界函数为已确知的罚款额，

优先队列分支限界

对于这个问题，同样地可以采取下界上界，下界为当前成本，上界为最优成本，同时有约束函数，即currentTime < limittime。

1展开 [2, 3]

2展开 5由于限界函数被去掉 [4, 3]

4展开 8由于约束函数被去掉 [3, 9]

3展开 [6, 9]

12展开 [25, 9]

得到解

TSP问题

限界函数为总花费