第6章分枝限界法6.1分枝限界法概述6.2求解0/1背包問(wèn)題6.3求解圖的單源最短路徑6.4求解任務(wù)分配問(wèn)題6.5求解流水作業(yè)調(diào)度問(wèn)題6.1.1什么是分枝限界法

分枝限界法類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解的算法。

但在一般情況下，分枝限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間樹(shù)中滿(mǎn)足約束條件的所有解，而分枝限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。6.1分枝限界法概述

所謂“分枝”就是采用廣度優(yōu)先的策略，依次搜索活結(jié)點(diǎn)的所有分枝，也就是所有相鄰結(jié)點(diǎn)。求最優(yōu)解時(shí)，選擇哪一個(gè)子結(jié)點(diǎn)？采用一個(gè)限界函數(shù)，計(jì)算限界函數(shù)值，選擇一個(gè)最有利的子結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分枝推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。sisi1si2sim…活結(jié)點(diǎn)產(chǎn)生所有的子結(jié)點(diǎn)分枝限界法與回溯法的主要區(qū)別方法解空間搜索方式存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)存儲(chǔ)特性常用應(yīng)用回溯法深度優(yōu)先?；罱Y(jié)點(diǎn)的所有可行子結(jié)點(diǎn)被遍歷后才從棧中出棧找出滿(mǎn)足條件的所有解分枝限界法廣度優(yōu)先隊(duì)列，優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿(mǎn)足條件一個(gè)解或者特定意義的最優(yōu)解6.1.2分枝限界法的設(shè)計(jì)思想1.設(shè)計(jì)合適的限界函數(shù)在搜索解空間樹(shù)時(shí)，每個(gè)活結(jié)點(diǎn)可能有很多孩子結(jié)點(diǎn)，其中有些孩子結(jié)點(diǎn)搜索下去是不可能產(chǎn)生問(wèn)題解或最優(yōu)解的?？梢栽O(shè)計(jì)好的限界函數(shù)在擴(kuò)展時(shí)刪除這些不必要的孩子結(jié)點(diǎn)，從而提高搜索效率。

假設(shè)活結(jié)點(diǎn)si有4個(gè)孩子結(jié)點(diǎn)，而滿(mǎn)足限界函數(shù)的孩子結(jié)點(diǎn)只有2個(gè)，可以刪除這2個(gè)不滿(mǎn)足限界函數(shù)的孩子結(jié)點(diǎn)，使得從si出發(fā)的搜索效率提高一倍。si活結(jié)點(diǎn)si1si2si3si4si活結(jié)點(diǎn)si2si3

限界函數(shù)設(shè)計(jì)難以找出通用的方法，需根據(jù)具體問(wèn)題來(lái)分析。一般地，先要確定問(wèn)題解的特性：目標(biāo)函數(shù)是求最大值：則設(shè)計(jì)上界限界函數(shù)ub（根結(jié)點(diǎn)的ub值通常大于或等于最優(yōu)解的ub值），若si是sj的雙親結(jié)點(diǎn)，應(yīng)滿(mǎn)足ub(si)≥ub(sj)，當(dāng)找到一個(gè)可行解ub(sk)后，將所有小于ub(sk)的結(jié)點(diǎn)剪枝。目標(biāo)函數(shù)是求最小值：則設(shè)計(jì)下界限界函數(shù)lb（根結(jié)點(diǎn)的lb值一定要小于或等于最優(yōu)解的lb值），若si是sj的雙親結(jié)點(diǎn)，應(yīng)滿(mǎn)足lb(si)≤lb(sj)，當(dāng)找到一個(gè)可行解lb(sk)后，將所有大于lb(sk)的結(jié)點(diǎn)剪枝。sisj2.組織活結(jié)點(diǎn)表根據(jù)選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的方式來(lái)組織活結(jié)點(diǎn)表，不同的活結(jié)點(diǎn)表對(duì)應(yīng)不同的分枝搜索方式。

隊(duì)列式分枝限界法優(yōu)先隊(duì)列式分枝限界法（1）隊(duì)列式分枝限界法

隊(duì)列式分枝限界法將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。步驟如下：將根結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列。從活結(jié)點(diǎn)隊(duì)中取出隊(duì)頭結(jié)點(diǎn)，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有孩子結(jié)點(diǎn)，用約束條件檢查，把所有滿(mǎn)足約束條件的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列。重復(fù)步驟②和③，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。（2）優(yōu)先隊(duì)列式分枝限界法

