实验三：分支限界法.doc

《实验三：分支限界法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告三实验名称分支限界法实现TSP问题系别计算机科学与技术姓名 冯文涛学号201108030241班级 二班实验地点 Scl4实验日期 2013/11/28 指导老师 吕亚丽同组其他成员 一、实验内容：应用分支限界法求解从顶点a出发的TSP问题，写出在解空间树上的搜索过程a2b5783C1d二、实验目的：1.了解分支限界法的思想2.学会使用分支限界法解题三、算法分析：*2572*8358*1731*无向矩阵图贪心法最优解abdca23152+3+1+5=11分支限界法：(2+5+2+3+5+1+3+1)/2=

2、11限界函数的计算方法：a到b：(2*2+5+3+5+1+3+1)/2=11a到c：(2*5+2+1+2+3+3+1)/2=11a到d:（2*7+2+1+2+3+5+1）/2=14排除a到b到c：(2*(2+8)+7+1+3+1)/2=16排除a到b到d:(2*(2+3)+5+1+5+1)/2=11a到c到b：(2*(5+8)+7+3+3+1)/2=20排除a到c到d:(2*(5+1)+2+3+2+3)/2=11a到b到d到c：(2*(2+8+1))/2=11a到c到d到b:(2*(5+1+3))/2=9排除lb=11abac

3、adlb=11lb=11lb=14bcbdcbcdlb=161b=11lb=20lb=11bcdblb=11lb=9所以最优解为：abdca2315最短路程：11四、算法描述1.根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2.计算根结点的目标函数值并加入待处理结点表PT；3.循环直到某个叶子结点的目标函数值在表PT中取得极小值3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作：3.2.1估算结点x的目标函数值lb;3.2.2若(lb<=up)，则将结点x加入表PT中；否则丢弃该结

4、点；4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量；五.实验程序：#include#include#defineN200usingnamespacestd;classHeapNode{public:doubleuprofit,profit,weight;intlevel,x[N];};stackH;doublew[N],p[N];doublecw,cp,c;intn;doubleBound(inti){doublecleft=c-cw,b=cp;while(i<=

5、n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}if(i<=n)b+=p[i]/w[i]*cleft;returnb;}voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel){HeapNodenod;nod.uprofit=up;nod.profit=cp;nod.weight=cw;nod.level=level;if(level<=n)H.push(nod);}doubleKnap(){inti=1;cw=cp=0;doubl

6、ebestp=0,up=Bound(1);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);if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);if(H.empty())returnbestp;HeapNodenode=H.top();H.pop();cw=node.weight;cp=node.

7、profit;up=node.uprofit;i=node.level;}}intmain(){cout<<"请输入n和c:";cin>>n>>c;cout<<"请输入w[i]"<>w[i];cout<<"请输入p[i]"<>p[j];cout<<"最优值是："<