008-アルゴリズム-分岐限界法

一、概念:貪欲法と同様に、この方法も組み合わせ最適化問題のために解アルゴリズムを設計するために使用され、異なるのは問題の可能な解空間全体を検索することであり、設計されたアルゴリズムは時間の複雑度が貪欲アルゴリズムより高いが、その利点は貧挙法と類似しており、問題の最適解を求めることを保証することができる.また,この方法は盲目的な窮挙探索ではなく,探索において限界を通過し,得られないいくつかの最適解に対するサブ空間を途中で停止することができる.さらに検索(人工知能の剪定に似ている)するので、窮屈な方法よりも効率的です.
二、基本構想:
分岐限界法は、問題の解空間ツリーを広さ優先または最小消費(最大利益)優先で探索することが多い.
分岐限界法では,各アクティブノードが拡張ノードになる機会は1回しかない.活結点が拡張結点になると,そのすべての息子結点が一度に生成される.これらの息子ノードでは,不可解または非最適解をもたらす息子ノードが捨てられ,残りの息子ノードが活ノードテーブルに組み込まれる.その後,生接点テーブルから1つの接点を外して現在の拡張接点とし,上記接点拡張過程を繰り返す.このプロセスは,所望の解や活結点テーブルが空である場合を見つけるまで続く.

（1）   (FIFO)     

         （FIFO）              。

（2）          

                                。

demo:

 
     
 
      
支界限算法 - 具体问题（背包问题） 
 
     
 
     

   NOIPコンテスト ， 4    の  . 5      .    リュックサックの  ，       ，      ：
  
一つこそ泥強盗を働く一つセーフティボックスロッカーの中にN種類の大きさと価値の異なるものがあるのを見つけたが、泥棒は容積Mのリュックサックが1つしか入っていない.リュックサックの問題は、泥棒が盗んだものの組み合わせを選んで、盗んだものの総価値を最大にすることだ.4つの物品がある場合、容積はそれぞれ:3 4 5 8に対応する価値はそれぞれ:4 5 7 10泥棒リュックサックの積載重量:12は番号1 2 3の物品を取り、最大価値は16を得る.  
  
* 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!! 
"); 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.
"); 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.
"); 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!
"); else { for(i=0;i<n;i++) printf("x%d is %d
",i+1,((po&(1><<(n-i-1)))!=0)); printf("The max weight is %f
",d); } getchar(); return 0 ; }