優(yōu)先隊(duì)列式分枝限界法的主要特點(diǎn)是將活結(jié)點(diǎn)表組組成一個(gè)優(yōu)先隊(duì)列，并選取優(yōu)先級(jí)最高的活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。步驟如下：計(jì)算起始結(jié)點(diǎn)（根結(jié)點(diǎn)）的優(yōu)先級(jí)并加入優(yōu)先隊(duì)列（與特定問(wèn)題相關(guān)的信息的函數(shù)值決定優(yōu)先級(jí)）。從優(yōu)先隊(duì)列中取出優(yōu)先級(jí)最高的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上可能有最優(yōu)解的分枝推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有孩子結(jié)點(diǎn)，然后用約束條件檢查，對(duì)所有滿(mǎn)足約束條件的孩子結(jié)點(diǎn)計(jì)算優(yōu)先級(jí)并加入優(yōu)先隊(duì)列。重復(fù)步驟②和③，直到找到一個(gè)解或優(yōu)先隊(duì)列為空為止。3.確定最優(yōu)解的解向量分枝限界法在搜索解空間樹(shù)時(shí)，結(jié)點(diǎn)的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層地向上回溯，因此當(dāng)搜索到某個(gè)葉子結(jié)點(diǎn)且該結(jié)點(diǎn)對(duì)應(yīng)一個(gè)可行解時(shí)，如何得到對(duì)應(yīng)的解向量呢？

①對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑。

每個(gè)結(jié)點(diǎn)帶有一個(gè)可能的解向量。這種做法比較浪費(fèi)空間，但實(shí)現(xiàn)起來(lái)簡(jiǎn)單，后面的示例均采用這種方式。②在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)帶有一個(gè)雙親結(jié)點(diǎn)指針，當(dāng)找到最優(yōu)解時(shí)，通過(guò)雙親指針找到對(duì)應(yīng)的最優(yōu)解向量。這種做法需保存搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親結(jié)點(diǎn)的指針。兩種方法：采用分枝限界法求解的3個(gè)關(guān)鍵問(wèn)題如下：（1）如何確定合適的限界函數(shù)。（2）如何組織待處理結(jié)點(diǎn)的活結(jié)點(diǎn)表。（3）如何確定解向量的各個(gè)分量。6.1.3分枝限界法的時(shí)間性能一般情況下，在問(wèn)題的解向量X=（x1，x2，…，xn）中，分量xi（1≤i≤n）的取值范圍為某個(gè)有限集合Si=（si1，si2，…，sir）。問(wèn)題的解空間由笛卡爾積S1×S2×…×Sn構(gòu)成：第1層根結(jié)點(diǎn)有|S1|棵子樹(shù)第2層有|S1|個(gè)結(jié)點(diǎn)，第2層的每個(gè)結(jié)點(diǎn)有|S2|棵子樹(shù)，第3層有|S1|×|S2|個(gè)結(jié)點(diǎn)…第n+1層有|S1|×|S2|×…×|Sn|個(gè)結(jié)點(diǎn)，它們都是葉子結(jié)點(diǎn)，代表問(wèn)題的所有可能解在最壞情況下，時(shí)間復(fù)雜性是指數(shù)階。6.2求解0/1背包問(wèn)題

【問(wèn)題描述】有n個(gè)重量分別為{w1，w2，…，wn}的物品，它們的價(jià)值分別為{v1，v2，…，vn}，給定一個(gè)容量為W的背包。

設(shè)計(jì)從這些物品中選取一部分物品放入該背包的方案，每個(gè)物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中，而且重量和為W具有最大的價(jià)值。假設(shè)一個(gè)0/1背包問(wèn)題是，n=3，重量為w=（16，15，15），價(jià)值為v=（45，25，25），背包限重為W=30，解向量為x=（x1，x2，x3）。編號(hào)123重量161515價(jià)值4525256.2.1采用隊(duì)列式分枝限界法求解首先不考慮限界問(wèn)題，用FIFO表示隊(duì)列（實(shí)際上對(duì)應(yīng)層次遍歷）。初始時(shí)，F(xiàn)IFO=[]。i=0A(0,0)編號(hào)123重量161515價(jià)值452525L(30,50)M(15,25)01N(15,25)O(0,0)01F(15,25)G(0,0)0110選擇或不選擇物品1B(16,45)C(0,0)i=1D(31,70)

E(16,45)01i=2選擇或不選擇物品2J(31,70)K(16,45)

01i=3選擇或不選擇物品3可行解得到最終解：（0,1,1）

采用STL的queue<NodeType>容器qu作為隊(duì)列，隊(duì)列中的結(jié)點(diǎn)類(lèi)型聲明如下：structNodeType

