分支限界法-課件

第6章分枝-限界法1ppt課件學習要點理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）隊列式(FIFO)分支限界法（2）優(yōu)先隊列式分支限界法通過應(yīng)用范例學習分支限界法的設(shè)計策略。（1）單源最短路徑問題（2）裝載問題；（3）布線問題（4）0-1背包問題；（5）最大團問題；（6）旅行售貨員問題（7）電路板排列問題（8）批處理作業(yè)調(diào)度問題2ppt課件6.1 分支限界法的基本思想分支限界法與回溯法（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。

3ppt課件6.1 分支限界法的基本思想分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。4ppt課件6.1 分支限界法的基本思想兩類常用的方法選擇下一個E-結(jié)點：（1）先進先出(FIFO)：從活結(jié)點表中取出結(jié)點的順序與加入結(jié)點的順序相同。后進先出(LIFO)：從活結(jié)點表中取出結(jié)點的順序與加入結(jié)點的順序相反。（2）優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。5ppt課件堆(Heap)優(yōu)先級隊列

每次出隊列的是優(yōu)先權(quán)最高的元素優(yōu)先級隊列支持以下操作：找出一個具有最高優(yōu)先級的元素刪除一個具有最高優(yōu)先級的元素添加一個元素到集合中6ppt課件完全二叉樹數(shù)組表示Ki

K2i+1&&

Ki

K2i+2完全二叉樹數(shù)組表示Ki

K2i+1&&

Ki

K2i+2堆的定義09098787787845456565313153232353171791765234578875331877853456593117237ppt課件自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆5353171778780923456587i0923456587i5317782345658795317789456587238ppt課件5353171778780923456587i0923456587i5317659457887235396517457887239ppt課件5353171778780923456587i0923456587i0953965174578872310ppt課件5353171778780923456587i0923456587i1791765234578875311ppt課件53171778780923456587i0923456587j11在堆中插入新元素1153j1123i最小堆的向上調(diào)整9176523457887531112ppt課件5317117878094565870917456587j115323i2317ji9116517457887532313ppt課件5311782331456587在堆中刪除根元素09531178233145658709531178093145658723231165314578875314ppt課件5323781131456587在堆中刪除根元素095323781131456587112365314578875315ppt課件例1：n=3時的0-1背包問題，w=[20,15,15]p=[40,25,25]c=30E-結(jié)點和活結(jié)點死結(jié)點FIFO隊列CBXX20403050152515250CECGFEGFG16ppt課件例1：n=3時的0-1背包問題，w=[20,15,15]p=[40,25,25]c=30E-結(jié)點和活結(jié)點死結(jié)點LIFO隊列BCXX20403050152515250BBFGBFBE17ppt課件例1：n=3時的0-1背包問題，w=[20,15,15]p=[40,25,25]c=30E-結(jié)點和活結(jié)點死結(jié)點優(yōu)先隊列20403050152515250XXCBCCECGFG18ppt課件例2：旅行商問題1423301020654旅行線路(1,2,4,3,1)(1,3,2,4,1)(1,4,3,2,1)19ppt課件例2：旅行商問題:FIFO(1,2,3,4,1)v=59(1,2,4,3,1)v=66(1,3,2,4,1)v=25X(1,4,2,3,1)V=25(1,4,3,2,1)V=59142330102065420ppt課件例2：旅行商問題:優(yōu)先隊列1423301020654(1,3,2,4,1)V=25(1,4,2,3,1)V=25XXX21ppt課件6.2 單源最短路徑問題1.問題描述

下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。要求圖G的從源頂點s到目標頂點t之間的最短路徑。22ppt課件6.2 單源最短路徑問題2.算法思想

解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當前路長。

算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后，它的兒子結(jié)點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結(jié)點作為當前擴展結(jié)點，并依次檢查與當前擴展結(jié)點相鄰的所有頂點。如果從當前擴展結(jié)點i到頂點j有邊可達，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。23ppt課件

下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當前路長。24ppt課件6.2 單源最短路徑問題2.算法設(shè)計

staticfloat[][]a//圖G的鄰接矩陣

staticfloat[]dist//源到各頂點的距離

staticint[]p//源到各頂點的路徑上的前驅(qū)頂點

HeapNode//最小堆元素

{inti;//頂點編號floatlength;//當前路長

……}25ppt課件while(true){//搜索問題的解空間for(intj=1;j<=n;j++)if((a[enode.i][j]<Float.MAX_VALUE)&&(enode.length+a[enode.i][j]<dist[j])){

//頂點i到頂點j可達，且滿足控制約束

dist[j]=enode.length+c[enode.i][j];p[j]=enode.i;

//加入活結(jié)點優(yōu)先隊列

HeapNodenode=newHeapNode(j,dist[j]);heap.put(node);}

