实验三分支限界法

《实验三分支限界法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析实验报告三实验名称分支限界法实现TSP问题系另

2、J计算机科学与技术姓名冯文涛学号201108030241班级二班实验地点Scl4实验日期2013/11/28指导老师吕亚丽同组其他成员一、实验内容过程aC:应用分支限X界法求解从顶点a出发的TSP问题，写出在解空间树上的搜索d二、实验目的：1.了解分支限界法的思想2.学会使用分支限界法解题三、算法分析：

3、*257

4、2*8358氺1731*无向矩阵图贪心法最优解a——>-b_►-d►—€►a23152+3+1+5=11分支限界法：(2+5+2+3+5+1+3+1)/2=11限界函数的计算方法：又--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所以最优解为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.根据限界函数计算目标函数的下界down；采用贪心法得到上界up;2.计算根结点的目标函数值并加入待处理结点表PT;3.循环直到某个叶子结点的目标函数值在表FT中取得极小值3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作：3.2.1估算结点x的目标函数值lb;3.2.2若（lb〈=up）,则将结点x加入表PT中；否则丢弃该结点；4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量;五.实验程序:#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〈〈〃最优值是：〃〈〈Knap()<