分支界限算法
所属分类：
计算机术语
计算机算法
与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。
一、基本设计思路（树型搜索法）
动态地构造一棵搜索树，树的结点对应着可能解的一个子集；估算子集中可能解约束函数值的界限值，用这个界限值来限定搜索的方向，控制搜索的进程。
为使大家对分枝界限法有一个感性认识，大家可以联想现实生活中这样一个例子：假如某小孩将心爱的风筝不慎挂在了一棵枝叶茂密的大树顶上，他欲爬上树顶取风筝。可想而知，他绝不是盲目地往上爬，而是经过肉眼和大脑的判断，从树根开始朝着最有可能取到风筝的树枝上爬……至于小孩是否最终真正取到了风筝，是否中途从树上摔下来，这不是我们今天要关心的问题。我们目前要关心的问题是，为让计算机利用分枝界限法搜索最优化问题的最佳解，事先应做哪些准备工作。
二、准备工作（以目标函数最小化问题为例）
1．确定子集合（结点）生成规则：规定如何划分可能解集合为若干子集合。
2．确定搜索过程：一般用树的结点表示各种可能解集合或子集合，并从树根开始动态地生成搜索树。
3．确定结点界值计算法：对搜索树每个结点都要用统一方法计算出可能解集合约束函数值的下界值作为控制搜索方向和是否进一步生成和搜索该结点子结点的判据。
4．确定限界或剪枝规则：一般规定，若某结点的下界值等于或超过了当前最佳解的值，则该结点的子结点不再生
成（在人工智能中叫剪枝）。
在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：
一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。
如有4件物品，容积分别为： 3 4 5 8
对应的价值分别为： 4 5 7 10
小偷背包的载重量为：12
则取编号为1 2 3的物品，得到最大价值为16。
下面为C源代码：
<![CDATA[/* 0/1背包问题的分支定界法算法*/ #include<stdio.h> #include<stdlib.h> #define MAXNUM 100 struct node { int step ; double price ; double weight ; double max,min ; unsigned long po ; } ; typedef struct node DataType ; struct SeqQueue { /* 顺序队列类型定义 */ int f,r ; DataType q[MAXNUM]; } ; typedef struct SeqQueue*PSeqQueue ; PSeqQueue createEmptyQueue_seq(void) { PSeqQueue paqu ; paqu=(PSeqQueue)malloc(sizeof(struct SeqQueue)); if(paqu==NULL) printf("Out of space!! \n"); else paqu->f=paqu->r=0 ; return paqu ; } int isEmptyQueue_seq(PSeqQueue paqu) { return paqu->f==paqu->r ; } /* 在队列中插入一元素x */ void enQueue_seq(PSeqQueue paqu,DataType x) { if((paqu->r+1)%MAXNUM==paqu->f) printf("Full queue.\n"); else { paqu->q[paqu->r]=x ; paqu->r=(paqu->r+1)%MAXNUM ; } } /* 删除队列头元素 */ void deQueue_seq(PSeqQueue paqu) { if(paqu->f==paqu->r) printf("Empty Queue.\n"); else paqu->f=(paqu->f+1)%MAXNUM ; } /* 对非空队列,求队列头部元素 */ DataType frontQueue_seq(PSeqQueue paqu) { return(paqu->q[paqu->f]); } /* 物品按性价比从新排序*/ void sort(int n,double p[],double w[]) { int i,j ; for(i=0;i<n-1;i++) for(j=i;j<n-1;j++) { double a=p[j]/w[j]; double b=p[j+1]/w[j+1]; if(a><b) { double temp=p[j]; p[j]=p[j+1]; p[j+1]=temp ; temp=w[j]; w[j]=w[j+1]; w[j+1]=temp ; } } } /* 求最大可能值*/ double up(int k,double m,int n,double p[],double w[]) { int i=k ; double s=0 ; while(i><n&&w[i]><m) { m-=w[i]; s+=p[i]; i++; } if(i><n&&m>0) { s+=p[i]*m/w[i]; i++; } return s ; } /* 求最小可能值*/ double down(int k,double m,int n,double p[],double w[]) { int i=k ; double s=0 ; while(i<n&&w[i]><=m) { m-=w[i]; s+=p[i]; i++; } return s ; } /* 用队列实现分支定界算法*/ double solve(double m,int n,double p[],double w[],unsigned long*po) { double min ; PSeqQueue q=createEmptyQueue_seq(); DataType x= { 0,0,0,0,0,0 } ; sort(n,p,w); x.max=up(0,m,n,p,w); x.min=min=down(0,m,n,p,w); if(min==0)return-1 ; enQueue_seq(q,x); while(!isEmptyQueue_seq(q)) { int step ; DataType y ; x=frontQueue_seq(q); deQueue_seq(q); if(x.max<min)continue ; step=x.step+1 ; if(step==n+1)continue ; y.max=x.price+up(step,m-x.weight,n,p,w); if(y.max>=min) { y.min=x.price+down(step,m-x.weight,n,p,w); y.price=x.price ; y.weight=x.weight ; y.step=step ; y.po=x.po<<1 ; if(y.min>=min) { min=y.min ; if(step==n)*po=y.po ; } enQueue_seq(q,y); } if(x.weight+w[step-1]<=m) { y.max=x.price+p[step-1]+ up(step,m-x.weight-w[step-1],n,p,w); if(y.max>=min) { y.min=x.price+p[step-1]+ down(step,m-x.weight-w[step-1],n,p,w); y.price=x.price+p[step-1]; y.weight=x.weight+w[step-1]; y.step=step ; y.po=(x.po<<1)+1 ; if(y.min>=min) { min=y.min ; if(step==n)*po=y.po ; } enQueue_seq(q,y); } } } return min ; } #define n 4 double m=15 ; double p[n]= { 10,10,12,18 } ; double w[n]= { 2,4,6,9 } ; int main() { int i ; double d ; unsigned long po ; d=solve(m,n,p,w,&po); if(d==-1) printf("No solution!\n"); else { for(i=0;i<n;i++) printf("x%d is %d\n",i+1,((po&(1><<(n-i-1)))!=0)); printf("The max weight is %f\n",d); } getchar(); return 0 ; } ]]>
)
