算法分支限界法教學(xué)教案

1、；.第六章 分支限界法1 學(xué)習(xí)要點(diǎn)1.1 學(xué)習(xí)要點(diǎn)理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）隊(duì)列式(FIFO)分支限界法（2）優(yōu)先隊(duì)列式分支限界法 通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。（1）單源最短路徑問題（2）裝載問題；（4）0-1背包問題；（8）批處理作業(yè)調(diào)度問題2 分支限界法的基本思想2.1 分支限界法描述采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分支限界法。所謂“分支”是采用廣度優(yōu)先的策略，依次生成擴(kuò)展結(jié)點(diǎn)的所有分支（即：兒子結(jié)點(diǎn)）。所謂“限界”是在結(jié)點(diǎn)擴(kuò)展過程中，計(jì)算結(jié)點(diǎn)的上界（或下界），邊搜索邊減掉搜索樹的某些分支，從而提高搜索效率。原理按照廣度

2、優(yōu)先的原則，一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)（E-結(jié)點(diǎn)）R后，算法將依次生成它的全部孩子結(jié)點(diǎn)，將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。然后，從活結(jié)點(diǎn)表中取出一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程，直至找到問題的解或判定無解為止。2.2 分支限界法與回溯法求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先的方式搜索解空間樹。分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方

3、式搜索問題的解空間樹。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。2.3 常見的兩種分支限界法隊(duì)列式(FIFO)分支限界法 按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。搜索策略：一開始，根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入隊(duì)。從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子，

4、用約束條件檢查，把所有滿足約束函數(shù)的兒子加入活結(jié)點(diǎn)隊(duì)列中。再從活結(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)（隊(duì)中最先進(jìn)來的結(jié)點(diǎn)）為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。隊(duì)列式分支限界法搜索解空間樹的方式與解空間樹的廣度優(yōu)先遍歷算法極為相似，唯一的不同之處是隊(duì)列式分支限界法不搜索以不可行結(jié)點(diǎn)為根的子樹。優(yōu)先隊(duì)列式分支限界法 基本思想：為了加速搜索的進(jìn)程，應(yīng)采用有效的方式選擇活結(jié)點(diǎn)進(jìn)行擴(kuò)展。按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 搜索策略：對(duì)每一活結(jié)點(diǎn)計(jì)算一個(gè)優(yōu)先級(jí)（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級(jí)；從當(dāng)前活結(jié)點(diǎn)表中優(yōu)先選擇一個(gè)優(yōu)先級(jí)最高（最有利）的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著

5、解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。再從活結(jié)點(diǎn)表中下一個(gè)優(yōu)先級(jí)別最高的結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。3 0 -1背包問題3.1 算法思想首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。在優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。template<class Typew,class Typep>Typep Knap<Typew,Typep>:Bound(int i) /計(jì)算節(jié)點(diǎn)所相應(yīng)價(jià)值的上界 Typew cleft = c-cw; /剩余

6、容量高 Typep b = cp; /價(jià)值上界 /以物品單位重量價(jià)值遞減序裝填剩余容量 while(i<=n && wi<=cleft) cleft -= wi; b += pi; i+; /裝填剩余容量裝滿背包 if(i<=n) b += pi/wi*cleft; return b;算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中，判斷方法同回溯法。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列，判斷方法同回溯法。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值

7、。例如：0-1背包問題，當(dāng)n=3時(shí)，w=16,15,15, p=45,25,25, c=30。優(yōu)先隊(duì)列式分支限界法處理法則：價(jià)值大者優(yōu)先。取結(jié)點(diǎn)的當(dāng)前價(jià)值排序（按照書本P162邏輯）。>A>B,C【>C，D（舍去），E】>E，C【>C，J（舍去），K】>K，C>F，G>G，L，M【>G，M（L，M已是葉節(jié)點(diǎn)）】>G>N，O>O>3.2 隊(duì)列式(FIFO)算法示例解空間樹如下圖所示，1代表選擇，0代表不選。分支限界法如下處理：可擴(kuò)展結(jié)點(diǎn)：A     活結(jié)點(diǎn)隊(duì)列：B，C選擇路徑 ： AW：0P：0可擴(kuò)