//隊(duì)列中的結(jié)點(diǎn)類(lèi)型{intno; //結(jié)點(diǎn)編號(hào)，從1開(kāi)始inti; //當(dāng)前結(jié)點(diǎn)在搜索空間中的層次intw; //當(dāng)前結(jié)點(diǎn)的總重量intv; //當(dāng)前結(jié)點(diǎn)的總價(jià)值intx[MAXN]; //當(dāng)前結(jié)點(diǎn)包含的解向量

doubleub; //上界};

現(xiàn)在設(shè)計(jì)限界函數(shù)，為了簡(jiǎn)便，設(shè)根結(jié)點(diǎn)為第0層，然后各層依次遞增，顯然i=n時(shí)表示是葉子結(jié)點(diǎn)層。

由于該問(wèn)題是求裝入背包的最大價(jià)值，屬求最大值問(wèn)題，采用上界設(shè)計(jì)方式。

對(duì)于第i層的某個(gè)結(jié)點(diǎn)e，用e.w表示結(jié)點(diǎn)e時(shí)已裝入的總重量，用e.v表示已裝入的總價(jià)值：如果所有剩余的物品都能裝入背包，那么價(jià)值的上界e.ub=e.v+(v[i+1]+…+v[n])如果所有剩余的物品不能全部裝入背包，那么價(jià)值的上界e.ub=e.v+(v[i+1]+…+v[k])+(物品k+1裝入的部分重量)×物品k+1的單位價(jià)值i=0A(0,0)10選擇或不選擇物品1B(16,45)C(0,0)i=1根結(jié)點(diǎn)A的層次i=0，w=0，v=0:ub=0+45+(30-16)×25/15=68（采用取整運(yùn)算）w=0w[1]=16<30可選物品1v[1]=45可選物品2的一部分,即30-16，對(duì)應(yīng)的價(jià)值編號(hào)123重量161515價(jià)值452525求結(jié)點(diǎn)e的上界e.ub的算法如下：voidbound(NodeType&e) //計(jì)算分枝結(jié)點(diǎn)e的上界{inti=e.i+1; //考慮結(jié)點(diǎn)e的余下物品intsumw=e.w; //求已裝入的總重量doublesumv=e.v; //求已裝入的總價(jià)值while((sumw+w[i]<=W)&&i<=n){sumw+=w[i]; //計(jì)算背包已裝入載重sumv+=v[i]; //計(jì)算背包已裝入價(jià)值i++;}if(i<=n) //余下物品只能部分裝入e.ub=sumv+(W-sumw)*v[i]/w[i];else //余下物品全部可以裝入e.ub=sumv;}//問(wèn)題表示intn=3,W=30;intw[]={0,16,15,15}; //重量，下標(biāo)0不用intv[]={0,45,25,25}; //價(jià)值，下標(biāo)0不用//求解結(jié)果表示intmaxv=-9999; //存放最大價(jià)值,初始為最小值intbestx[MAXN]; //存放最優(yōu)解,全局變量inttotal=1; //解空間中結(jié)點(diǎn)數(shù)累計(jì),全局變量structNodeType //隊(duì)列中的結(jié)點(diǎn)類(lèi)型{intno; //結(jié)點(diǎn)編號(hào)inti; //當(dāng)前結(jié)點(diǎn)在搜索空間中的層次intw; //當(dāng)前結(jié)點(diǎn)的總重量intv; //當(dāng)前結(jié)點(diǎn)的總價(jià)值intx[MAXN]; //當(dāng)前結(jié)點(diǎn)包含的解向量doubleub; //上界};voidEnQueue(NodeTypee,queue<NodeType>&qu)//結(jié)點(diǎn)e進(jìn)隊(duì)qu{if(e.i==n) //到達(dá)葉子結(jié)點(diǎn){if(e.v>maxv) //找到更大價(jià)值的解{maxv=e.v;for(intj=1;j<=n;j++)bestx[j]=e.x[j];}}elsequ.push(e); //非葉子結(jié)點(diǎn)進(jìn)隊(duì)}在結(jié)點(diǎn)進(jìn)隊(duì)時(shí)判斷是否為葉子結(jié)點(diǎn)：葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)解葉子結(jié)點(diǎn)不再擴(kuò)展voidbfs() //求0/1背包的最優(yōu)解{intj;NodeTypee,e1,e2; //定義3個(gè)結(jié)點(diǎn)queue<NodeType>qu; //定義一個(gè)隊(duì)列e.i=0; //根結(jié)點(diǎn)置初值，其層次計(jì)為0e.w=0;e.v=0;e.no=total++;for(j=1;j<=n;j++) e.x[j]=0;bound(e); //求根結(jié)點(diǎn)的上界qu.push(e); //根結(jié)點(diǎn)進(jìn)隊(duì)while(!qu.empty()) //隊(duì)不空循環(huán){e=qu.front();qu.pop();