//取下一擴展結(jié)點

if(heap.isEmpty())break;

elseenode=(HeapNode)heap.removeMin();

}}頂點i和j間有邊，且此路徑長小于原先從原點到j(luò)的路徑長26ppt課件實例：優(yōu)先隊列：11110987654321234567891011dist0

1234567891011102342037230924025050506013705180509050100211027ppt課件2341234567891011dist0234p111優(yōu)先隊列:1結(jié)點1到其它結(jié)點：236710977563410779991091128ppt課件34651234567891011dist023494p11122優(yōu)先隊列:1經(jīng)過結(jié)點2到其它結(jié)點：2367109775634107799910911X29ppt課件46751234567891011dist0234945p111223優(yōu)先隊列:1經(jīng)過結(jié)點3到其它結(jié)點：2367109775634107799910911XX30ppt課件6751234567891011dist0234945p111223優(yōu)先隊列:1經(jīng)過結(jié)點4到其它結(jié)點：2367109775634107799910911XXX31ppt課件7951234567891011dist02349457p1112236優(yōu)先隊列:1經(jīng)過結(jié)點6到其它結(jié)點：2367109775634107799910911XXXX32ppt課件10951234567891011dist023494576p11122367優(yōu)先隊列:1經(jīng)過結(jié)點7到其它結(jié)點：2367109775634107799910911XXXX33ppt課件951234567891011dist0234945768p1112236710優(yōu)先隊列:1經(jīng)過結(jié)點10到其它結(jié)點：2367109775634107799910911XXXXX34ppt課件6.2 單源最短路徑問題復雜度分析計算時間為O(n!)。需要空間為O(n2)。35ppt課件6.3裝載問題1.問題描述有一批共n個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。36ppt課件6.3裝載問題2.算法描述目標：尋找第一條船的最大裝載方案。解空間：子集樹。數(shù)據(jù)結(jié)構(gòu)：queue:存放活結(jié)點隊列，隊列中的元素值表示活結(jié)點對應(yīng)的當前載重量。元素值為-1，表示隊列已到達解空間樹同一層結(jié)點的尾部。bestw:當前最優(yōu)載重量。i:表示擴展結(jié)點所處的層cw:擴展結(jié)點所對應(yīng)的載重量37ppt課件6.3裝載問題2.隊列式分支限界法maxLoading算法的while循環(huán)中，首先檢測當前擴展結(jié)點的左兒子結(jié)點是否為可行結(jié)點。如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列中(右兒子結(jié)點一定是可行結(jié)點)。2個兒子結(jié)點都產(chǎn)生后，當前擴展結(jié)點被舍棄?；罱Y(jié)點隊列中的隊首元素被取出作為當前擴展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標記-1，故在取隊首元素時，活結(jié)點隊列一定不空。當取出的元素是-1時，再判斷當前隊列是否為空。如果隊列非空，則將尾部標記-1加入活結(jié)點隊列，算法開始處理下一層的活結(jié)點。maxLoading算法的時間和空間復雜性均為：O(2n)38ppt課件2.隊列式分支限界法while(true){//搜索子集樹

//檢查左兒子結(jié)點

if(cw+w[i]<=c)//x[i]=1enQueue(cw+w[i],i);

//右兒子結(jié)點總是可行的

enQueue(cw,i);//x[i]=0cw=((Integer)queue.remove()).intValue();//取下一擴展結(jié)點

if(cw==-1){//同層結(jié)點尾部

if(queue.isEmpty())returnbestw;queue.put(newInteger(-1));//同層結(jié)點尾部標志

queue.remove()).intValue();//取下一擴展結(jié)點

i++;//進入下一層

}}39ppt課件privatestaticvoidenQueue(intwt,inti){//將活結(jié)點加入到活結(jié)點隊列中if(i==n){//可行葉結(jié)點if(wt>bestw){bestw=wt;}else//非葉結(jié)點

queue.put(newInteger(wt));}40ppt課件cw+w[4]>c1xABJHEC10cw=0cw=8cw=8cw=10cw=8bestw=10bestw=11cw+w[2]>c1xcw+w[3]<c1NOcw+w[4]<c1cw=8Pcw=0GFcw=8cw=0Icw+w[3]<c1Lcw+w[3]<c1MQcw+w[4]<c1cw=6Rcw=11Kcw=8voidbacktrack(inti){//搜索第i層結(jié)點

if(i>n){//到達葉結(jié)點

if(cw>bestw)bestw=cw;return;}

if(cw+w[i]<=c){//搜索左子樹

cw+=w[i];

backtrack(i+1);cw-=w[i];}//搜索右子樹

backtrack(i+1);}例：假定n=4，w=[8,6,2,3]，c1=1241ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw-1i1bestw:0,i=1,cw=0A42ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw08-1i1bestw:0,i=1,cw=0ABC10cw=0cw=8cw=043ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw-108i2bestw:0,i=2,cw=-1ABC10cw=0cw=8cw=044ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw8-10i2bestw:0,i=2,cw=8ABEC10cw=0cw=8cw=8cw+w[2]>c1xcw=045ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw068-1i2bestw:0,i=2,cw=0ABEC10cw=0cw=8cw=8cw+w[2]>c1xcw=0GFcw=0cw=646ppt課件2.隊列式分支限界法例：假定n=4，w=[8,6,2,3]，c1=12cw-10268810-1068-108-1i4321bestw:11ABJHEC10cw=0cw=8cw=8cw=10cw=8bestw=10bestw=11cw+w[2]>c1xcw+w[3]<c1NOcw+w[4]<c1cw=8Pcw=0GFcw=8cw=0Icw+w[3]<c1Lcw+w[3]<c1MQcw+w[4]<c1cw=6Rcw=11Kcw=8cw+w[4]>c1x47ppt課件裝載問題復雜度分析計算時間為O(2n)。需要空間為O(2n)。48ppt課件6.3裝載問題3.算法的改進節(jié)點的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè):

