基本介紹
- 中文名：分支界限算法
- 套用：為組合最佳化問題設計求解算法
- 優勢：效率更高
- 定義：整個可能解空間搜尋
基本思想,具體問題,
基本思想
一、基本設計思路（樹型搜尋法）
動態地構造一棵搜尋樹，樹的結點對應著可能解的一個子集；估運算元集中可能解約束函式值的界限值，用這個界限值來限定搜尋的方向，控制搜尋的進程。
為使大家對分枝界限法有一個感性認識，大家可以聯想現實生活中這樣一個例子：假如某小孩將心愛的風箏不慎掛在了一棵枝葉茂密的大樹頂上，他欲爬上樹頂取風箏。可想而知，他絕不是盲目地往上爬，而是經過肉眼和大腦的判斷，從樹根開始朝著最有可能取到風箏的樹枝上爬……至於小孩是否最終真正取到了風箏，是否中途從樹上摔下來，這不是我們今天要關心的問題。我們目前要關心的問題是，為讓計算機利用分枝界限法搜尋最最佳化問題的最佳解，事先應做哪些準備工作。
二、準備工作（以目標函式最小化問題為例）
1．確定子集合（結點）生成規則：規定如何劃分可能解集合為若干子集合。
2．確定搜尋過程：一般用樹的結點表示各種可能解集合或子集合，並從樹根開始動態地生成搜尋樹。
3．確定結點界值計算法：對搜尋樹每個結點都要用統一方法計算出可能解集契約束函式值的下界值作為控制搜尋方向和是否進一步生成和搜尋該結點子結點的判據。
4．確定限界或剪枝規則：一般規定，若某結點的下界值等於或超過了當前最佳解的值，則該結點的子結點不再生
成（在人工智慧中叫剪枝）。
具體問題
在歷屆NOIP競賽中，有4道初賽題和5道複賽題均涉及到背包問題，所謂的背包問題，可以描述如下：
一個小偷打劫一個保險箱，發現柜子里有N類不同大小與價值的物品，但小偷只有一個容積為M的背包來裝東西，背包問題就是要找出一個小偷選擇所偷物品的組合，以使偷走的物品總價值最大。
如有4件物品，容積分別為： 3 4 5 8
對應的價值分別為： 4 5 7 10
小偷背包的載重量為：12
則取編號為1 2 3的物品，得到最大價值為16。
下面為C原始碼：
/* 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><m) { m-=w; s+=p; i++; } if(i><n&&m>0) { s+=p*m/w; 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><=m) { m-=w; s+=p; 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 ; }