//出隊(duì)結(jié)點(diǎn)eif(e.w+w[e.i+1]<=W) //剪枝：檢查左孩子結(jié)點(diǎn){e1.no=total++;e1.i=e.i+1; //建立左孩子結(jié)點(diǎn)e1.w=e.w+w[e1.i];e1.v=e.v+v[e1.i];for(j=1;j<=n;j++) //復(fù)制解向量e1.x[j]=e.x[j];e1.x[e1.i]=1;bound(e1); //求左孩子結(jié)點(diǎn)的上界

EnQueue(e1,qu); //左孩子結(jié)點(diǎn)進(jìn)隊(duì)操作}e2.no=total++; //建立右孩子結(jié)點(diǎn)e2.i=e.i+1;e2.w=e.w;e2.v=e.v;for(j=1;j<=n;j++) //復(fù)制解向量e2.x[j]=e.x[j];e2.x[e2.i]=0;bound(e2); //求右孩子結(jié)點(diǎn)的上界if(e2.ub>maxv) //若右孩子結(jié)點(diǎn)可行,則進(jìn)隊(duì),否則被剪枝

EnQueue(e2,qu);}}結(jié)點(diǎn)e→e1,e2，剪枝左孩子：e.w+w[e.i+1]<=W)右孩子：e2.ub>maxv)6.2.2采用優(yōu)先隊(duì)列式分枝限界法求解

采用優(yōu)先隊(duì)列式分枝限界法求解就是將一般的隊(duì)列改為優(yōu)先隊(duì)列，但必須設(shè)計(jì)限界函數(shù)，因?yàn)閮?yōu)先級(jí)是以限界函數(shù)值為基礎(chǔ)的。

限界函數(shù)的設(shè)計(jì)方法與前面的相同。這里用大根堆表示活結(jié)點(diǎn)表，取優(yōu)先級(jí)為活結(jié)點(diǎn)所獲得的價(jià)值。structNodeType //隊(duì)列中的結(jié)點(diǎn)類(lèi)型{intno; //結(jié)點(diǎn)編號(hào)inti; //當(dāng)前結(jié)點(diǎn)在搜索空間中的層次intw; //當(dāng)前結(jié)點(diǎn)的總重量intv; //當(dāng)前結(jié)點(diǎn)的總價(jià)值intx[MAXN]; //當(dāng)前結(jié)點(diǎn)包含的解向量doubleub; //上界

booloperator<(constNodeType&s)const //重載<關(guān)系函數(shù){returnub<s.ub; //ub越大越優(yōu)先出隊(duì)}};voidbfs() //求0/1背包的最優(yōu)解{intj;NodeTypee,e1,e2; //定義3個(gè)結(jié)點(diǎn)

priority_queue<NodeType>qu;

//定義一個(gè)優(yōu)先隊(duì)列（大根堆）e.i=0; //根結(jié)點(diǎn)置初值，其層次計(jì)為0e.w=0;e.v=0;e.no=total++;for(j=1;j<=n;j++)e.x[j]=0;bound(e); //求根結(jié)點(diǎn)的上界qu.push(e); //根結(jié)點(diǎn)進(jìn)隊(duì)while(!qu.empty()) //隊(duì)不空循環(huán){e=qu.top();qu.pop();

//出隊(duì)結(jié)點(diǎn)eif(e.w+w[e.i+1]<=W) //剪枝：檢查左孩子結(jié)點(diǎn){e1.no=total++;e1.i=e.i+1; //建立左孩子結(jié)點(diǎn)e1.w=e.w+w[e1.i];e1.v=e.v+v[e1.i];for(j=1;j<=n;j++)e1.x[j]=e.x[j]; //復(fù)制解向量e1.x[e1.i]=1;bound(e1); //求左孩子結(jié)點(diǎn)的上界EnQueue(e1,qu);

//左孩子結(jié)點(diǎn)進(jìn)隊(duì)操作}e2.no=total++; //建立右孩子結(jié)點(diǎn)e2.i=e.i+1;e2.w=e.w;e2.v=e.v;for(j=1;j<=n;j++)e2.x[j]=e.x[j]; //復(fù)制解向量e2.x[e2.i]=0;bound(e2); //求右孩子結(jié)點(diǎn)的上界if(e2.ub>maxv) //若右孩子結(jié)點(diǎn)剪枝

EnQueue(e2,qu);}}

【算法分析】無(wú)論采用隊(duì)列式分枝限界法還是優(yōu)先隊(duì)列式分枝限界法求解0/1背包問(wèn)題，最壞情況下要搜索整個(gè)解空間樹(shù)，所以最壞時(shí)間和空間復(fù)雜度均為O(2n)，其中n為物品個(gè)數(shù)。6.3求解圖的單源最短路徑

