分支限界法

分支限界法的基本思想

1. 分支限界法与回溯法的不同

   1. 求解目标

      回溯法求解目标是找出解空间树中满足约束条件所有解

      分支限界法的求解目标则是找出满足约束条件的一个解（或一个最优解）

   2. 搜索方式的不同

      回溯法以深度优先方式搜索解空间树

      分支限界法则以广度优先或以最小耗费优先方式搜索解空间树

2. 分支限界法基本思想

   1. 让根结点成为当前扩展结点

   2. 当前扩展结点一次性产生其所有儿子结点。

   3. 舍弃导致不可行解或非最优解的儿子结点，其余儿子结点加入活结点表

   4. 从活结点表中取下一结点成为当前扩展结点，

   5. 如果找到所需的解或活结点表为空，算法结束，否则重复步骤2,3,4。从活结点表中取下一个扩展结点：广度优先、最小耗费（最大效益）优先

   6. 广度优先和最小耗费优先的区别

      

3. 常见的两种分支限界法

   1. 队列式(FIFO)分支限界法

      按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。

   2. 优先队列式分支限界法

      按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

装载问题

有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且$\stackrel{n}{\sum\limits_{i=1}} w_i \leq c_i+c_2$

采用下面的策略可得到最优装载方案。

1. 将第一艘轮船尽可能装满；
2. 将剩余集装箱装上第二艘轮船；

队列式分支限界法

1. 检测当前扩展结点的左儿子结点，可行入队
2. 将其右儿子结点加入队列(右儿子结点一定可行)
3. 舍弃当前扩展结点。
4. 每层结点之后都加一个尾部标记-1，将活结点分层

只考虑求最大载重量，不考虑构造最优解

装载问题队列式分支限界法算法

Ew=0, Q.Add(-1) ;i=1; bestw=0；
//Ew为当前结点对应的在船的集装箱重量
while (true) {
	// 检查左儿子结点
	if (Ew + w[i] <= c) // x[i] = 1
		EnQueue(Q, Ew + w[i], bestw, i, n);
	// 右儿子结点总是可行的
	EnQueue(Q, Ew, bestw, i, n); // x[i] = 0
	Q.Delete(Ew); // 取下一扩展结点
	if (Ew == -1) { // 同层结点尾部
		if (Q.IsEmpty()) return bestw;
			Q.Add(-1); // 同层结点尾部标志
			Q.Delete(Ew); // 取下一扩展结点
			i++;} // 进入下一层
}
void EnQueue(Queue<Type> &Q, Type wt, 
Type &bestw, int i, int n)
{ if(i==n){
	if(wt>bestw)bestw=wt;
	}//叶子结点不入队列
  else Q.add(wt);
}

算法中右分支不剪枝，效率差如何改进?

算法的改进（右子树加入剪枝条件）

1. 策略：当$Ew+r \leq bestw$时，可将其右子树剪去。

   bestw:当前最优解；Ew:当前扩展结点所相应重量； r:剩余集装箱的重量和

2. 算法每一次进入左子树的时候更新bestw的值，确保右子树有效剪枝，不要等待i=n时才去更新。

// 检查左儿子结点
Type wt = Ew + w[i]; // 左儿子结点的重量
	if (wt <= c) { // 可行结点
		if (wt > bestw) bestw = wt;
		if (i < n) Q.Add(wt); // 加入活结点队列
}
// 检查右儿子结点
if (Ew + r > bestw && i < n)
	Q.Add(Ew); // 可能含最优解