bestw是當前最優(yōu)解；

cw是當前擴展結(jié)點所相應(yīng)的重量；

r是剩余集裝箱的重量。則當cw+rbestw時，可將其右子樹剪去，因為此時若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。另外，為了確保右子樹成功剪枝，應(yīng)該在算法每一次進入左子樹的時候更新bestw的值。49ppt課件3.算法的改進//檢查左兒子結(jié)點

intwt=cw+w[i];//wt:左兒子結(jié)點的重量

if(wt<=c){//可行結(jié)點

if(wt>bestw)bestw=wt;

//加入活結(jié)點隊列

if(i<n)queue.put(newInteger(wt));}提前更新bestw//檢查左兒子結(jié)點if(cw+w[i]<=c)//x[i]=1enQueue(cw+w[i],i);//右兒子結(jié)點總是可行的

enQueue(cw,i);//x[i]=050ppt課件3.算法的改進//檢查右兒子結(jié)點,可能含最優(yōu)解if(cw+r>bestw&&i<n)queue.put(newInteger(wt));//取下一擴展結(jié)點

cw=queue.remove().intValue();右兒子剪枝

//檢查左兒子結(jié)點if(cw+w[i]<=c)//x[i]=1enQueue(cw+w[i],i);//右兒子結(jié)點總是可行的

enQueue(cw,i);//x[i]=051ppt課件例：假定n=4，w=[8,6,2,3]，c1=12cw-168810-1068-108-1i4321r035555111111bestw111080ABJHEC10cw=0cw=8cw=8cw=10cw=8bestw=10bestw=11cw+w[2]>c1xcw+w[3]<c1NOcw+w[4]<c1cw=8Pcw=0GFcw=8cw=0Icw+w[3]<c1Lcw+w[3]<c1MQcw+w[4]<c1cw=6Rcw=11Kcw=8XXX52ppt課件4.構(gòu)造最優(yōu)解為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲相應(yīng)子集樹中從活結(jié)點到根結(jié)點的路徑。為此目的，可在每個結(jié)點處設(shè)置指向其父結(jié)點的指針，并設(shè)置左、右兒子標志。staticintn;staticintbestw;//當前最優(yōu)載重量staticArrayQueuequeue;//活結(jié)點隊列staticQnodebestE;//當前最優(yōu)擴展結(jié)點staticint[]bestx;//當前最優(yōu)解53ppt課件classQNode{QNodeparent;

//父結(jié)點

booleanLeftChild;

//左兒子標志

intweight;

//結(jié)點所相應(yīng)的載重量staticvoidenQueue(intwt,intI,Qnodeparent,booleanleftchild){if(i==n){//可行葉結(jié)點if(wt==bestw){//當前最優(yōu)載重量bestE=parent;bestx[n]=(leftchild)?1:0;}return;Qnodeb=newQnode(parent,leftchild,wt);//非葉結(jié)點

queue.put(b);}54ppt課件修改后的搜索算法intwt=cw+w[i];//檢查左兒子結(jié)點，wt:左兒子結(jié)點的重量

