實驗三分支限界法

《實驗三分支限界法》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、算法設計與分析實驗報告三實驗名稱分支限界法實現(xiàn)TSP問題系另

2、J計算機科學與技術姓名馮文濤學號201108030241班級二班實驗地點Scl4實驗日期2013/11/28指導老師呂亞麗同組其他成員一、實驗內容過程aC:應用分支限X界法求解從頂點a出發(fā)的TSP問題，寫出在解空間樹上的搜索d二、實驗目的：1.了解分支限界法的思想2.學會使用分支限界法解題三、算法分析：

3、*257

4、2*8358氺1731*無向矩陣圖貪心法最優(yōu)解a——>-b_?-d?—€?a23152+3+1+5=11分支限界法：(2+5+2+3+5+1+3+1)/2=11限界函數(shù)的計算方法：又--1//7=(2Ec

5、[z}][么]+[巧行不在路徑上的最小元素+[r/于最小的兩個元素)/2/=!i=hkr;eUa到b:(2*2+5+3+5+l+3+l)/2=lla到c:(2*5+2+l+2+3+3+l)/2=lla到d:(2*7+2+l+2+3+5+l)/2=14排除a到b到c:(2*(2+8)+7+l+3+l)/2=16排除a到b到d:(2*(2+3)+5+l+5+l)/2=lla到c到b:(2*(5+8)+7+3+3+1)/2=20排除a到c到d:(2*(5+1)+2+3+2+3)/2=ll所以最優(yōu)解為w2最短路程：11d->>c315a到b到d到c:(2*(2+8+l))/2=lla

6、到c到d到b:(2*(5+1+3))/2=9排除blb=ll人lb=9、算法描述1.根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界up;2.計算根結點的目標函數(shù)值并加入待處理結點表PT;3.循環(huán)直到某個葉子結點的目標函數(shù)值在表FT中取得極小值3.1i=表PT中具有最小值的結點；3.2對結點i的每個孩子結點x執(zhí)行下列操作：3.2.1估算結點x的目標函數(shù)值lb;3.2.2若（lb〈=up）,則將結點x加入表PT中；否則丟棄該結點；4.將葉子結點對應的最優(yōu)值輸出，回溯求得最優(yōu)解的各個分量;五.實驗程序:#include#include#

7、defineN200usingnamespacestd;classHeapNodepublic:doubleuprofit,profit,weight;intlevel,x[N];｝；stackH;doublew[N],p[N];doublecw，cp，c;intn;doubleBound(inti)doublecleft=c-cw，b=cp;while(i<=n&&w[i]<=cleft)b+=p[i];i++;if(i<=n)b+=p[i]/w[i]*cleft;returnb;voidAddLiveNode(doubleup,doublecp,dou

8、blecw,boolch,intlevel)HeapNodenod;nod.uprofit=up;nod.profit=cp;nod.weight=cw;nod.level=level:if(level<=n)H.push(nod);doubleKnap()inti=l;cw=cp=0:doublebestp=0,up=Bound(l):while(1)doublewt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up二Bound(i+1)

9、;if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);if(H.empty())returnbestp;HeapNodenode=H.top();H.pop();cw=node.weight;cp=node.profit;up=node.uprofit:i=node.level;main()cout〈〈〃請輸入n和c:〃；cin?n?c;cout〈〈〃請輸入w[i]"〈〈endl;for(inti=l;i〈=n;i++)cin〉〉w[i];cout〈〈"請輸入p[i]"〈〈endl;for(intj=l;j〈=n;j++)cin?p[j]

10、:cout〈〈〃最優(yōu)值是：〃〈〈Knap()<