8、展結(jié)點(diǎn)：B； 活結(jié)點(diǎn)隊(duì)列：C，D，E選擇路徑： A->BW：16P：45可擴(kuò)展結(jié)點(diǎn)：C    活結(jié)點(diǎn)隊(duì)列：D，E，F(xiàn)，G選擇路徑： A->CW：0 P：0如果擴(kuò)展D，那么當(dāng)前w = 31 > 30越界，所以直接進(jìn)行剪枝，解空間樹變成如下：                                       可擴(kuò)展結(jié)點(diǎn)：E  

9、; 活結(jié)點(diǎn)隊(duì)列：F，G，J，K選擇路徑： A->B->EW：16P：45可擴(kuò)展結(jié)點(diǎn)：F   活結(jié)點(diǎn)隊(duì)列：G，J，K，L，M選擇路徑： A->C->FW：15P：25可擴(kuò)展結(jié)點(diǎn)：G   活結(jié)點(diǎn)隊(duì)列：J，K，L，M，N，O選擇路徑： A->C->GW：0P：0如果擴(kuò)展J，那么當(dāng)前w = 16+15=31>30，所以對(duì)J剪枝，解空間樹變?yōu)椋嚎蓴U(kuò)展結(jié)點(diǎn)：K  活結(jié)點(diǎn)隊(duì)列：L，M，N，O選擇路徑： A->B->E->K W：16 P：45可擴(kuò)展結(jié)點(diǎn)：L  活結(jié)點(diǎn)隊(duì)列：M，N，O選擇路徑： A->C-

10、>F->L W：30 P：50可擴(kuò)展結(jié)點(diǎn)：M  活結(jié)點(diǎn)隊(duì)列：N，O選擇路徑： A->C->F->MW：15P：25可擴(kuò)展結(jié)點(diǎn)：N  活結(jié)點(diǎn)隊(duì)列：O選擇路徑： A->C->G->N W：15 P：25可擴(kuò)展結(jié)點(diǎn)：O  活結(jié)點(diǎn)隊(duì)列：NULL選擇路徑： A->C->G->OW：0P：0活結(jié)點(diǎn)隊(duì)列為空，算法終止，從可行解中篩選出最佳解為（0,1,1），maxP = 50；3.3 完整代碼#include <iostream>using namespace std;/-template <c

11、lass Type>inline void Swap(Type &a,Type &b) Type temp = a; a = b; b = temp;template<class Type>void BubbleSort(Type a,int n) /記錄一次遍歷中是否有元素的交換 bool exchange; for(int i=0; i<n-1;i+) exchange = false ; for(int j=i+1; j<=n-1; j+) if(aj<=aj-1) Swap(aj,aj-1); exchange = true; /如果

12、這次遍歷沒有元素的交換,那么排序結(jié)束 if(false = exchange) break ; /-class Object template<class Typew,class Typep> friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx);public: int operator <= (Object a) const return d>=a.d; private: int ID; float d; /單位重量價(jià)值;/-template<class Typew,class Typep

13、> class Knap;/返回最大價(jià)值，bestx返回最優(yōu)解template<class Typew,class Typep>Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx) /初始化 Typew W = 0; /裝包物品重量 Typep P = 0; /裝包物品價(jià)值 /定義依單位重量價(jià)值排序的物品數(shù)組 Object *Q = new Objectn; for(int i=1; i<=n; i+) /單位重量價(jià)值數(shù)組 Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W