【問(wèn)題描述】給定一個(gè)帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是一個(gè)正整數(shù)。

另外，還給定V中的一個(gè)頂點(diǎn)v，稱(chēng)為源點(diǎn)。計(jì)算從源點(diǎn)到其他所有頂點(diǎn)的最短路徑長(zhǎng)度。這里的長(zhǎng)度是指路上各邊權(quán)之和。6.3.1采用隊(duì)列式分枝限界法求解02435110301006050410200∞∞∞∞∞∞0∞∞∞∞1040∞∞∞∞∞50020∞30∞∞∞0∞100∞∞10600實(shí)例圖隊(duì)列結(jié)點(diǎn)類(lèi)型聲明如下：structNodeType

//隊(duì)列結(jié)點(diǎn)類(lèi)型{intvno; //頂點(diǎn)編號(hào)intlength; //路徑長(zhǎng)度};

用dist數(shù)組存放源點(diǎn)v出發(fā)的最短路徑長(zhǎng)度，dist[i]表示源點(diǎn)v到頂點(diǎn)i的最短路徑長(zhǎng)度，初始時(shí)所有dist[i]值為∞。

用prev數(shù)組存放最短路徑，prev[i]表示源點(diǎn)v到頂點(diǎn)i的最短路徑中頂點(diǎn)i的前驅(qū)頂點(diǎn)。0,0頂點(diǎn)編號(hào)，lengthdist[i]=∞02435110301006050410200+10<∞:prev[2]=0dist[2]=102,100→24,300+30<∞:prev[4]=0dist[4]=300→45,1000+100<∞:prev[5]=0dist[5]=1000→53,6010+50<∞:prev[3]=2dist[3]=602→33,5030+20<60:prev[3]=4dist[3]=504→35,9030+60<100:prev[5]=4dist[5]=904→55,7060+10<90:prev[5]=3dist[5]=703→55,6050+10<70prev[5]=3dist[5]=603→5dist[1]=∞，prev[1]=* dist[2]=10，prev[2]=0dist[3]=50，prev[3]=4 dist[4]=30，prev[4]=0dist[5]=60，prev[5]=3求頂點(diǎn)0出發(fā)的最短路徑#defineINF0x3f3f3f3f//表示∞#defineMAXN51//問(wèn)題表示intn; //圖頂點(diǎn)個(gè)數(shù)inta[MAXN][MAXN]; //圖的鄰接矩陣intv; //源點(diǎn)//求解結(jié)果表示intdist[MAXN]; //dist[i]源點(diǎn)到頂點(diǎn)i的最短路徑長(zhǎng)度intprev[MAXN]; //prev[i]表示源點(diǎn)到j(luò)的最短路徑中頂點(diǎn)j的前驅(qū)頂點(diǎn)structNodeType

//隊(duì)列結(jié)點(diǎn)類(lèi)型{intvno; //頂點(diǎn)編號(hào)intlength; //路徑長(zhǎng)度};voidbfs(intv) //求解算法{NodeTypee,e1;queue<NodeType>pqu;e.vno=v; //建立源點(diǎn)結(jié)點(diǎn)e（根結(jié)點(diǎn)）e.length=0;pqu.push(e); //源點(diǎn)結(jié)點(diǎn)e進(jìn)隊(duì)dist[v]=0;while(!pqu.empty()) //隊(duì)列不空循環(huán){e=pqu.front();pqu.pop();

//出隊(duì)列結(jié)點(diǎn)efor(intj=0;j<n;j++){if(a[e.vno][j]<INF&&e.length+a[e.vno][j]<dist[j]){ //剪枝：e.vno到頂點(diǎn)j有邊并且路徑長(zhǎng)度更短 dist[j]=e.length+a[e.vno][j]; prev[j]=e.vno; e1.vno=j; //建立相鄰頂點(diǎn)j的結(jié)點(diǎn)e1 e1.length=dist[j]; pqu.push(e1); //結(jié)點(diǎn)e1進(jìn)隊(duì)}}}}6.3.2采用優(yōu)先隊(duì)列式分枝限界法求解