入队列函数 EnQueue( ）就可以去掉了

构造最优解

class QNode
{ QNode *parent; // 指向父结点的指针
	bool LChild; // 左儿子标志
	Type weight; // 结点所相应的载重量
}

记住最优值结点，根据parent可回溯到根节点，找到最优解

// 构造当前最优解
for (int j = n ; j > =1; j--) 
{
	bestx[j] = bestE->LChild; 
	bestE = bestE->parent; 
}

解空间树中L结点构造出最优值9

根据构造最优解的算法，最优解bestx[1..3]={0,1,1}

优先队列式分支限界法

1. 活结点x的优先级:根到结点x的路径相应的载重量+剩余集装箱重量之和
2. 优先队列中优先级最高的活结点成为下一个扩展结点。
3. 用最大优先队列存储活结点表（大顶堆）
4. 以结点x为根的子树中所有结点相应的路径的载重量不会超过x的优先级。叶结点所相应的载重量与其优先级相同。
5. 一旦优先队列中有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的载重量即为最优值。此时即可终止算法的搜索过程。

注意：算法中扩展出的叶子结点要进队列

模拟优先队列（堆）

Templete<class Type >
Type MaxLoading(Type w[], Type c, int n, int bestx[]) { //优先队列分支限界法，返回最大装载量Ew，最优解bestx
MaxHeap<HeapNode<Type>> H(1000); //定义最大堆的容量为1000
Type *r=new Type [n+1];
r[n]=0;
for(int j=n-1;j>0;j--) r[j]=r[j+1]+w[j+1];
int i=1;
bbnode *E=0;
Type Ew=0;
while (i!=n+1){ //搜索子集树
	if (Ew+w[i] <= c) AddLiveNode(H, E, Ew+w[i]+r[i], true, i+1);
	AddLiveNode(H, E, Ew+r[i], false, i+1);
	HeapNode<Type> N;
	H.DeleteMax(N);
	i=N.level; 
	E=N.ptr;
	Ew=N.uweight-r[i-1];
}
for（int j=n;j>0;j--）{//构造最优解
	bestx[j]=E->lchild; E=E->parent;｝
return Ew;
}

总结

1. 回溯法与分支限界法的区别：求解目标、搜索方式
2. 分支限界法的基本思想： 五个步骤
3. 分支限界法的分类：** 队列与优先队列，同活结点表有关**
4. 装载问题的分支限界法：队列式与优先队列式，重点内容包括算法设计，剪枝条件，算法结束条件，优先队列式的优先级的定义,构造最优解

布线问题

布线问题分支限界法

0-1背包问题

算法的思想

1. 先进行预处理：将各物品依其单位重量价值从大到小排列。
2. 优先队列的优先级：已装物品价值+后面物品装满剩余容量的价值
3. 算法：
   1. 先检查当前扩展结点的左儿子结点。如果该左儿子结点是可行结点，则将它加 入活结点优先队列中，如优于当前最优值，则更新当前最优值。
   2. 当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时 （优先级大于当前最优值）才将它加入活结点优先队列。
   3. 从优先队列中取下一个活结点成为扩展结点，继续扩展。
   4. 当叶节点为扩展结点时即为问题的最优值，算法结束。

b=背包已有物品价值；cleft=背包剩余容量，从第i~n物品为剩余的物品，用剩余物品装满剩余背包容量的背包的贪心算法（主要代码如下）

while (i <= n && w[i] <= cleft) // n表示物品总数，cleft为剩余空间
{
	cleft -= w[i]; //w[i]表示i所占空间
	b += p[i]; //p[i]表示i的价值
	i++;
}
if (i <= n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包
	return b; //b为上界函数值

优先队列中的结点信息包含：

1. 当前背包价值、重量；
2. 结点的优先级（价值上界）；
3. 左孩子标志；
4. 父结点地址；
5. 本结点对应的下一个要装入背包的物品编号；

搜索算法的主代码

while (i != n+1) {// 非叶结点
// 检查当前扩展结点的左儿子结点
	Typew wt = cw + w[i];
	if (wt <= c) {// 左儿子结点为可行结点
		if (cp+p[i] > bestp) bestp = cp+p[i];
		AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}
		up = Bound(i+1);
		// 检查当前扩展结点的右儿子结点
if (up >= bestp) // 右子树可能含最优解
	AddLiveNode(up, cp, cw, false, i+1);
	// 取下一个扩展节点（略）；
}

最大团问题

回溯与分支限界算法实验：最大团问题_分支限界 最大团问题 代码实现-CSDN博客

旅行售货员问题

旅行售货员问题-分支限界法

小结

1. 队列式：活结点表是一个队列，新扩展出的满足条件的活结点追加在队尾。这里需要加入层次标志（如-1），或记录下层编号在活结点中。
2. 优先队列式：活结点表是优先队列，一般使用堆（大顶堆或小顶堆）存储， 优点是只需要O（logn）时间复杂性完成插入或者删除（取堆顶结点，即 优先级最高的结点）
3. 构造解方法， 活结点通过记录其父节点地址，及左孩子标志去，在找到最 优值时，回溯方法找到最优解。也可在扩展出的结点中记录构造的解，如 问题规模较大时，应考虑压缩存储。
4. 分支限界法的剪枝方法：
   1. 对于子集树，左右分支剪枝策略不同，
   2. 对于排列树，n叉树， 剪枝策略是相同的。
5. 算法的结束控制：
   1. 队列式分支限界， 活结点表为空
   2. 优先队列式，叶子结点成为扩展结点(在确认后面的活结点不存在 更好的解)或队列为空。通常叶子结点加入优先队列中。