14、+= wi; if(W<=c) return P;/所有物品裝包 /依單位價(jià)值重量排序 BubbleSort(Q,n); /創(chuàng)建類Knap的數(shù)據(jù)成員 Knap<Typew,Typep> K; K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i<=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; /調(diào)用MaxKnapsack求問題的最優(yōu)解 Typep bestp = K.MaxKnapsack(); for(

15、int j=1; j<=n; j+) bestxQj-1.ID = K.bestxj; delete Q; delete K.w; delete K.p; delete K.bestx; return bestp;template<class T>class MaxHeap public: MaxHeap(int MaxHeapSize = 10); MaxHeap() delete heap; int Size() const return CurrentSize; T Max() if (CurrentSize = 0) return heap1; MaxHeap<

16、T>& Insert(const T& x); MaxHeap<T>& DeleteMax(T& x); void Initialize(T a, int size, int ArraySize);private: int CurrentSize, MaxSize; T *heap; / element array;template<class T>MaxHeap<T>:MaxHeap(int MaxHeapSize) MaxSize = MaxHeapSize; heap = new TMaxSize+1; Curre

17、ntSize = 0;template<class T>MaxHeap<T>& MaxHeap<T>:Insert(const T& x) if(CurrentSize = MaxSize) cout<<"no space!"<<endl; return *this; / 尋找新元素x的位置 / i初始為新葉節(jié)點(diǎn)的位置，逐層向上，尋找最終位置 int i = +CurrentSize; while (i != 1 && x > heapi/2) / i不是根節(jié)點(diǎn)，且其值大于父節(jié)

18、點(diǎn)的值，需要繼續(xù)調(diào)整 heapi = heapi/2; / 父節(jié)點(diǎn)下降 i /= 2; / 繼續(xù)向上，搜尋正確位置 heapi = x; return *this;template<class T>MaxHeap<T>& MaxHeap<T>:DeleteMax(T& x) / Set x to max element and delete max element from heap. / check if heap is empty if(CurrentSize = 0) cout<<"Empty heap!"

19、;<<endl; return *this; x = heap1; / 刪除最大元素 / 重整堆 T y = heapCurrentSize-; / 取最后一個(gè)節(jié)點(diǎn)，從根開始重整 / find place for y starting at root int i = 1, / current node of heap ci = 2; / child of i while (ci <= CurrentSize) / 使ci指向i的兩個(gè)孩子中較大者 if(ci<CurrentSize && heapci < heapci+1) ci+; / y的值大于

20、等于孩子節(jié)點(diǎn)嗎？ if(y >= heapci) break; / 是，i就是y的正確位置，退出 / 否，需要繼續(xù)向下，重整堆 heapi = heapci; / 大于父節(jié)點(diǎn)的孩子節(jié)點(diǎn)上升 i = ci; / 向下一層，繼續(xù)搜索正確位置 ci *= 2; heapi = y; return *this;template<class T>void MaxHeap<T>:Initialize(T a, int size,int ArraySize) delete heap; heap = a; CurrentSize = size; MaxSize = ArraySi

21、ze; / 從最后一個(gè)內(nèi)部節(jié)點(diǎn)開始，一直到根，對(duì)每個(gè)子樹進(jìn)行堆重整 for(int i = CurrentSize/2; i >= 1; i-) T y = heapi; / 子樹根節(jié)點(diǎn)元素 / find place to put y int c = 2*i; / parent of c is target location for y while (c <= CurrentSize) / heapc should be larger sibling if (c < CurrentSize && heapc < heapc+1) c+; / can we

22、 put y in heapc/2? if (y >= heapc) break; / yes / no heapc/2 = heapc; / move child up c *= 2; / move down a level heapc/2 = y; /-class bbnode public: template<class Typew,class Typep> friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); bbnode * parent; /指向父節(jié)點(diǎn)的指針 bool LChild; /左

