第七章 分支限界算法

分支限界法类似于回溯法，是一种在问题的解空间树上搜索问题解的算法。

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

分支限界法常以广度优先的方式搜索问题的解空间树。

队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先

0-1背包问题 n=3，c=30，w={16,15,15},v={45,25,25} 队列式分支限界法：

[A] B, C => B, C [B, C] D, E => E [C, E] F, G => F, G [E, F, G] J, K => K(45) [1,0,0] [F, G] L, M =>L(50) [0, 1, 1] M(25) [G] N, O =>N(25), O(0) 不搜索以不可行结点为根的子树 优先队列式分支限界法:（当前背包内物品价值+剩余物品价值,价值上限）

[A] B, C => B(45，45+50), C(0，0+50) [B, C] D, E => E(45，45+25) //约束函数进行剪枝 [E, C] J, K => K(45，45+0) [C，K] F, G => F(25,25 +25), G(0,0+25) [F, K, G] L, M => L(50,50+0), M(25,25+0) [L,K, G,M] L 出队，搜索结束

提高分支界限算法效率 实现分支限界算法时，首先确定目标值的上/下界(求最大值时，定义上界函数；求最小值时，定义下界函数)，边搜索边剪掉搜索树的某些分支，提高搜索效率。

利用约束函数和限界函数剪去无效的分支，提高搜索效率。

界限函数 利用约束函数和限界函数剪去无效的分支，提高搜索效率。

求解最大值问题时： 维护一个活节点表，从活结点表中选择一个结对作为扩展节点 对扩展节点的每个分支，计算器上界值Bound(i). 如果当前最大目标函数值bestc>=Bound（i）,那么结点 i 就不会放入活结点表中，否则放入。从而完成剪枝操作。

求解最小值问题时： 维护一个活节点表，从活结点表中选择一个结对作为扩展节点 对扩展节点的每个分支，计算器下界值Bound(i). 如果当前最大目标函数值bestc<=Bound（i）,那么结点 i 就不会放入活结点表中，否则放入。从而完成剪枝操作。

细胞问题 分析：

解空间是一棵四叉树(上下左右四个方向)

