【算法】四、分支限界法

分支限界法（Brach-and-Bound）

分支限界法与回溯法类似，也是在问题的解空间树上搜索问题的解，通过限界函数进行剪枝，但采用BFS广度优先策略搜索。

4.1基本思想

首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]；然后，按照广度优先策略搜索问题的解空间树：

1.在当前扩展结点处，生成所有儿子结点，估算所有儿子结点对目标函数的可能取值，舍弃不可能通向最优解的结点 (剪枝），将其余的加入到活结点表（用队列组织）中。

2.在当前活结点表中，依据先进先出或某种优先级(最小耗费或最大效益）策略，从当前活结点表中选择一个结点作为扩展结点。

3.重复(1)-(2)步骤，直到找到所需的解或活结点表为空。

分支限界法与回溯法的区别

1.求解目标不同

回溯法的求解目标一般是找出满足约束条件的所有解或最优解

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

2.搜索方式不同

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

分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树

3.空间复杂度不同

这里介绍两种从活结点表选择下一个扩展结点的方法：

1.队列式分支限界法：按照队列先进先出原则选取下一个结点为扩展结点

2.优先队列式分支限界法：以最小耗费（最大效益）优先的方式搜索解空间树，即按照优先队列中规定的优先级选取优先级最高的结点称为当前扩展结点。常用堆（大根堆/小根堆）来实现。

4.2具体问题

以0/1背包问题为例具体来讲解分支限界法

4.2.1 0/1背包问题

问题描述：有n个重量分别为{w1，w2， … ，wn} 的物品，它们的价值分别为{v1，v2， … ，vn}，给定一个容量为C的背包。 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品重量和不超过C，且具有最大的价值。

确定剪枝函数（限界函数）

与回溯法类似

 若为队列式分支限界法，则结点声明如下：

struct NodeType { //队列中的结点类型
	int no; //结点编号，从1开始
	int t; //当前结点在搜索空间中的层次
	int w; //当前结点的总重量
	int v; //当前结点的总价值
	int x[MAXN]; //当前结点包含的解向量
	double leftV; //剩余物品价值上界
};

若为优先队列式分支限界法，则结点声明如下：

struct NodeType { //队列中的结点类型
	int no; //结点编号
	int t; //当前结点在搜索空间中的层次
	int w; //当前结点的总重量
	int v; //当前结点的总价值
	int x[MAXN]; //当前结点包含的解向量
	double ub; //上界
	bool operator<(const NodeType &s) const { //重载<关系函数
		return ub<s.ub; //ub越大越优先出队
	}
};

 确定解向量：

我们知道分支限界法在搜索解空间树时，对于结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层地向上回溯，因此，当搜索到某个叶子结点且该对应一个可行解时，如何保存对应的解向量呢？

有两种可行办法：

1.每个结点带有一个可能的解向量。这种做法比较浪费空间，但实现起来简单。

2.每个结点带有一个双亲结点指针，当找到最优解时，通过双亲指针找到对应的最优解向量。这种做法需保存搜索经过的树结构，每个结点增加一个指向双亲结点的指针。

分支限界法求解的三个关键问题如下：

1.确定合适的限界函数，以及函数的界[down,up]。

2.如何组织待处理的活结点表。

3.如何构造解向量。

具体实现代码：

#include<stdio.h>
#include<queue>
#define MAXN 51
#define C 30
using namespace std;
int w[MAXN]= {0,16,15,15}; //背包的重量
int v[MAXN]= {0,45,25,25}; //背包的价值
int bestx[MAXN]; //最优解
int n=3; //背包个数
int bestv;
struct NodeType { //队列中的结点类型
	int t; //当前结点在搜索空间中的层次
	int w; //当前结点的总重量
	int v; //当前结点的总价值
	int x[MAXN]; //当前结点包含的解向量
};

void bfs() {
	NodeType e,e1;
	int t;
	queue<NodeType>qu;
	e1.t=0;
	e1.no=1;
	e1.v=0;
	e1.w=0;
	e1.leftV=C;
	for(int i=1; i<=n; i++)
		e1.x[i]=0;
	qu.push(e1);
	while(!qu.empty()) {
		e=qu.front();
		qu.pop();
		t=e.t;
		if(t==n) {
			if(e.v>bestv) {
				bestv=e.v;
				for(int i=1; i<=n; i++) {
					bestx[i]=e.x[i];
				}
			}
		} else {
			e1.t=e.t+1;   
			for(int i=1; i<=n; i++)
				e1.x[i]=e.x[i];
			e1.w=e.w+w[e1.t];
			e1.v=e.v+v[e1.t];
			e1.x[e1.t]=1;
			if(e1.w<=30)
				qu.push(e1);
			e1.w=e.w;
			e1.v=e.v;
			e1.x[e1.t]=0;
			qu.push(e1);
		}
	}
}

int main() {
	bfs();
	for(int i=1; i<=3; i++) {
		if(bestx[i]==1)printf("选择%d号背包\n",i);
	}
	printf("总价值为：%d\n",bestv); 
}

4.2.2单源最短路径

采用队列式分支限界法求解

定义顶点结构：

struct NodeType //队列结点类型
{  int vno; //顶点编号
   int length; //当前路径长度
};

模拟这个过程：

代码如下：
 

void bfs(int v) { //求解算法
	NodeType e,e1;
	queue<NodeType> qu;
	e.vno=v; //建立源点结点e（根结点）
	e.length=0;
	qu.push(e); //源点结点e进队
	dist[v]=0;
	while(!qu.empty()) { //队列不空循环
		e=qu.front();
		qu.pop();//出队列结点e
		for (int j=0; j<n; j++) {
			if(a[e.vno][j]<INF && e.length+a[e.vno][j]<dist[j]) {
				//剪枝：e.vno到顶点j有边并且路径长度更短
				dist[j]=e.length+a[e.vno][j];
				prev[j]=e.vno;
				e1.vno=j; //建立相邻顶点j的结点e1
				e1.length=dist[j];
				qu.push(e1); //结点e1进队
			}
		}
	}
}

4.2.3旅行商问题

问题描述：一个商品推销员要去若干个城市推销商品，该 推销员从一个城市出发，需要经过所有城市后，回到出发地。 应如何选择行进路线，以使总的行程最短。

用队列式分支限界法求解：

定义顶点结构：

struct Node {
	int t;    //顶点的深度
	int road[MAXN];   //当前路径
	int length;    //当前走过的总花费
};

 代码如下：

#include<stdio.h>
#include<queue>
#define INF 0x3f3f3f3f
#define MAXN 51
using namespace std;

int n=5;
/*int a[MAXN][MAXN]= {{INF,INF,INF,INF,INF},
	{INF,INF,30,6,4},{INF,30,INF,5,10},
	{INF,6,5,INF,20},{INF,4,10,20,INF}
};*/

int a[MAXN][MAXN]= {{INF,INF,INF,INF,INF,INF},{INF,INF,13,3,7,2},
	{INF,13,INF,6,1,9},{INF,3,6,INF,8,16},
	{INF,7,1,8,INF,19},{INF,2,9,16,19,INF}
};
int bestx[MAXN];
int minlength=INF;
void dfs();
void output();

struct Node {
	int t;    //顶点的深度
	int road[MAXN];   //当前路径
	int length;    //当前走过的总花费
};

int main() {
	dfs();
	output();
}

void dfs() {
	Node e;
	Node e1;
	int t;
	queue<Node> qu;
	for(int i=1; i<=n; i++)
		e1.road[i]=i;
	e1.t=2;
	e1.length=0;
	qu.push(e1);
	while(!qu.empty()) {
		e=qu.front();
		qu.pop();
		t=e.t;
		if(t==n) {
			if(a[e.road[t-1]][e.road[t]] != INF && a[e.road[t]][1] != INF) {
				if(e.length+a[e.road[t-1]][e.road[t]]+a[e.road[t]][1] < minlength) {
					minlength=e.length+a[e.road[t-1]][e.road[t]]+a[e.road[t]][1];
					for(int i=1; i<=n; i++)
						bestx[i]=e.road[i];
				}
			}
			continue;
		} else {
			if(e.length>=minlength)continue;
			for(int j=t; j<=n; j++) {
				if(a[e.road[t-1]][e.road[j]] != INF && 	e.length+a[e.road[t-1]][e.road[j]]<minlength) {
					e1.length=e.length+a[e.road[t-1]][e.road[j]];
					e1.t=t+1;
					for(int k=1; k<=n; k++)
						e1.road[k]=e.road[k];
					swap(e1.road[t],e1.road[j]);
					qu.push(e1);
				}
			}
		}

	}
}

void output() {
	for(int i=1; i<=n; i++) {
		printf("%d->",bestx[i]);
	}
	printf("%d\n",bestx[1]);
	printf("最短路径长度为：%d",minlength);
}

这个代码当时我在写的时候，一直不理解为什么要swap，后来明白了是通过swap来交换次序得到不同的路线，最终得到最优解。

4.3总结

学好分支限界法，主要有以下方面：
1.确定限界函数

2.组织待处理活结点表

3.确定最优解中的各个分量