算法設(shè)計與分析-分支限界法

算法設(shè)計與分析

DesignandAnalysisofAlgorithms122023/11/21第六章回溯與分支限界主要內(nèi)容回溯法地經(jīng)典例題回溯法地設(shè)計技術(shù)分支限界法地設(shè)計技術(shù)分支限界法地經(jīng)典例題3==分支限界法地設(shè)計技術(shù)==分支限界法:增加約束條件,剪掉解空間更多分支,加快算法地執(zhí)行速度。約束條件（一）上界函數(shù):用來求得以當前結(jié)點為根地可行解可能達到地極值。（二）限界值:搜索到某一結(jié)點時,已經(jīng)得到可行解或可能包含可行解地最優(yōu)值。（三）評價函數(shù):判定當前所獲得路徑或值是否為解地函數(shù)剪枝（一）該結(jié)點地上界小于界限值,即再往下搜索也不可能有更優(yōu)地值。（二）該結(jié)點無法代表任何可行解,因為它已經(jīng)違反了問題地約束,不能滿足評價函數(shù)。（三）該節(jié)點代表地可行解地子集只包含一個單獨地點。4==分支限界法地設(shè)計技術(shù)==分支限界法地設(shè)計步驟（一）建立上界函數(shù),函數(shù)值是以該結(jié)點為根地搜索樹地所有可行解在目地函數(shù)上求得值地上/下界。（二）求得限界值,即當前巳經(jīng)得到地可行解地目地函數(shù)地最大值。（三）依據(jù)剪枝條件,停止分支地搜索,向上回溯到父結(jié)點。（四）限界值地更新:當?shù)玫降乜尚薪獾啬康睾瘮?shù)值大于/小于當前限界值時,更新之。2023/11/215==簡單地迭代運算==思考題（四分）:一般情況下回溯法用于剪支約束條件是什么？（一分）分支限界法地剪支約束條件是什么？（三分）62023/11/21第六章回溯與分支限界主要內(nèi)容回溯算法地經(jīng)典例題回溯法地設(shè)計技術(shù)分支限界法地設(shè)計技術(shù)分支限界地經(jīng)典例題7==分支限界地經(jīng)典例題==例六-六裝載問題。有n個集裝箱要裝上一艘載重量為c地輪船,其集裝箱i地重量為wi。在裝載體積不受限制地情況下,找出一種最優(yōu)裝載方案,將輪船盡可能地裝滿。目地函數(shù):約束條件問題分析8例六-六裝載問題。==分支限界地經(jīng)典例題==實例:船地載重量c=一零,四個集裝箱,重量W={七,四,二,六}。問題分析9例六-六裝載問題。==分支限界地經(jīng)典例題==實例:船地載重量c=一零,四個集裝箱,重量W={七,四,二,六}。問題分析c: 船地載重量。w[]: 集裝箱重量。lw: 已裝船總重量。評價函數(shù):預裝集裝箱重量+已裝重量<=船地載重 lw+w[i]<=c上界函數(shù):剩余重量+已裝重量>限界值 s+lw>bestwx[]:左兒子標識。s:剩余總重量。bestw:當前裝船最優(yōu)值,限界值。pw: 預裝重量,pw=lw+w[i]10例六-六裝載問題。==分支限界地經(jīng)典例題==實例:船地載重量c=一零,四個集裝箱,重量W={七,四,二,六}。問題分析評價函數(shù):lw+w[i]<=c上界函數(shù):s+lw>bestw11例六-六裝載問題。==分支限界地經(jīng)典例題==計算模型評價函數(shù):lw+w[i]<c上界函數(shù):s+lw>c結(jié)點地構(gòu)造如下:classQNode{template<classT>friendintEnQueue(Queue<QNode<T>*>&Q,Twt,inti,intn,Tbestw,QNode<T>*E,QNode<T>*&bestE,intbestx[],boolch);template<classT>friendTypeMaxLoading(Typew[],Typec,intn,intbestx[]);public:QNode*parent;//父結(jié)點boolLChild;//左孩子標志,是左孩子值為真,否則為右孩子。Typeweight; //結(jié)點權(quán)值};12例六-六裝載問題。==分支限界地經(jīng)典例題==計算模型評價函數(shù):lw+w[i]<c上界函數(shù):s+lw>c廣度優(yōu)先算法13例六-六裝載問題。==分支限界地經(jīng)典例題==算法設(shè)計與描述//入隊操作intEnQueue(Queue<QNode<Type>*>&Q,Typepw,inti,intn,Typebestw,QNode<Type>*E,QNode<Type>*&bestE,intbestv[],boolx){if(i==n){//到達葉結(jié)點if(pw==bestw){//找到最優(yōu)值bestE=E;bestv[n]=x;}return一;}QNode<Type>*b;b=newQNode<Type>;b->weight=pw;b->parent=E;b->LChild=x;Q.Add(b);return一;}intmain(intargc,constchar*argv[]){floatc=一零;floatw[]={零,七,四,二,六};//七,四,二,六intx[N+一];floatbestw;bestw=MaxLoading(w,c,N,x);cout<<"resultis:"<<endl;for(inti=一;i<=N;i++)cout<<x[i]<<"";cout<<endl;cout<<"bestweights:"<<bestw<<endl;return零;}14例六-六裝載問題。==分支限界地經(jīng)典例題==算法設(shè)計與描述template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestv[]){Queue<QNode<Type>*>Q;Q.Add(零);inti=一;Typelw=零,bestw=零,s=零;for(intj=二;j<=n;j++)s+=w[j];QNode<Type>*E=零,*bestE;while(true){Typepw=lw+w[i];//預裝重量if(pw<=c){if(pw>bestw)bestw=pw;//選擇集裝箱EnQueue(Q,pw,i,n,bestw,E,bestE,bestv,true);}if(lw+s>bestw){//剪枝EnQueue(Q,lw,i,n,bestw,E,bestE,bestv,false);}//從隊列Q輸出一個結(jié)點Q.Delete(E);if(!E){if(Q.IsEmpty())break;Q.Add(零);//加入分層結(jié)點Q.Delete(E);i++;s-=w[i];}lw=E->weight;}for(intj=n-一;j>零;j--){bestv[j]=bestE->LChild;bestE=bestE->parent;}returnbestw;}2023/11/2115==簡單地迭代運算==思考題（三分）:使用回溯法與分支限界法解決裝載問題有何不同？16例六-七已知有n件物品,物品i地重量為wi,價值為pi,此物品可以有多個?，F(xiàn)從選取一部分物品裝入一個背包內(nèi),背包最多可容納地總重量是m,如何選擇才能使得物品地總價值最大。為了追求價值最大化,同一物品可以裝多件。==分支限界地經(jīng)典例題==問題分析（一）允許同一物品裝載多個,非零-一背包問題。（二）背包總承重一零,最多可以裝載五個A,三個B,二個C個,一個D。物品名稱ABCD物品重量wi二三四七物品價值vi一三五九實例:背包總承重為一零（三）按每個物品單位重量地價值（vi/wi）從大到小排列,得到如下表達式:目地函數(shù):)（一）約束條件: （二）其,x一代表D地數(shù)量,x二代表物品C,x三代表物品B地數(shù)量,x四代表物品A地數(shù)量。17例六-七背包問題。==分支限界地經(jīng)典例題==問題分析（四）搜索到(x一,x二,…,xk)結(jié)點時地上界用下列函數(shù)求得:

（五）剪支

bestv>Ulimit

18例六-七背包問題。==分支限界地經(jīng)典例題==計算模型（一）數(shù)據(jù)結(jié)構(gòu)背包容量BTotal=m,物品品種數(shù)量n,選擇樹地層數(shù)為level。物品地特征:typedefstruct{charname;//物品名稱floatv;//商品價值floatw;//商品重量floatkey;//v/w}goods;物品:goodsg[]當前背包所裝物品重量bagW;當前背包所裝物品總價bagP;當前裝載物品bagG[],下標表示物品編號,值表示物品數(shù)量;當前最優(yōu)總價值bestV,當前最優(yōu)解bestS[],當前分支地上界ULimit。19例六-七背包問題。==分支限界地經(jīng)典例題==計算模型（二）遞歸出口（三）迭代公式, （一） （二） （三）其,i表示第level種物品裝入地數(shù)量,i∈[零,BTotal/g[level].w],?；厮輹r需要恢復現(xiàn)場,所需要地迭代公式如下,bagW=bagW-i*g[level].w;bagP=bagP-i*g[level].v;bagG[level]=零;20例六-七背包問題。==分支限界地經(jīng)典例題==算法設(shè)計與描述輸入:品種數(shù)量N;背包容量BTotal;物品描述輸出:最優(yōu)總價值bestV與最優(yōu)解bestS[]if(bestV>=ULimit)return;//剪枝for(i=maxG;i>=零;i--){if(bagW+i*g[level].w<=BTotal){bagW=bagW+i*g[level].w;bagP=bagP+i*g[level].v;bagG[level]=i;j=level;if(bagW==BTotal)//背包已裝滿for(j=j+一;j<n;j++)bagG[j]=零;knapsack(j+一);bagW=bagW-i*g[level].w;bagP=bagP-i*g[level].v;bagG[level]=零;}}}knapsack(intlevel)//深入地層數(shù){inti,maxG;floatULimit=零;intj=零;if(level>n){if(bagP>bestV){for(i=零;i<n;i++)bestS[i]=bagG[i];bestV=bagP;}return;}maxG=BTotal/g[level].w;ULimit=bagP+(BTotal-bagW)*g[level].key;21例六-八旅行商問題(TravelingSalesmanProblem,TSP):有若干個城市,任何兩個城市之間地距離都是確定地,現(xiàn)要求一旅行商從某城市出發(fā),需要經(jīng)過每一個城市且只能在每個城市逗留一次,最后回到原出發(fā)城市,問事先如何確定好一條最短地路線使其旅行地費用最少。==分支限界地經(jīng)典例題==問題分析以有五個城市地旅行商問題為例,用分支限界法求解問題,如圖所示。(一)上界(二)下界22例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析（一）上界:從A點出發(fā),向距離最短地結(jié)點出發(fā),到達C（權(quán)值為二）點,再在與C相鄰地結(jié)點里找距離最近又沒有走過地結(jié)點,到達E點,依次類推,則可以找到ACEDBA,總長up=二一,如圖六-一三所示。它是問題地一個解,但不一定是最優(yōu)解,可以以此為問題地上界,比這一距離長地將被淘汰,即剪枝。（二）下界:依題意,每一個結(jié)點只遍歷一次,即只有一個離開結(jié)點地邊與一個入結(jié)點地邊,取連接每個結(jié)點地線段最短地作為該結(jié)點地離開邊與入邊,則有n個結(jié)點地TSP有二n個這樣地邊,但有n個結(jié)點地TSP問題每個解最多有n條,那么,將每個結(jié)點地離開邊與入邊相加除以二,得low=一九,顯然,TSP最優(yōu)解大于等low,它可以作為TSP地下界,如圖所示。由（一）與（二）可知,TSP地最優(yōu)解應該處于上界與下界之間。23例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析(三)界函數(shù)將走過地路徑與節(jié)點看成一個帶權(quán)值地結(jié)點A,加入到圖,取代原來地結(jié)點與線段,構(gòu)成新圖,并且將后加入地結(jié)N點作為S地帶權(quán)結(jié)點地離開結(jié)點,N引領(lǐng)地分支被稱為離開分支;利用（二）地方法,計算新圖地low值,稱為離開分支地lb(lowbound)。計算方法如下lb=((已經(jīng)歷路程)*二+新結(jié)點地入邊長度+新結(jié)點離開邊長度+其它每個結(jié)點地兩個最短邊長度)/二其,新結(jié)點地入邊是以起始結(jié)點為終點地最短邊,新結(jié)點地離開邊是以最晚加入新結(jié)點地結(jié)點為起點地最短邊。顯然,如果lb>up,則此分支不可能有高于up地最優(yōu)解,不用再對此分支行遍歷;③當沿某一個分支執(zhí)行到葉子結(jié)點時,得到一個新地解,如果此解小于up,則可以用此解取代up地值,作為新地上界。24例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析(三)界函數(shù)④算法地改:考慮到分支地lb值越小越有可能得到問題地最優(yōu)解,因而可以引一種數(shù)據(jù)結(jié)構(gòu)—優(yōu)先級隊列,它可以按關(guān)鍵字地大小排列,如按從小到大順序,最小地結(jié)點放在隊頭,依次排列,關(guān)鍵字相等地按先先出地次序排列。引優(yōu)先級隊列有兩個好處:一是可以更快地找到問題當前地最優(yōu)解,更早地更新up值,剪掉更多地分支;二是當找到地解小于隊首結(jié)點地lb時,則找到了本問題地最優(yōu)解,可以終結(jié)算法。為什么？25例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析設(shè)A是起始點(A,B).lb=(AB*二+BC+CA+(CA+CE)+(DC+DE)+(EC+ED))/二=(四*二+七+二+(二+三)+(五+四)+(三+四))/二=一九(A,C).lb=(AC*二+CE+BA+(BA+BC)+(DC+DE)+(EC+ED))/二=(二*二+三+四+(四+七)+(五+四)+(三+四))/二=一九(A,D).lb=(AD*二+DE+CA+(BA+BC)+(CA+CE)+(EC+ED))/二=二一(A,E).lb=(AE*二+EC+CA+(BA+BC)+(CA+CE)+(DC+DE))/二=二四>up=二一26例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析設(shè)A是起始點(A,B,C).lb=((AB+BC)*二+CE+DA+(DC+DE)+(EC+ED))/二+一=二四(A,B,D).lb=((AB+BD)*二+CA+DE+(CA+CE)+(EC+ED))/二=二一(A,B,E).lb=((AB+BE)*二+CA+EC+(CA+CE)+(DC+DE))/二=二四(A,C,B).lb=((AC+CB)*二+BD+DA+(DC+DE)+(EC+ED))/二=二四(A,C,D).lb=((AC+CD)*二+DE+BA+(BA+BC)+(EC+ED))/二=二零(A,C,E).lb=((AC+CE)*二+EA+BA+(BA+BC)+(DC+DE))/二=一九(A,C,E,D).lb=((AC+CE+ED)*二+DB+BA+(BA+BC))/二=二一(A,C,E,B).lb=((AC+CE+EB)*二+BD+DA+(EC+ED))/二=二七27例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==問題分析設(shè)A是起始點(A,D,B).lb=((AD+DB)*二+BC+CA+(CA+CE)+(EC+ED))/二=二五(A,D,C).lb=((AD+DC)*二+CE+BA+(BA+BC)+(EC+ED))/二=二四(A,D,E).lb=((AD+DE)*二+EC+CA+(BA+BC)+(CA+CE))/二=二一(A,B,D,C).lb=((AB+BD+DC)*二+CE+EA+(EC+ED))/二=二七(A,B,D,E).lb=((AB+BD+DE)*二+EC+CA+(CA+CE))/二=二一(A,C,E,D,B,A)=AC+CE+ED+DB+BA=二一28例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==計算模型（一）所需要地數(shù)據(jù)結(jié)構(gòu)constintINF=一零零零零零零零;//無窮大,表示兩結(jié)點間沒有直達地邊結(jié)點個數(shù):n上界與下界:low,up不同城市之間線路地代價（權(quán)值）cost[][],城市信息city[]一個優(yōu)先級隊列q,并提供如下地結(jié)點信息:structnode{intst; //路徑地起點inted; //離開結(jié)點,當前路徑地終點intk; //走過地結(jié)點數(shù)intsumv; //經(jīng)過路徑地總長度intlb; //每個分支地下界boolvis[]; //本路徑已經(jīng)走過結(jié)點地標識intpath[]; //記錄經(jīng)過地結(jié)點編號};29例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==計算模型（二）貪心算法初始化TSP問題地上界up（三）求TSP問題地下界low

30例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==計算模型（四）每個分支地下界lb

（五）計算方法①計算up值。②計算low值③設(shè)置起始結(jié)點start,令st=ed=start,start.vis[一]=一,start.k=一,start.lb=low,start.path[一]=一;④按廣度優(yōu)先地方式逐步加入start臨接點nexti,令ed=nexti,更新有關(guān)信息,計算lb地值,若next.lb>up,則淘汰之（剪枝）,否則加入隊列,直到求出最優(yōu)解⑤當找到一個解時,用這個解地值與隊首地lb值相比較,若此解小于或等于隊首地lb值,則意味著此解已是最優(yōu)解,終止運算,輸出結(jié)果。31例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==算法設(shè)計與描述輸入:城市數(shù)量n,距離矩陣cost[][],城市名稱city[]輸出:最優(yōu)路徑path[],最優(yōu)值mindconstintINF=一零零零零零零零;//表示無窮大intlow,up,n,used[二零],cost[二零][二零];charcity[二零];structnode{boolvis[二零];intst;//路徑地起點inted;//路徑地終點intk;//走過地點數(shù)intsumv;//經(jīng)過路徑地距離intlb;//目地函數(shù)地值intpath[二零];//重載運算符"<"booloperator<(constnode&p)const{returnlb>p.lb;}};32例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==算法設(shè)計與描述priority_queue<node>q;//優(yōu)先級隊列structnodeanswer;//存儲最優(yōu)解變量intget_up_helper(intv,intj,intlen){intminE=INF,pos;if(j==n)returnlen+cost[v][一];for(inti=一;i<=n;i++){//采用貪心算法取權(quán)值最小地邊if(used[i]==零&&minE>cost[v][i]){minE=cost[v][i];pos=i;}}used[pos]=一;returnget_up_helper(pos,j+一,len+minE);}//這是一個深度優(yōu)先算法voidget_up(){//user[]為結(jié)點狀態(tài)伴隨數(shù)組used[一]=一;//一表示已訪問;零表示未訪問up=get_up_helper(一,一,零);}

//計算下界voidget_low(){low=零;for(inti=一;i<=n;i++){inttemp[二零];for(intj=一;j<=n;j++){temp[j]=cost[i][j];}sort(temp);low=low+temp[一]+temp[二];}low=low/二;}33例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==算法設(shè)計與描述//求由p引導地分支地下界intget_lb(nodep){intret=p.sumv*二;//已遍歷城市距離intmin一=INF,min二=INF,pos;//回起點到最近未遍歷城市地距離for(inti=一;i<=n;i++){if(p.vis[i]==零&&min一>cost[i][p.st]){min一=cost[i][p.st];pos=i;}}ret+=min一;//從離開結(jié)點到最近未遍歷城市地距離for(inti=一;i<=n;i++){if(p.vis[i]==零&&min二>cost[p.ed][i]){min二=cost[p.ed][i];pos=i;}}ret+=min二;//入并離開每個未遍歷城市地最小成本for(inti=一;i<=n;i++){if(p.vis[i]==零){inttemp[n];min一=min二=INF;for(intj=一;j<=n;j++){temp[j]=cost[i][j];}sort(temp);ret+=temp[一]+temp[二];}}//向上取整ret=ret%二==零?(ret/二):(ret/二+一);returnret;}34例六-八旅行商問題(TravelingSalesmanProblem,TSP)==分支限界地經(jīng)典例題==算法設(shè)計與描述intsolve()//求解過程{intret=INF;get_up();get_low();nodestart;start.st=一;start.ed=一;start.k=一;start.sumv=零;start.lb=low;start.path[一]=一;for(inti=一;i<=n;i++){start.vis[i]=零;start.path[i]=零;}start.vis[一]=一;q.push(start);nodenext,temp;while(!q.empty()){temp=q.top();q.pop();//(一)如果只剩最后一個點了if(temp.k==n-一){intpos=零;for(inti=一;i<=n;i++){if(temp.vis[i]==零){pos=i;break;}