《旅行商问题实验报告》由会员分享，可在线阅读，更多相关《旅行商问题实验报告（4页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告 姓名： xx 班级： xxxx 学号： xxxxxx 实验名称：旅行商问题实验目的：1.分支限界法按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。2.分支限界法适用于求解最优化问题。实验程序：输入：图G=（V, E） 输出：最短哈密顿回路1. 根据限界函数计算目标函数的下界down；采用贪心法得到上界up;2. 计算根节点的目标函数并加入待处理的结点表PT;3. 循环直到某个叶子结点的目标函数值在表PT中取得极小值
2、3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作； 估算结点x的目标函数值lb； 若（lb=up）,则将结点x加入表PT中，否则丢弃该结点；4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量。实验分析：问题描述：TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C= 3 1 5 8 3 6 7 91 6 4 25 7 4 38 9 2 3 采用贪心法求得近似解为：135421，其路径长度为1+2+3+7+3=16,这可以作为TSP问题的上界，把矩阵中每一行最小的两个元素相加再除以2，得到TSP问题的下界：(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,于是得到目标函数的界14,16。一般情况下，假设当前已确定的路径为U=(r1, r2, , rk)，即路径上已确定了k个顶点，此时，该部分解的目标函数值的计算方法（限界函数）如下： 分支限界法求解图上机心得与体会：时间复杂性分析：分支限界法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。