struct sit{ int x; int y; }; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int b=[100][100],num=0,n,m; void doit(int p,int q){//p,q矩阵的行列号; int i; queue<sit> qc;//实例化 num++; struct sit s,f; s.x=p;s.y=q; qc.push(s);//入列 while(!qc.empty()){ f=qc.front(); qc.pop(); for(i=0;i<=3;i++){ s.x=f.x+dx[i]; s.y=f.y+dy[i]; } if ((s.x>=0)&&(s.x<m)&&(s.y>=0)&&(s.y<n)&&(bz[s.x][s.y])){ qc.push(s); bz[s.x][s.y]=0; } }

单源最短路径问题

算法从优先队列中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 2出队 6 5 入队 3不入队 3出队 7入队 6不入队 4出队 7不入队 数据结构：

#include <iostream> #include <string> #include <queue> using namespace std; class Graphic{ int n;//图中顶点的个数 int e;//边的数目 int **adjmatrix;//邻接矩阵，存储图 int *dist;//dist[n],存储单元点到其他n-1个顶点的最短路的长度 int *prev;//prev[i]=j 存储顶点i 的前驱结点为j , 利用这些前驱结点可以找到源点到顶点i的最短路 int start;//源点 public: Graphic(int n, int e); void ShortPath(); void display(); }; class PathNode{ //放入优先队列中的节点,解空间中的结点 int i; //解空间中结点的编号。一个结点对应于一条路 int length;//路的长度。 friend class Graphic; public: PathNode(int a=0, int b=0):i(a),length(b){} bool operator <(PathNode b) const {//定义优先关系函数 return length>b.length; } }; Graphic::Graphic(int n, int e){ this->n=n; this->e=e; adjmatrix=new int*[n+1]; dist=new int[n+1]; prev=new int[n+1]; for(int i=1;i<=n;i++) adjmatrix[i]=new int[n+1]; cout<<"输入源点编号："; cin>>start; cout<<"请输入e条边"<<endl; for(i=1;i<=n;i++){ //邻接矩阵初始化 for(int j=1;j<=n;j++) adjmatrix[i][j]=-1; //两个顶点之间没有边 adjmatrix[i][i]=0; } for( i=0;i<e;i++) { int a, b,length; cin>>a>>b>>length; //输入一条边所依附的两个顶点和这条边的长度 adjmatrix[a][b]=length; //有向图 dist[i]=99999; //最短路赋初值 prev[i]=start; } };

分支界限算法实现

在这里插入代码片void Graphic::ShortPath() { priority_queue<PathNode> q; PathNode first,next; first.i=start; //计算顶点v到其它顶点的最短路 first.length=0; prev[start]=0; dist[start]=0; q.push(first); while(true) { if(q.empty()) break; first=q.top(); q.pop(); for(int i=1;i<=n;i++){// 搜索孩子结点，并将可行的结点插入优先队列 if(adjmatrix[first.i][i]>0 && (first.length+adjmatrix[first.i][i])<dist[i]){ dist[i]=first.length+adjmatrix[first.i][i]; prev[i]=first.i; next.i=i; next.length=dist[i]; q.push(next); } } } }

旅行商问题分析 优先队列分支界限算法 解空间是一棵排列树、 cc:从出发点截止到当前城市，路径长度 rcost:从当前城市出发，回到起点路径长度可能的最小值 扩展结点i的界限函数为：B（i）=cc(i)+rcost(i) (1)优先队列式分支界限算法数据结构

#define inf 1000000 //∞ #define NUM 100 int n; //图G的顶点数 int a[NUM][NUM]; //图G的邻接矩阵 int NoEdge = inf; //图G的无边标志 int cc; //当前费用（子路的长度） int bestc; //当前的最小费用（完整路的长度）

优先队列元素的数据结构

struct node{ 　　//优先队列以lcost为优先级参数 　　friend bool operator < (const node& a,const node& b){ 　　　　if(a.lcost > b.lcost) return true; 　　　　else return false; 　　} 　　int lcost;　//子树费用的下界 　　int rcost;　//从x[s]～x[n-1]顶点的最小出边和 　　int cc;　　 //当前费用。截止到当前城市的路径长度 　　int s;　　　//当前结点的编号。结点的层次编号。已经经过的城市的数目 　　int *x;　 //需进一步搜索的路径x[s+1:n]。全排列 };

优先队列式分支界限算法

priority_queue <node> H; int minOut[NUM];　　　 //各个顶点的最小出边费用 int minSum = 0;　　　　 //最小出边费用之和 //计算各个顶点的最小出边费用 int i, j; for(i=1; i<=n; i++) { 　　int Min = NoEdge; 　　for(j=1; j<=n; j++) 　　　　if( a[i][j]!=NoEdge && (a[i][j]<Min || Min==NoEdge)) 　　　　　　Min = a[i][j]; 　　if (Min==NoEdge) return NoEdge; //无回路 　　minOut[i] = Min; 　　minSum += Min; } //初始化 node E; for(i=1; i<=n; i++) 　　E.x[i] = i; E.s = 1; E.cc = 0; E.rcost = minSum; int bestc = NoEdge; //搜索排列树 while (E.s<n) {　　　　//非叶结点 　if (E.s==n-1) {　//当前扩展结点是叶结点的父结点 　　　//再加2条边构成回路　　//所构成的回路是否优于当前最优解 　　if (a[E.x[n-1]][E.x[n]]!=NoEdge && a[E.x[n]][1]!=NoEdge 　　　&& (E.cc+a[E.x[n-1]][E.x[n]]+a[E.x[n]][1]<bestc 　　　|| bestc==NoEdge))　　{ 　　　//费用更小的回路　 　　　bestc = E.cc+a[E.x[n-1]][E.x[n]]+a[E.x[n]][1]; 　　　E.cc = bestc; 　　　E.lcost = bestc; 　　　E.s++; 　　　H.push(E); 　　} 　　else delete[ ] E.x; //舍弃扩展结点 　} else{　　　　　　//搜索树的内部结点 　　for (i=E.s+1; i<=n; i++) //产生当前扩展结点的儿子结点 　　if (a[E.x[E.s]][E.x[i]]!=NoEdge)　　{　　　//可行儿子结点 　　　int cc = E.cc+a[E.x[E.s]][E.x[i]]; 　　　int rcost = E.rcost-minOut[E.x[E.s]]; 　　　//限界函数B(i) 　　　int B = cc+rcost; 　　　//子树可能包含最优解 　　　if(B<bestc || bestc==NoEdge) 　　　{ 　　　　//结点E插入优先队列 node N: for(j=1;j<=n;j++) N.x[j]=E.x[j]; N.x[E.s+1]=E.x[i]; N.x[i]=E.x[E.s+1]; N.cc=cc; N.s=E.s+1; N.lcost=B; N.rcost=rcost; H.push(N); 　　　} 　　} 　　//完成结点扩展 　　delete [] E.x; } //队列为空时，搜索结束 　if(H.empty()) break; 　else 　{ 　　E=H.top(); //取下一个扩展结点 　　H.pop(); 　} } if (bestc==NoEdge) return NoEdge; //表示无回路 //输出最优解 for(i=1; i<=n; i++) 　printf("%d ", E.x[i]); printf("\n"); //清空剩余的队列元素 while (!H.empty()) H.pop(); return bestc; //返回最优解 }