采用STL的priority_queue<NodeType>容器作為優(yōu)先隊(duì)列（小根堆），優(yōu)先隊(duì)列結(jié)點(diǎn)類(lèi)型與前面的相同，添加比較重載函數(shù)，即按結(jié)點(diǎn)的length成員值越小越優(yōu)先出隊(duì)，為此設(shè)計(jì)NodeType結(jié)構(gòu)體的比較重載函數(shù)如下：booloperator<(constNodeType&node)const{returnlength>node.length; //length越小越優(yōu)先出隊(duì)}voidbfs(intv) //求解算法{NodeTypee,e1;

priority_queue<NodeType>pqu;

//定義優(yōu)先隊(duì)列e.vno=v; //建立源點(diǎn)結(jié)點(diǎn)ee.length=0;pqu.push(e); //源點(diǎn)結(jié)點(diǎn)e進(jìn)隊(duì)dist[v]=0;while(!pqu.empty()) //隊(duì)列不空循環(huán){e=pqu.top();pqu.pop();

//出隊(duì)列結(jié)點(diǎn)efor(intj=0;j<n;j++){if(a[e.vno][j]<INF&&e.length+a[e.vno][j]<dist[j]){//剪枝：e.vno到頂點(diǎn)j有邊并且路徑長(zhǎng)度更短dist[j]=e.length+a[e.vno][j];prev[j]=e.vno;e1.vno=j; //建立相鄰頂點(diǎn)j的結(jié)點(diǎn)e1e1.length=dist[j];pqu.push(e1); //結(jié)點(diǎn)e1進(jìn)隊(duì)}}}}0,0頂點(diǎn)編號(hào)，lengthdist[i]=∞02435110301006050410200+10<∞:prev[2]=0dist[2]=102,100→24,300+30<∞:prev[4]=0dist[4]=300→45,1000+100<∞:prev[5]=0dist[5]=1000→53,6010+50<∞:prev[3]=2dist[3]=602→33,5030+20<60:prev[3]=4dist[3]=504→35,9030+60<100:prev[5]=4dist[5]=904→55,6050+10<70prev[5]=3dist[5]=603→5dist[1]=∞，prev[1]=* dist[2]=10，prev[2]=0dist[3]=50，prev[3]=4 dist[4]=30，prev[4]=0dist[5]=60，prev[5]=3求頂點(diǎn)0出發(fā)的最短路徑6.4求解任務(wù)分配問(wèn)題

【問(wèn)題描述】有n（n≥1）個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只能分配給一個(gè)人，每個(gè)人只能執(zhí)行一個(gè)任務(wù)。

第i個(gè)人執(zhí)行第j個(gè)任務(wù)的成本是c[i][j]（1≤i，j≤n）。求出總成本最小的分配方案。人員任務(wù)1任務(wù)2任務(wù)3任務(wù)4192782643735818476944個(gè)人員、4個(gè)任務(wù)的信息【問(wèn)題求解】這里采用優(yōu)先隊(duì)列式分枝限界法求解。任務(wù)和人員的編號(hào)均為1～n，解空間每一層對(duì)應(yīng)一個(gè)人員的分配。根結(jié)點(diǎn)對(duì)應(yīng)人員0（虛結(jié)點(diǎn)），依次為人員1、2、…、n分配任務(wù)。葉子結(jié)點(diǎn)對(duì)應(yīng)人員n。解向量為x：x[i]表示人員i分配任務(wù)編號(hào)。初始時(shí)所有元素值為0，表示沒(méi)有分配。臨時(shí)標(biāo)識(shí)數(shù)組worker：worker[i]=true表示任務(wù)i已經(jīng)分配。初始時(shí)所有元素值為false，表示沒(méi)有分配。用bestx[MAXN]存放最優(yōu)分配方案，mincost（初始值為∞）存放最優(yōu)成本。

符號(hào)表示structNodeType

//隊(duì)列結(jié)點(diǎn)類(lèi)型{intno; //結(jié)點(diǎn)編號(hào)inti; //人員編號(hào)intx[MAXN]; //x[i]為人員i分配的任務(wù)編號(hào)boolworker[MAXN]; //worker[i]=true表示任務(wù)i已經(jīng)分配intcost; //已經(jīng)分配任務(wù)所需要的成本intlb; //下界booloperator<(constNodeType&s)const //重載<關(guān)系函數(shù){ returnlb>s.lb;}};

隊(duì)列結(jié)點(diǎn)的類(lèi)型lb為當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)分配方案的成本下界。

例如對(duì)于結(jié)點(diǎn)e：x[]=[2，1，0，0]，表示第1個(gè)人員分配任務(wù)2，第2個(gè)人員分配任務(wù)1，第3、4個(gè)人員沒(méi)有分配任務(wù)；

相對(duì)應(yīng)有worker[]=[true,true,false,false]，表示任務(wù)1和2已經(jīng)分配，而任務(wù)3、4還沒(méi)有分配。此時(shí)計(jì)算結(jié)果是：e.cost=c[1][2]+c[2][1]=2+6=8。