if(wt<=c){//可行結(jié)點

if(wt>bestw)bestw=wt;enQueue(wt,i,e,ture);//加入活結(jié)點隊列//檢查右兒子結(jié)點,可能含最優(yōu)解if(cw+r>bestw)enQueue(cw,i,e,false);e=(QNode)queue.remove();……}55ppt課件4.構(gòu)造最優(yōu)解找到最優(yōu)值后，可以根據(jù)parent回溯到根節(jié)點，找到最優(yōu)解。//構(gòu)造當前最優(yōu)解for(intj=n-1;j>0;j--){bestx[j]=(bestE.LeftChild)?1:0;bestE=bestE.parent;}56ppt課件6.3裝載問題5.優(yōu)先隊列式分支限界法

解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結(jié)點表?；罱Y(jié)點x在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點。以結(jié)點x為根的子樹中所有結(jié)點相應(yīng)的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同。在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當前擴展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。此時可終止算法。57ppt課件解空間樹：子集樹數(shù)據(jù)結(jié)構(gòu)：

staticclassBbnode{//子集樹中的結(jié)點Bbnodeparent;booleanleftChild;

…}staticclassHeapNodeimplementsComparable{BbnodeliveNode;intuweight;//活結(jié)點優(yōu)先級（上界）intlevel;//活結(jié)點在子集樹中所處的層序號

…}5.優(yōu)先隊列式分支限界法58ppt課件while(i!=n+1){//非葉結(jié)點，檢查當前擴展結(jié)點的兒子結(jié)點

if(ew+w[i]<=c)//左兒子結(jié)點為可行結(jié)點addLiveNode(ew+w[i]+r[i],i+1,e,true);

//右兒子結(jié)點總為可行結(jié)點addLiveNode(ew+r[i],i+1,e,false);

//取下一擴展結(jié)點

HeapNodenode=(HeapNode)heap.removeMax();i=node.level;e=node.liveNode;ew=node.uweight-r[i-1];}//構(gòu)造當前最優(yōu)解For(intj=n;j>0;j--){bestx[j]=(e.leftChild)?1:0;e=e.parent;}returnew;

59ppt課件裝載問題復雜度分析計算時間為O(2n)。需要空間為O(2n)。60ppt課件6.4布線問題ab61ppt課件6.4布線問題1.算法思想

解此問題的隊列式分支限界法從起始位置a開始將它作為第一個擴展結(jié)點。與該擴展結(jié)點相鄰并且可達的方格成為可行結(jié)點被加入到活結(jié)點隊列中，并且將這些方格標記為1，即從起始方格a到這些方格的距離為1。

接著，算法從活結(jié)點隊列中取出隊首結(jié)點作為下一個擴展結(jié)點，并將與當前擴展結(jié)點相鄰且未標記過的方格標記為2，并存入活結(jié)點隊列。這個過程一直繼續(xù)到算法搜索到目標方格b或活結(jié)點隊列為空時為止。即加入剪枝的廣度優(yōu)先搜索。62ppt課件6.4布線問題解空間：圖staticclassPosition{privateintrow;//方格所在的行privateintcol;//方格所在的列staticint[][]grid;//方格陣列,存儲距離值staticintsize;//方格陣列大小staticintpathLen;//最短線路長度staticArrayQueueq;//擴展結(jié)點隊列staticPositionstatrt,finish;//起點，終點staticPosition[]path;//最短路徑63ppt課件6.4布線問題Position[]offset=newPosition[4];offset[0]=newPosition(0,1);//右

offset[1]=newPosition(1,0);//下

offset[2]=newPosition(0,-1);//左

offset[3]=newPosition(-1,0);//上定義移動方向的相對位移

for(inti=0;i<=size+1;i++){grid[0][i]=grid[size+1][i]=1;//頂部和底部grid[i][0]=grid[i][size+1]=1;//左翼和右翼}設(shè)置邊界的圍墻64ppt課件例子：ab111111111100000011000001102000110000011000001100001100001111111111R3C265ppt課件for(inti=0;i<4;i++){//四周方格數(shù)nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//該方格未標記

grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布線

q.put(newPosition(nbr.row,nbr.col));}}66ppt課件例子：ab111111111100011031132311030b110000110000110001111111111R2343C2123g333367ppt課件例子：ab1111111111000110311323411034b110000110000110001111111111R43234C34212g4433368ppt課件例子：ab1111111111000110311323411434b11400110000110001111111111R454323C123421g44443369ppt課件例子：ab1111111111540114311323411434b114561011789101189101111111111R2445432C1112342g444444370ppt課件例子：ab1111111111321121111a111212b11234811567811678111111111171ppt課件找到目標位置后，可以通過回溯方法找到這條最短路徑。pathLen=grid[finish.row][finish.col]-2;path=newPosition[pathLen];here=finish;//從目標位置向起始位置回溯for(intj=pathLen-1;i>=0;j--){path[j]=here;for(inti=0;i<4;i++){//找前驅(qū)位置nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==j+2)break;}here=newPosition(nbr.row,nbr.col);//向前移動}

72ppt課件pathLen=9，j=8b:(4,6),右:(4,7)下:(5,6),10=8+2左:(4,5)上:(3,6)：：：(5,3)右:(5,4)下:(6,3)左:(5,2),4=2+2上:(4,3)1111111111540114311323411434b11456101178910118910111111111173ppt課件6.4布線問題復雜度分析計算時間為O(mn)+O(L)需要空間為O(mn)。74ppt課件6.50-1背包問題算法的思想首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。75ppt課件6.50-1背包問題上界函數(shù)while(i<=n&&w[i]<=cleft)//n表示物品總數(shù)，cleft為剩余空間{cleft-=w[i];//w[i]表示i所占空間b+=p[i];//p[i]表示i的價值i++;}if(i<=n)b+=p[i]/w[i]*cleft;//裝填剩余容量裝滿背包returnb;

//b為上界函數(shù)值76ppt課件6.50-1背包問題staticclassBbnode{BBnodeparent;//父結(jié)點

booleanleftChild;//左兒子結(jié)點標志…}staticclassHeapNodeimplementsComparable{BBnodeliveNode;//活結(jié)點

doubleupperProfit;//結(jié)點的價值上界

doubleprofit;//結(jié)點所相應(yīng)的價值

doubleweight;//結(jié)點所相應(yīng)的重量intlevel;//活結(jié)點在子集樹中所處的層序號77ppt課件

while(i!=n+1){//非葉結(jié)點

//檢查當前擴展結(jié)點的左兒子結(jié)點

doublewt=cw+w[i];if(wt<=c){//左兒子結(jié)點為可行結(jié)點

if(cp+p[i]>bestp)bestp=cp+p[i];

addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);

//檢查當前擴展結(jié)點的右兒子結(jié)點

if(up>=bestp)//右子樹可能含最優(yōu)解

addLiveNode(up,cp,cw,i+1,enode,false);

//取下一個擴展節(jié)點

HeapNodenode=(HeapNode)heap.removeMax();enode=node.liveNode;cw=node.weight;cp=fit;up=node.upperProfit;i=node.level;}分支限界搜索過程計算上界78ppt課件

//構(gòu)造當前最優(yōu)解for(intj=n;j>0;j--){bestx[j]=(e.leftChild)?1:0;e=e.parent;}returncp;

實例：背包的承重量W等于10。物品重量w價值p價值/重量14401027426352554312479ppt課件0,i=1cw=0,cp=0up=761,i=2cw=4,cp=40up=76T2,i=2cw=0,cp=0up=57F3,i=3cw=11X4,i=3cw=4,cp=40up=69F5,i=4cw=9,cp=65up=69T6,i=4cw=4,cp=40up=52X7,i=5cw=12X8,i=5cw=9,cp=65up=65

F

解(1,0,1,0)80ppt課件6.6最大團問題

給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。下圖G中，子集{1，2}是G的大小為2的完全子圖。這個完全子圖不是團，因為它被G的更大的完全子圖{1，2，5}包含。{1，2，5}是G的最大團。{1，4，5}和{2，3，5}也是G的最大團。1.問題描述81ppt課件6.6最大團問題2.上界函數(shù)cliqueSize：表示與該結(jié)點相應(yīng)的團的頂點數(shù)；level：表示結(jié)點在子集空間樹中所處的層次；cliqueSize+n-level+1:頂點數(shù)上界upperSize的值。在此優(yōu)先隊列式分支限界法中，upperSize實際上也是優(yōu)先隊列中元素的優(yōu)先級。算法總是從活結(jié)點優(yōu)先隊列中抽取具有最大upperSize值的元素作為下一個擴展元素。82ppt課件6.6最大團問題3.算法思想子集樹的根結(jié)點是初始擴展結(jié)點，對于這個特殊的擴展結(jié)點，其cliqueSize的值為0。算法在擴展內(nèi)部結(jié)點時，首先考察其左兒子結(jié)點。在左兒子結(jié)點處，將頂點i加入到當前團中，并檢查該頂點與當前團中其它頂點之間是否有邊相連。當頂點i與當前團中所有頂點之間都有邊相連，則相應(yīng)的左兒子結(jié)點是可行結(jié)點，將它加入到子集樹中并插入活結(jié)點優(yōu)先隊列，否則就不是可行結(jié)點。接著繼續(xù)考察當前擴展結(jié)點的右兒子結(jié)點。當upperSize>bestn時，右子樹中可能含有最優(yōu)解，此時將右兒子結(jié)點加入到子集樹中并插入到活結(jié)點優(yōu)先隊列中。83ppt課件算法設(shè)計解空間：子集樹可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。staticclassBBnode{BBnodeparent;//父結(jié)點

booleanleftChild;//左兒子結(jié)點……}84ppt課件staticclassHeapNodeimplementsComparable{BBnodeliveNode;intupperSize;//當前團最大頂點數(shù)上界intclipqueSize;//當前團的頂點數(shù)intlevel;//結(jié)點在子集樹中所處的層次

……}PublicclassBBClique{staticboolean[][]a;//圖G的鄰接矩陣staticMaxHeapheap;//活結(jié)點優(yōu)先隊列}85ppt課件6.6最大團問題3.算法思想

算法的while循環(huán)的終止條件是遇到子集樹中的一個葉結(jié)點(即n+1層結(jié)點)成為當前擴展結(jié)點。對于子集樹中的葉結(jié)點，有upperSize＝cliqueSize。此時活結(jié)點優(yōu)先隊列中剩余結(jié)點的upperSize值均不超過當前擴展結(jié)點的upperSize值，從而進一步搜索不可能得到更大的團，此時算法已找到一個最優(yōu)解。86ppt課件

while(i!=n+1){//非葉結(jié)點

//檢查頂點i與當前團中其他頂點之間是否有邊相連booleanok=true;BBnodebnode=enode;for(intj=i-1;j>0;bnode=bnode.parent,j--)if(bnode.leftChild&&!a[i][j]){ok=false;break;}

if(ok){//左兒子結(jié)點為可行結(jié)點if(cn+1>bestn)bestn=cn+1;addLiveNode(cn+n-i+1,cn+1,i+1,enode,true);}if(cn+n-i>=bestn)//右子樹可能含最優(yōu)解

addLiveNode(cn+n-i,cn,i+1,enode,false);

//取下一個擴展節(jié)點

HeapNodenode=(HeapNode)heap.removeMax();enode=node.liveNode;cn=node.cliqueSize;i=node.level;}可行性約束分支限界搜索過程87ppt課件12118716917X1=1X1=0

X2=1X2=0X3=1X4=1X4=0X3=1X3=0X2=1X2=01與3不相連3124534X4=1X4=02與4不相連5X5=1X5=06Bestn=3cn+n-i<bestnX3=1X3=0=BestnxX5=1X5=0cn+n-i<bestncn+n-i<bestn12X4=1X4=01314cn+n-i<bestnX3=1X3=0X5=1X5=0cn+n-i<bestnX4=1X4=02與4不相連3與4不相連cn+n-i<bestncn+n-i<bestn=Bestnx實例：backtrack88ppt課件0,i=1cn=0bestn=01,i=2size=1bestn=1up=5T2,i=2size=0bestn=1up=4F3,i=3size=2bestn=2up=5T4,i=3size=1bestn=2up=4F6,i=4size=1bestn=2up=3F8,i=4size=1bestn=2up=4T7,i=5size=2bestn=2up=3F13,i=6size=3bestn=3up=3T解(1,1,0,0,1)12453n=5i=1cn=0bestn=0X5,i=4size=2bestn=2up=4FXX9,i=4size=0bestn=2up=3F10,i=4size=2bestn=2up=4F11,i=4size=1bestn=2up=3F12,i=5size=2bestn=2up=3FXX89ppt課件6.7旅行售貨員問題1.問題描述

某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。路線是一個帶權(quán)圖。圖中各邊的費用（權(quán)）為正數(shù)。圖的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。周游路線的費用是這條路線上所有邊的費用之和。旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點到任一葉結(jié)點的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖G中找出費用最小的周游路線。90ppt課件publicclassBBTSP{privatestaticclassHeapNodeimplementsComparable{floatlcost,//子樹費用的下界rcost,//x[s:n-1]中頂點最小出邊費用和cc;//當前費用ints;//根結(jié)點到當前結(jié)點的路徑為x[0:s]int[]x;//需要進一步搜索的頂點是x[s+1:n-1]

……staticfloat[][]a;//圖G的鄰接矩陣}91ppt課件6.7旅行售貨員問題2.算法描述算法開始時創(chuàng)建一個最小堆，用于表示活結(jié)點優(yōu)先隊列。優(yōu)先級:每個結(jié)點的子樹費用的下界lcost值。預處理：計算出圖中每個頂點的最小費用出邊并用minOut記錄。如果所給的有向圖中某個頂點沒有出邊，則該圖不可能有回路，算法即告結(jié)束。如果每個頂點都有出邊，則根據(jù)計算出的minOut作算法初始化。92ppt課件1423301020654實例：1234minOut4554minSum=1893ppt課件2.算法描述

1、首先考慮s=n-2的情形，此時當前擴展結(jié)點是排列樹中某個葉結(jié)點的父結(jié)點。如果該葉結(jié)點相應(yīng)一條可行回路且費用小于當前最小費用，則將該葉結(jié)點插入到優(yōu)先隊列中，否則舍去該葉結(jié)點。

2、當s<n-2時，算法依次產(chǎn)生當前擴展結(jié)點的所有兒子結(jié)點。由于當前擴展結(jié)點所相應(yīng)的路徑是x[0:s]，其可行兒子結(jié)點是從剩余頂點x[s+1:n-1]中選取的頂點x[i]，且(x[s]，x[i])是所給有向圖G中的一條邊。對于當前擴展結(jié)點的每一個可行兒子結(jié)點，計算出其前綴(x[0:s]，x[i])的費用cc和相應(yīng)的下界lcost。當lcost<bestc時，將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。算法的while循環(huán)體完成對排列樹內(nèi)部結(jié)點的擴展。對于當前擴展結(jié)點，算法分2種情況進行處理：94ppt課件6.7旅行售貨員問題2.算法描述

算法中while循環(huán)的終止條件是排列樹的一個葉結(jié)點成為當前擴展結(jié)點。當s=n-1時，已找到的回路前綴是x[0:n-1]，它已包含圖G的所有n個頂點。因此，當s=n-1時，相應(yīng)的擴展結(jié)點表示一個葉結(jié)點。此時該葉結(jié)點所相應(yīng)的回路的費用等于cc和lcost的值。剩余的活結(jié)點的lcost值不小于已找到的回路的費用。它們都不可能導致費用更小的回路。因此已找到的葉結(jié)點所相應(yīng)的回路是一個最小費用旅行售貨員回路，算法可以結(jié)束。算法結(jié)束時返回找到的最小費用，相應(yīng)的最優(yōu)解由數(shù)組v給出。95ppt課件

//搜索排列空間樹

while(enode!=null&&enode.s<n-1){//非葉結(jié)點

x=enode.xif(enode.s==n-2){//當前擴展結(jié)點是葉結(jié)點的父結(jié)點，再加兩條邊構(gòu)成回路，所構(gòu)成的回路是否優(yōu)于當前最優(yōu)解if(a[x[n-2]][x[n-1]]<Integer.MAX_VALUE&&a[x[n-1]][1]<Integer.MAX_VALUE&&(enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1]<bestc){//找到費用更小的回路

bestc=enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1];

enode.cc=bestc;enode.lcost=bestc;enode.s++;heap.put(enode);}}可行性約束96ppt課件else{//產(chǎn)生當前擴展結(jié)點的兒子結(jié)點for(inti=enode.s+1;i<n;i++)if(a[x[enode.s]][x[i]]<Integer.MAX_VALUE){//可行兒子結(jié)點

intcc=enode.cc+a[x[enode.s]][x[i]];intrcost=enode.rcost-minOut[x[enode.s]];intb=cc+rcost;//下界if(b<bestc){//子樹可能含最優(yōu)解，結(jié)點插入最小堆

int[]xx=newint[n];for(intj=0;j<n;j++)xx[j]=x[j];

xx[enode.s+1]=x[i];xx[i]=x[enode.s+1];HeapNodenode=newHeapNodd(b,cc,rcost,enode.s+1,xx);heap.put(node);}}}enode=(HeapNode)heap.removeMin();//取下一擴展結(jié)點}分支限界搜索過程97ppt課件實例：s=0,x[0]=1,x[1:3]=(2,3,4),cc=01423301020654i01234minOut04554x[i]1234lcostminSum=18rcost=18bestc=Max98ppt課件根1,s=0[1,2,3,4];cc=0rcost=184,s=1[1,4,3,2];cc=4rcost=14,b=182,s=1[1,2,3,4];cc=30rcost=14,b=443,s=1[1,3,2,4];cc=6rcost=14,b=205,s=2[1,4,3,2];cc=24rcost=10,b=346,s=2[1,4,2,3];cc=14rcost=10,b=247,s=2[1,3,2,4];cc=11rcost=9,b=208,s=2[1,3,4,2];cc=26rcost=9,b=359,s=31,3,2,4;cc=25解lcost=bestc=2510,s=3X1,4,2,3;cc=25解lcost=bestc=2511,s=3X1,4,3,2;cc=59解lcost=bestc=5912,s=3X1,3,3,2;cc=66解lcost=bestc=66X142330102065499ppt課件6.8電路板排列問題問題描述

n塊電路板B={b1,b2,…,bn}m個網(wǎng)組集合L={N1,N2,…,Nm}Ni是B的子集，子集中的元素需要連接起來。目標：找到一種電路板的排列方式，使機箱中任意一對相鄰插槽間所連電線數(shù)目最小。例：n=8，m=5B={b1,b2,b3,b4,b5,b6,b7,b8}L={N1,N2,N3,N4,N5}N1={b4,b5,b6}N2={b2,b3}N3={b1,b3}N4={b3,b6}N5={b7,b8}12345678b1b2b3b4b5b6b7b8100ppt課件6.8電路板排列問題2.算法描述算法開始時，將排列樹的根結(jié)點置為當前擴展結(jié)點。在do-while循環(huán)體內(nèi)算法依次從活結(jié)點優(yōu)先隊列中取出具有最小cd值的結(jié)點作為當前擴展結(jié)點，并加以擴展。首先考慮s=n-1的情形，當前擴展結(jié)點是排列樹中的一個葉結(jié)點的父結(jié)點。x

表示相應(yīng)于該葉結(jié)點的電路板排列。計算出與x相應(yīng)的密度并在必要時更新當前最優(yōu)值和相應(yīng)的當前最優(yōu)解。當s<n-1時，算法依次產(chǎn)生當前擴展結(jié)點的所有兒子結(jié)點。對于當前擴展結(jié)點的每一個兒子結(jié)點node，計算出其相應(yīng)的密度node.cd。當node.cd<bestd時，將該兒子結(jié)點N插入到活結(jié)點優(yōu)先隊列中。101ppt課件2.算法描述

privatestaticclassHeapNodeimplementsComparable{ints,//x[1:s]是當前結(jié)點所相應(yīng)的部分排列

cd；//x[1:s]的密度int[]x;//當前解int[]now;//now[j]為當前解中所含連接塊j的電路板數(shù)……}int[]bestx;//當前最優(yōu)解int[]total;//total[j]為連接塊j的電路板數(shù)intbestd;//當前最優(yōu)密度int[][]board;//board[i][j]表示電路板i在連接塊j中102ppt課件

do{//結(jié)點擴展

if(enode.s==n-1){//僅一個兒子結(jié)點

intld=0;//最后一塊電路板的密度

for(intj=1;j<=m;j++)ld+=board[enode.x[n]][j];if(ld<bestd){//密度更小的電路板排列x=enode.x;bestd=Math.max(ld,enode.cd);}}else{//產(chǎn)生當前擴展結(jié)點的所有兒子結(jié)點

for(inti=enode.s+1;i<=n;i++){HeapNodenode=newHeapNode(0,newint[m+1],0,newint[n+1]);for(intj=1;j<=m;j++)//新插入的電路板

node.now[j]=enode.now[j]+board[enode.x[i]][j];

S=n-1的情況，計算出此時的密度和bestd進行比較。x[1:s]的密度,為當前解中所含連接塊j的電路板數(shù),當前結(jié)點所相應(yīng)的部分排列,當前解103ppt課件

intld=0;//新插入電路板的密度

for(intj=1;j<=m;j++)if(node.now[j]>0&&total[j]!=node.now[j])ld++;node.cd=max(ld,enode.cd);if(node.cd<bestd){//可能產(chǎn)生更好的葉結(jié)點

node.s=enode.s+1;for(intj=1;j<=n;j++)node.x[j]=enode.x[j];node.x[node.s]=enode.x[i];node.x[i]=enode.x[node.s];heap.put(node);}}}//取下一擴展結(jié)點

enode=(HeapNode).heap.removeMin()}while(enode!=null&&enode.cd<bestd);計算出每一個兒子結(jié)點的密度與bestd進行比較小于bestd時加入隊列104ppt課件6.8電路板排列問題實例：n=8，m=5B={b1,b2,b3,b4,b5,b6,b7,b8}L={N1,N2,N3,N4,N5}N1={b4,b5,b6}N2={b2,b3}N3={b1,b3}N4={b3,b6}N5={b7,b8}12345678b1b2b3b4b5b6b7b8i1234