23、兒子節(jié)點(diǎn)標(biāo)識(shí);template<class Typew,class Typep>class HeapNode public: operator Typep() const return uprofit; Typep uprofit, /節(jié)點(diǎn)的價(jià)值上界 profit; /節(jié)點(diǎn)所相應(yīng)的價(jià)值 Typew weight; /節(jié)點(diǎn)所相應(yīng)的重量 int level; /活節(jié)點(diǎn)在子集樹中所處的層序號(hào) bbnode *ptr; /指向活節(jié)點(diǎn)在子集中相應(yīng)節(jié)點(diǎn)的指針;/-template<class Typew,class Typep>class Knap public: Typep Ma

24、xKnapsack(); MaxHeap<HeapNode<Typep,Typew> > *H; Typep Bound(int i); void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev); bbnode *E; /指向擴(kuò)展節(jié)點(diǎn)的指針 Typew c; /背包容量 int n; /物品數(shù) Typew *w; /物品重量數(shù)組 Typep *p; /物品價(jià)值數(shù)組 Typew cw; /當(dāng)前重量 Typep cp; /當(dāng)前價(jià)值 int *bestx; /最優(yōu)解;template<class Typew

25、,class Typep>Typep Knap<Typew,Typep>:Bound(int i) /計(jì)算節(jié)點(diǎn)所相應(yīng)價(jià)值的上界 Typew cleft = c-cw; /剩余容量高 Typep b = cp; /價(jià)值上界 /以物品單位重量價(jià)值遞減序裝填剩余容量 while(i<=n && wi<=cleft) cleft -= wi; b += pi; i+; /裝填剩余容量裝滿背包 if(i<=n) b += pi/wi*cleft; return b;/將一個(gè)活節(jié)點(diǎn)插入到子集樹和優(yōu)先隊(duì)列中template<class Typew,c

26、lass Typep>void Knap<Typew,Typep>:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev) bbnode *b = new bbnode; b->parent = E; b->LChild = ch; HeapNode<Typep,Typew> N; N.uprofit = up; N.profit = cp; N.weight = cw; N.level = lev; N.ptr = b; H->Insert(N);/優(yōu)先隊(duì)列式分支限界法，返回最大價(jià)值，be

27、stx返回最優(yōu)解template<class Typew,class Typep>Typep Knap<Typew,Typep>:MaxKnapsack() H = new MaxHeap<HeapNode<Typep,Typew> >(1000); /為bestx分配存儲(chǔ)空間 bestx = new intn+1; /初始化 int i = 1; E = 0; cw = cp = 0; Typep bestp = 0;/當(dāng)前最優(yōu)值 Typep up = Bound(1); /價(jià)值上界 /搜索子集空間樹 while(i!=n+1) /檢查當(dāng)前擴(kuò)展

28、節(jié)點(diǎn)的左兒子節(jié)點(diǎn) Typew wt = cw + wi; if(wt <= c) /左兒子節(jié)點(diǎn)為可行節(jié)點(diǎn) if(cp+pi>bestp) bestp = cp + pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up = Bound(i+1); /檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的右兒子節(jié)點(diǎn) if(up>=bestp) /右子樹可能含有最優(yōu)解 AddLiveNode(up,cp,cw,false,i+1); /取下一擴(kuò)展節(jié)點(diǎn) HeapNode<Typep,Typew> N; H->DeleteMax(N); E = N.ptr; cw =

29、 N.weight; cp = N.profit; up = N.uprofit; i = N.level; /構(gòu)造當(dāng)前最優(yōu)解 for(int j=n; j>0; j-) bestxj = E->LChild; E = E->parent; return cp;/-int main() int n = 3; /物品數(shù) int c = 30; /背包容量 int p = 0,45,25,25; /物品價(jià)值 下標(biāo)從1開始 int w = 0,16,15,15; /物品重量 下標(biāo)從1開始 int bestx4; /最優(yōu)解 cout<<"背包容量為："<<c<<endl; cout<<"物品重量和價(jià)值分別為："<<endl; for(int i=1; i<=n; i+) cout<<"("<<wi<<","<<pi<<") " co