下一步最好的情況是在數(shù)組c中第3行和第4行中找到非第1、2列（因?yàn)槿蝿?wù)1、2已經(jīng)分配）中最小元素和，顯然為1+4=5，即其e.lb=e.cost+5=13。人員任務(wù)1任務(wù)2任務(wù)3任務(wù)4192782643735818476941+4=5e.lb=e.cost+5=13

下界限界函數(shù)設(shè)計(jì)voidbound(NodeType&e) //求結(jié)點(diǎn)e的限界值

{intminsum=0;for(inti1=e.i+1;i1<=n;i1++)//求c[e.i+1..n]行中最小元素和{intminc=INF;for(intj1=1;j1<=n;j1++)//各列中僅僅考慮沒(méi)有分配的任務(wù)if(e.worker[j1]==false&&&&c[i1][j1]<minc)minc=c[i1][j1];minsum+=minc;}e.lb=e.cost+minsum;}人員任務(wù)1任務(wù)2任務(wù)3任務(wù)4192782643735818476941+4=5e.lb=e.cost+5=13e.i=2x[]=[2，1，0，0]求lb的算法

用bestx[MAXN]存放最優(yōu)分配方案，mincost（初始值為∞）存放最優(yōu)成本。

顯然一個(gè)結(jié)點(diǎn)的lb>mincost，則不可能從其子結(jié)點(diǎn)中找到最優(yōu)解，進(jìn)行剪枝。僅僅擴(kuò)展lb≤mincost的結(jié)點(diǎn)。

剪枝操作//問(wèn)題表示intn=4;intc[MAXN][MAXN]={{0},{0,9,2,7,8},{0,6,4,3,7}, {0,5,8,1,8},{0,7,6,9,4}};

//下標(biāo)0的元素不用intbestx[MAXN]; //最優(yōu)分配方案intmincost=INF; //最小成本inttotal=1; //結(jié)點(diǎn)個(gè)數(shù)累計(jì)voidbfs()

//求解任務(wù)分配{intj;NodeTypee,e1;priority_queue<NodeType>qu;memset(e.x,0,sizeof(e.x)); //初始化根結(jié)點(diǎn)的xmemset(e.worker,0,sizeof(e.worker));

//初始化根結(jié)點(diǎn)的workere.i=0; //根結(jié)點(diǎn)，指定人員為0e.cost=0;bound(e); //求根結(jié)點(diǎn)的lbe.no=total++;qu.push(e); //根結(jié)點(diǎn)進(jìn)隊(duì)列while(!qu.empty()){e=qu.top();qu.pop(); //出隊(duì)結(jié)點(diǎn)e，當(dāng)前考慮人員e.iif(e.i==n) //達(dá)到葉子結(jié)點(diǎn){if(e.cost<mincost) //比較求最優(yōu)解{ mincost=e.cost; for(j=1;j<=n;j++) bestx[j]=e.x[j]; } } e1.i=e.i+1; //擴(kuò)展分配下一個(gè)人員的任務(wù)，對(duì)應(yīng)結(jié)點(diǎn)e1 for(j=1;j<=n;j++) //考慮n個(gè)任務(wù) {if(e.worker[j]) //任務(wù)j是否已分配人員,若已分配，跳過(guò)continue; for(inti1=1;i1<=n;i1++) //復(fù)制e.x得到e1.x e1.x[i1]=e.x[i1]; e1.x[e1.i]=j; //為人員e1.i分配任務(wù)jfor(inti2=1;i2<=n;i2++) //復(fù)制e.worker得到e1.workere1.worker[i2]=e.worker[i2];e1.worker[j]=true; //表示任務(wù)j已經(jīng)分配e1.cost=e.cost+c[e1.i][j];bound(e1); //求e1的lbe1.no=total++;if(e1.lb<=mincost) //剪枝qu.push(e1);}}}1人員任務(wù)1任務(wù)2任務(wù)3任務(wù)419278264373581847694i=1，cost=2lb=10x[]={2,0,0,0}i=0，cost=0lb=10x[]={0,0,0,0}i=1，cost=9lb=17x[]={1,0,0,0}23i=1，cost=7lb=15x[]={3,0,0,0}4i=1，cost=8lb=16x[]={4,0,0,0}5j=1j=2j=3j=4為e.i+1任務(wù)分配人員ji=2，cost=8lb=13x[]={2,1,0,0}6i=2，cost=5lb=14x[]={2,3,0,0}7i=2，cost=9lb=17x[]={2,4,0,0}8j=1j=3j=4i=3，cost=9lb=13x[]={2,1,3,0}9i=3，cost=16lb=25x[]={2,1,4,0}10j=3j=4i=4，cost=13lb=13x[]={2,1,3,4}11j=4其他子結(jié)點(diǎn)被剪枝！解結(jié)點(diǎn)程序的執(zhí)行結(jié)果：最優(yōu)方案:第1個(gè)人員分配第2個(gè)任務(wù)

第2個(gè)人員分配第1個(gè)任務(wù)

第3個(gè)人員分配第3個(gè)任務(wù)

第4個(gè)人員分配第4個(gè)任務(wù)總成本=13人員任務(wù)1任務(wù)2任務(wù)3任務(wù)419278264373581847694x[]={2,1,3,4}6.5求解流水作業(yè)調(diào)度問(wèn)題

【問(wèn)題描述】有n個(gè)作業(yè)（編號(hào)為1～n）要在由兩臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi（1≤i≤n）。

流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少?？梢约俣ㄈ魏巫鳂I(yè)一旦開(kāi)始加工，就不允許被中斷，直到該作業(yè)被完成，即非優(yōu)先調(diào)度。

【問(wèn)題求解】作業(yè)編號(hào)為1到n，調(diào)度方案的執(zhí)行步驟為1到n，解空間每一層對(duì)應(yīng)一個(gè)步驟的作業(yè)分配。

根結(jié)點(diǎn)對(duì)應(yīng)步驟0（虛），依次為步驟1、2、…、n分配任務(wù)，葉子結(jié)點(diǎn)對(duì)應(yīng)步驟n。根結(jié)點(diǎn)（i=0）…j=1j=2j=n…j=2j=3j=n……步驟1步驟2葉子結(jié)點(diǎn)為一個(gè)可行解，比較求最優(yōu)解

對(duì)于按1～n順序執(zhí)行的某種調(diào)度方案，f1表示在M1上執(zhí)行完當(dāng)前第i步的作業(yè)對(duì)應(yīng)的總時(shí)間，f2數(shù)組表示在M2上執(zhí)行完當(dāng)前第i步的作業(yè)的總時(shí)間。

若第i步執(zhí)行作業(yè)j，計(jì)算公式如下：f1=f1+a[j];f2[i]=max(f1，f2[i-1])+b[j]

這里由于每個(gè)結(jié)點(diǎn)中都保存了f1和f2，因此可以將f2數(shù)組改為單個(gè)變量。將每個(gè)隊(duì)列結(jié)點(diǎn)的類(lèi)型聲明如下：structNodeType

//隊(duì)列結(jié)點(diǎn)類(lèi)型{intno; //結(jié)點(diǎn)編號(hào)intx[MAX]; //x[i]表示第i步分配作業(yè)編號(hào)inty[MAX]; //y[i]=1表示編號(hào)為i的作業(yè)已經(jīng)分配inti; //步驟編號(hào)intf1; //已經(jīng)分配作業(yè)M1的執(zhí)行時(shí)間intf2; //已經(jīng)分配作業(yè)M2的執(zhí)行時(shí)間intlb; //下界booloperator<(constNodeType&s)const //重載<關(guān)系函數(shù){ returnlb>s.lb; //lb越小越優(yōu)先出隊(duì)}};那么如果計(jì)算lb呢？x[1]x[i]x[n]x[i+1]ee1e.f2為總時(shí)間已經(jīng)執(zhí)行的作業(yè)

執(zhí)行時(shí)間e1.f2尚未執(zhí)行的作業(yè)

最少執(zhí)行時(shí)間為它們的b之和e1.lb=+lb為當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)調(diào)度方案的時(shí)間下界。

