实验三：分支限界法.doc

算法设计与分析实验报告三 实验名称分支限界法实现TSP问题系 别计算机科学与技术姓 名冯文涛学 号201108030241班 级二班实验地点Scl4实验日期2013/11/28指导老师吕亚丽同组其他成员一、实验内容：应用分支限界法求解从顶点a出发的TSP问题，写出在解空间树上的搜索过程 a 2 b 5 7 8 3 C 1 d 二、实验目的：1.了解分支限界法的思想 2.学会使用分支限界法解题 三、算法分析： * 2 5 7 2 * 8 3 5 8 * 1 7 3 1 * 无向矩阵图 贪心法最优解 a b d c a 2 3 1 5 2+3+1+5=11分支限界法：(2+5+2+3+5+1+3+1)/2=11限界函数的计算方法： a到b：(2*2+5+3+5+1+3+1)/2=11 a到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=11 a b a c a d lb=11 lb=11 lb=14 b c b d c b c d lb=16 1b=11 lb=20 lb=11 b c d b lb=11 lb=9 所以最优解为：a b d c a 2 3 1 5 最短路程：11 四、算法描述1.根据限界函数计算目标函数的下界down； 采用贪心法得到上界up；2. 计算根结点的目标函数值并加入待处理结点表PT；3. 循环直到某个叶子结点的目标函数值在表PT中取得极小值 3.1 i = 表PT中具有最小值的结点； 3.2 对结点i的每个孩子结点x执行下列操作： 3.2.1 估算结点x的目标函数值lb; 3.2.2 若(lb=up)，则将结点x加入表PT中； 否则丢弃该结点；4. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量； 五.实验程序：#include#include#define N 200using namespace std;class HeapNode public: double uprofit,profit,weight; int level,xN;stack H;double wN,pN;double cw,cp,c;int n;double Bound(int i) double cleft=c-cw,b=cp; while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; if(i=n) b+=pi/wi*cleft; return b;void AddLiveNode(double up,double cp,double cw,bool ch,int level) HeapNode nod; nod.uprofit=up; fit=cp; nod.weight=cw; nod.level=level; if(level=n) H.push(nod);double Knap() int i=1; cw=cp=0; double bestp=0,up=Bound(1); while(1) double wt=cw+wi; if(wtbestp) bestp=cp+pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up=Bound(i+1); if(up=bestp) AddLiveNode(up,cp,cw,false,i+1); if(H.empty() return bestp; HeapNode node=H.top(); H.pop(); cw=node.weight; cp=fit; up=node.uprofit; i=node.level; int main() coutnc; cou