实验三分支限界法.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=11 a到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=11 a到c到b：(2*(5+8)+7+3+3+1)/2=20 排除 a到c到d:(2*(5+1)+2+3+2+3)/2=11 a到b到d到c：(2*(2+8+1))/2=11 a到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. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量； 五.实验程序： #includeiostream #includestack #define N 200 using namespace std; class HeapNode { public: double uprofit,profit,weight; int level,x[N]; }; stackHeapNode H; double w[N],p[N]; dou