例如，對(duì)于出隊(duì)結(jié)點(diǎn)e，如果在第2步選擇作業(yè)1（j=1），對(duì)應(yīng)結(jié)點(diǎn)為e1，則：e1.i=e.i+1=2，e1.f1=e.f1+a[1]=9e1.f2=max(e.f2，e1.f1)+b[1]=18+6=24e1.x=[3，1，0，0]e1.y=[1，0，1，0]作業(yè)編號(hào)1234M1時(shí)間a51248M2時(shí)間b62147i=1,f1=4f2=18,lb=33x[]={3,0,0,0}y[]={0,0,1,0}i=2,f1=9f2=24,lb=33x[]={3,1,0,0}y[]={1,0,1,0}j=1結(jié)點(diǎn)e結(jié)點(diǎn)e1e1.lb=e1.f2+沒(méi)有分配的作業(yè)在M2上的時(shí)間和=e1.f2+作業(yè)2和4在M2上的時(shí)間和=24+2+7=33。對(duì)應(yīng)的求結(jié)點(diǎn)e的lb的算法如下：voidbound(NodeType&e) //求結(jié)點(diǎn)e的限界值

{intsum=0;for(inti=1;i<=n;i++) //掃描所有作業(yè)if(e.y[i]==0)sum+=b[i];

//僅累計(jì)e.x中還沒(méi)有